Archive for reference only

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Undergraduate Course: Algorithms and Data Structures (INFR09006)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 9 (Year 3 Undergraduate) AvailabilityAvailable to all students
SCQF Credits10 ECTS Credits5
SummaryThe 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 concepts
Review 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 conquer
Matrix 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.

Quicksort and its analysis; worst-case, best-case and average-case.

Data structures: Disjoint sets
The ``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 programming
Introduction to the technique; examples: Matrix-chain multiplication, Longest common subsequences.

Graph/Network algorithms
Network flow, Max-flow/min-cut theorem, Ford-Fulkerson algorithm.

Geometric algorithms
Convex hull of a set of points (in 2-d).

Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms
Entry Requirements (not applicable to Visiting Students)
Pre-requisites Students MUST have passed: Informatics 2B - Algorithms, Data Structures, Learning (INFR08009) AND Probability with Applications (MATH08067) AND Discrete Mathematics and Mathematical Reasoning (INFR08023)
Prohibited Combinations Other requirements This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser.

Joint honours students (or Maths students) who took different second-year Maths courses should get permission of the Course lecturer

Students who did not take Inf2B should get special permission from the course lecturer.

This course has the following mathematics prerequisites:

1 - Calculus: limits, sums, integration, differentiation, recurrence relations, the Master theorem.
2 - Graph theory: graphs, digraphs, components, trees, weighted graphs, DFS, BFS.
3 - Probability: random variables, expectation, variance, Markov's inequality, Chebychev's inequality
4 - Linear algebra: vectors, matrices, matrix multiplication, scalar products.
5 - Complex numbers: the imaginary unit i, addition and multiplication in C, exponentiation.
6 - Generalities: induction, O-notation, proof by contradiction.
Information for Visiting Students
Course Delivery Information
Not being delivered
Learning Outcomes
1 - Should be able to describe, and implement, the major algorithms for well known combinatorial problems such as Sorting, Matrix Multiplication, Minimum Spanning Trees, and other problems listed in the syllabus.
2 - Should be able to demonstrate familiarity with algorithmic strategies such as Divide-and-Conquer, the Greedy strategy and Dynamic Programming; and should be able to test these strategies on new problems and identify whether or not they are likely to be useful for those problems.
3 - Should be able to construct clear and rigorous arguments to prove correctness/running-time bounds of algorithms, and should be able to present these arguments in writing.
4 - Should be able to explain the importance of the data structures used in a particular implementation of an algorithm, and how the data structure that is used can affect the running time.
5 - Should be able to construct simple lower bound arguments for algorithmic problems, and to understand the relationship between upper and lower bounds. Also should be able to perform simple average-case analyses of the running-time of an algorithm, as well as worst-case analyses.
Reading List
Introduction to Algorithms (3rd Edition), Cormen, Leiserson, Rivest, Stein: . MIT Press, 2002. (Course text)

Additional Information
Course URL
Graduate Attributes and Skills Rigorous mathematics reasoning
KeywordsNot entered
Course organiserDr Mary Cryan
Tel: (0131 6)50 5153
Course secretaryMrs Victoria Swann
Tel: (0131 6)51 7607
Help & Information
Search DPTs and Courses
Degree Programmes
Browse DPTs
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Important Information
© Copyright 2014 The University of Edinburgh - 12 January 2015 4:10 am