Undergraduate Course: Algorithms and Data Structures (INFR09006)
Course Outline
School  School of Informatics 
College  College of Science and Engineering 
Course type  Standard 
Availability  Available to all students 
Credit level (Normal year taken)  SCQF Level 9 (Year 3 Undergraduate) 
Credits  10 
Home subject area  Informatics 
Other subject area  None 
Course website 
http://www.inf.ed.ac.uk/teaching/courses/ads 
Taught in Gaelic?  No 
Course description  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. 
Entry Requirements (not applicable to Visiting Students)
Prerequisites 
Students MUST have passed:
Informatics 2B  Algorithms, Data Structures, Learning (INFR08009) AND (
Mathematics for Informatics 3a (MATH08042) OR
Foundations of Calculus (MATH08005)) AND (
Mathematics for Informatics 3b (MATH08043) OR
Linear Algebra (MATH08007)) AND (
Mathematics for Informatics 4a (MATH08044) OR
Methods of Applied Mathematics (MATH08035)) AND (
Mathematics for Informatics 4b (MATH08045) OR
Several Variable Calculus (MATH08006))

Corequisites  
Prohibited Combinations  
Other requirements  Students who did not take Inf2B should get special permission from the course lecturer.
Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School.
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, Onotation, proof by contradiction. 
Additional Costs  None 
Information for Visiting Students
Prerequisites  None 
Displayed in Visiting Students Prospectus?  Yes 
Course Delivery Information

Delivery period: 2011/12 Semester 1, Available to all students (SV1)

WebCT enabled: No 
Quota: None 
Location 
Activity 
Description 
Weeks 
Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
Central  Lecture   111   10:00  10:50     Central  Lecture   111      10:00  10:50 
First Class 
Week 1, Tuesday, 10:00  10:50, Zone: Central. Minto House Lec Rm 1 
Exam Information 
Exam Diet 
Paper Name 
Hours:Minutes 


Main Exam Diet S2 (April/May)   2:00    Resit Exam Diet (August)   2:00   

Delivery period: 2011/12 Semester 1, Partyear visiting students only (VV1)

WebCT enabled: No 
Quota: None 
Location 
Activity 
Description 
Weeks 
Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
Central  Lecture   111   10:00  10:50     Central  Lecture   111      10:00  10:50 
First Class 
Week 1, Tuesday, 10:00  10:50, Zone: Central. Minto House Lec Rm 1 
Exam Information 
Exam Diet 
Paper Name 
Hours:Minutes 


Main Exam Diet S1 (December)   2:00   
Summary of Intended 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 DivideandConquer, 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/runningtime 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 averagecase analyses of the runningtime of an algorithm, as well as worstcase analyses.

Assessment Information
Written Examination 75
Assessed Assignments 25
Oral Presentations 0
Assessment
In addition to the written exam there are two pieces of assessed coursework, which involve pen and paper exercises and programming.
If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year. 
Special Arrangements
None 
Additional Information
Academic description 
Not entered 
Syllabus 
Introductory concepts
Review of CS2. Models of computation; time and space complexity; upper and lower bounds, bigO and bigOmega 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.
Sorting
Quicksort and its analysis; worstcase, bestcase and averagecase.
Data structures: Disjoint sets
The ``disjoint sets'' (unionfind) abstract data type: specification and implementations as lists and trees. Unionbyrank, pathcompression, etc., ``heuristics''. Applications to finding minimum spanning trees.
Dynamic programming
Introduction to the technique; examples: Matrixchain multiplication, Longest common subsequences.
Graph/Network algorithms
Network flow, Maxflow/mincut theorem, FordFulkerson algorithm.
Geometric algorithms
Convex hull of a set of points (in 2d).
Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms 
Transferable skills 
Not entered 
Reading list 
* Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd Edition). MIT Press, 2002. (Course text)
* Goodrich, Tamassia: Algorithm Design  Foundations, Analysis, and Internet Examples. Wiley, 2002.
* Kleinberg, Tardos: Algorithm Design. AddisonWesley, 2005.

Study Abroad 
Not entered 
Study Pattern 
Lectures 20
Tutorials 8
Timetabled Laboratories 0
Nontimetabled assessed assignments 25
Private Study/Other 47
Total 100 
Keywords  Not entered 
Contacts
Course organiser  Dr Nigel Goddard
Tel: (0131 6)51 3091
Email: Nigel.Goddard@ed.ac.uk 
Course secretary  Miss Tamise Totterdell
Tel: 0131 650 9970
Email: t.totterdell@ed.ac.uk 

