Course finder

<< return to browsing

Semester 1

Algorithms and Data Structures (INFR10052)

Course Website

http://course.inf.ed.ac.uk/ads

Subject

Informatics

College

SCE

Credits

10

Normal Year Taken

3

Delivery Session Year

2023/2024

Pre-requisites

Visiting students are required to have comparable background to that assumed by the course prerequisites listed in the Degree Regulations & Programmes of Study. If in doubt, consult the Course organiser (lecturer).

Course Summary

The course aims to provide general techniques for the design of efficient algorithms and, in parallel, develop appropriate mathematical tools for analysing their performance. In this, it broadens and deepens the study of algorithms and data structures initiated in INF2. The focus is on algorithms, more than data structures. Along the way, problem solving skills are exercised and developed.

Course Description

Introductory conceptsReview of CS2. Models of computation; time and space complexity; upper and lower bounds, big-O and big-Omega notation; average and worst case analysis.Divide and conquerMatrix multiplication: Strassen's algorithm; the discrete Fourier transform (DFT), the fast Fourier transform (FFT). Expressing the runtime of a recursive algorithm as a recurrence relation; solving recurrence relations.SortingQuicksort and its analysis; worst-case, best-case and average-case.Data structures: Disjoint setsThe "disjoint sets'' (union-find) abstract data type: specification and implementations as lists and trees. Union-by-rank, path-compression, etc., "heuristics''. Applications to finding minimum spanning trees.Dynamic programmingIntroduction to the technique; examples: Matrix-chain multiplication, Longest common subsequences.Graph/Network algorithmsNetwork flow, Max-flow/min-cut theorem, Ford-Fulkerson algorithm.Geometric algorithmsConvex hull of a set of points (in 2-d).Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms

Assessment Information

Written Exam 75%, Coursework 25%, Practical Exam 0%

Additional Assessment Information

In addition to the written exam, there is one piece of assessed coursework.This should take about 8-9 hours.There will also be one formative assessment (5-6 hours) earlier in the semester to allow you to submit work and obtain feedback on your submission; that earlier piece of formative work will not contribute to your overall grade.

view the timetable and further details for this course