School of Computing Science

# School of Computing Science

### CSC2023 : Algorithm Design and Analysis

• Offered for Year: 2016/17
• Module Leader(s): Dr Jason Steggles
• Lecturer: Prof. Aad van Moorsel, Dr Changyu Dong
• Owning School: Computing Science
• Teaching Location: Newcastle City Campus
##### Semesters
 Semester 1 Credit Value: 20 ECTS Credits: 10.0
##### Pre Requisites
Code Title
CSC1025Mathematics for Computer Science

N/A

N/A

#### 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
•       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

#### Learning Outcomes

##### Intended Knowledge Outcomes

To be able to define and discuss:
- a range of basic numerical algorithms.
- the areas of sorting, searching and geometric algorithms.
- a variety of algorithm design techniques.
- algorithm complexity.
- the practical implications of polynomial and exponential complexity.

##### Intended Skill Outcomes

To be able to demonstrate:
- using pseudo code to document algorithms.
- practical skills in implementing a range of key algorithms.
- practical skills in analysing the complexity of algorithms.
- problem solving skills.
To be able to:
- assimilate, evaluate and analyse information as a result of independent or group research.
- formulate a practical solution to a problem, making effective use of time and resources available

• Cognitive/Intellectual Skills
• Critical Thinking : Assessed
• Data Synthesis : Present
• Active Learning : Present
• Literacy : Present
• Information Literacy
• Source Materials : Present
• Synthesise And Present Materials : Assessed
• Self Management
• Self Awareness And Reflection : Present
• Planning and Organisation
• Goal Setting And Action Planning : Present
• Personal Enterprise
• Independence : Present
• Problem Solving : Assessed

#### Teaching Methods

##### Teaching Activities
Category Activity Number Length Student Hours Comment
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 ActivitiesLecture441:0044:00Lectures
Scheduled Learning And Teaching ActivitiesSmall group teaching221:0022:00Tutorials
Guided Independent StudyProject work301:0030:00Coursework
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%.

#### General Notes

N/A

Disclaimer: The University will use all reasonable endeavours to deliver modules in accordance with the descriptions set out in this catalogue. Every effort has been made to ensure the accuracy of the information, however, the University reserves the right to introduce changes to the information given including the addition, withdrawal or restructuring of modules if it considers such action to be necessary.