Study Abroad and Exchanges

# Modules

### CSC2023 : Algorithm Design and Analysis

• Offered for Year: 2017/18
• Module Leader(s): Dr Jason Steggles
• Lecturer: Professor Maciej Koutny, Dr Changyu Dong
• Owning School: Computing
• Teaching Location: Newcastle City Campus
##### Semesters
 Semester 1 Credit Value: 20 ECTS Credits: 10.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.

This module provides an introduction to the design and analysis of algorithms. It begins by considering a range of illustrative application areas including sorting, searching and numerical algorithms. It then looks in more detail at key techniques for designing algorithmic solutions and introduces approaches for analysing algorithms.

#### Outline Of Syllabus

Discrete Structures – basics of counting
•       Solving recurrence relations
•       Common examples
•       The Master theorem
Discrete Structures – graphs and trees
•       Spanning trees/forests
•       Traversal strategies
Algorithms and Complexity – basic analysis
•       Asymptotic analysis of upper and average complexity bounds
•       Identifying differences among best, average, and worst case behaviours
•       Big O, little o, omega, and theta notation
•       Standard complexity classes
•       Empirical measurements of performance
•       Time and space tradeoffs in algorithms
•       Using recurrence relations to analyze recursive algorithms
Algorithms and Complexity – algorithmic strategies
•       Brute-force algorithms
•       Greedy algorithms
•       Divide-and-conquer
•       Backtracking
•       Branch-and-bound
•       Heuristics
•       Pattern matching and string/text algorithms
•       Numerical approximation algorithms
Algorithms and Complexity – fundamental algorithms
•       Simple numerical algorithms
•       Sequential and binary search algorithms
•       Quadratic sorting algorithms (selection, insertion)
•       O(N log N) sorting algorithms (Quicksort, heapsort, mergesort)
•       Hash tables, including collision-avoidance strategies
•       Binary search trees
•       Representations of graphs (adjacency list, adjacency matrix)
•       Depth- and breadth-first traversals
•       Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
•       Transitive closure (Floyd’s algorithm)
•       Minimum spanning tree (Prim’s and Kruskal’s algorithms)
Algorithms and Complexity – geometric algorithms
•       Closest pair
•       Convex hull finding algorithms
Algorithms and Complexity – advanced analysis
•       Online and offline algorithms
Algorithms and Complexity – P versus NP
•       Standard NP-complete problems

#### Teaching Methods

##### Teaching Activities
Category Activity Number Length Student Hours Comment
Scheduled Learning And Teaching ActivitiesLecture441:0044:00Lectures
Guided Independent StudyAssessment preparation and completion500:3025:00Revision for end of Semester exam and exam duration
Guided Independent StudyAssessment preparation and completion441:0044:00Lecture follow-up
Scheduled Learning And Teaching ActivitiesSmall group teaching221:0022:00Tutorials
Guided Independent StudyProject work301:0030:00Coursework
Guided Independent StudyIndependent study351:0035:00Background reading
Total200:00
##### Teaching Rationale And Relationship

Techniques, theory and examples are presented in lectures. Examples and practice exercises are undertaken in the tutorial. Further exercise work takes place during the private study hours.

#### Assessment Methods

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

##### Exams
Description Length Semester When Set Percentage Comment
PC Examination1201A80Blackboard Exam
##### Other Assessment
Description Semester When Set Percentage Comment
Practical/lab report1M10programming coursework on algorithms (15 hours)
Practical/lab report1M10programming coursework on algorithms (15 hours)
##### Assessment Rationale And Relationship

Each examination will cover the material taught in lectures.
An important objective of the course is to develop students' practical abilities in designing, analysing and implementing algorithms. This will be assessed by coursework that cover these key aspects.

Study abroad students considering this module should contact the School to discuss its availability and assessment.

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