Undergraduate

modules

Modules

CSC2032 : Algorithm Design and Analysis (Inactive)

Semesters
Semester 1 Credit Value: 10
ECTS Credits: 5.0

Aims

Knowledge of a range of key application areas where algorithmic solutions are required.
Understand the key issues in algorithm design.
Understand what makes a "good" algorithm.
Explore range of techniques that can be employed in the design of various types of algorithm.
Analyse the properties of key algorithms in terms of their time and space complexity.
Provide practical experience of implementing a range of algorithms.

Outline Of Syllabus

Fundamental Algorithms:
•       Numerical algorithms (root finding)
•       Search algorithms (sequential, binary search, binary search trees, hashing)
•       Sorting algorithms (selection, insertion, Quicksort)
•       String searching algorithms (brute force, Knuth Morris Pratt, Boyer Moore)
•       Graphs (Depth- and breadth-first traversals, shortest-path algorithms, minimum spanning tree)

Algorithm Analysis:
•       Asymptotic analysis of upper and average complexity bounds
•       Identifying differences among best, average, and worst case behaviours
•       Standard complexity classes
•       Time and space tradeoffs in algorithms
•       Using recurrence relations to analyze recursive algorithms
•       NP Complete problems

Algorithm Design Techniques:
•       Brute-force algorithms
•       Greedy algorithms
•       Divide-and-conquer
•       Backtracking
•       Branch-and-bound
•       Heuristics

Teaching Methods

Teaching Activities
Category Activity Number Length Student Hours Comment
Guided Independent StudyAssessment preparation and completion121:0012:00Formative assessment
Scheduled Learning And Teaching ActivitiesLecture221:0022:00Lectures
Guided Independent StudyAssessment preparation and completion351:0035:00Lecture follow-up
Guided Independent StudyAssessment preparation and completion250:3012:30Revision for end of semester exam
Guided Independent StudyAssessment preparation and completion11:301:30End of semester examination
Scheduled Learning And Teaching ActivitiesSmall group teaching121:0012:00Tutorials
Guided Independent StudyProject work15:005:00Coursework
Total100:00
Teaching Rationale And Relationship

Tutorials will be used to provide the opportunity for students to gain practical skills and understanding in the theory and techniques developed during lectures.

Exams provide a formal assessment of underlying techniques, and coursework assesses the application of skills to algorithmic problems.

Assessment Methods

The format of resits will be determined by the Board of Examiners

Exams
Description Length Semester When Set Percentage Comment
PC Examination901A80N/A
Other Assessment
Description Semester When Set Percentage Comment
Practical/lab report1M20Single implementation assignment equivalent to 1000 words.
Formative Assessments
Description Semester When Set Comment
Lab exercise1MExercise set as part of each tutorial as appropriate
Practical/lab report1MSample exam paper
Assessment Rationale And Relationship

The PC exam will be used to assess students' understanding and ability to apply the knowledge, theory and techniques covered in the course. The coursework assignment will be used to help develop and assess students' understanding of and abilities to practically apply knowledge and techniques covered on the course.

A range of formative assessments are used to support student’s self-study during the module and gauge their understanding as the course progresses.


NB. This module has both “Exam assessment” and “Other assessment” (e.g. coursework). If the total mark for either falls below 35%, the maximum mark returned for the module will normally be 35%

Reading Lists

Timetable