Undergraduate Course: Algorithms and Data Structures (INFR10052)

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 10 (Year 3 Undergraduate)	Credits	10
Home subject area	Informatics	Other subject area	None
Course website	http://course.inf.ed.ac.uk/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)
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)	Co-requisites
Prohibited Combinations	Students MUST NOT also be taking Algorithms and Data Structures (INFR09006)	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, confidence in proving theorems.
Additional Costs	None

Information for Visiting Students
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 lecturer.
Displayed in Visiting Students Prospectus?	Yes

Course Delivery Information

Delivery period: 2014/15 Semester 1, Available to all students (SV1)			Learn enabled: No	Quota: None
Web Timetable	Web Timetable
Course Start Date	15/09/2014
Breakdown of Learning and Teaching activities (Further Info)	Total Hours: 100 ( Lecture Hours 20, Seminar/Tutorial Hours 8, Summative Assessment Hours 2, Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 68 )
Additional Notes
Breakdown of Assessment Methods (Further Info)	Written Exam 75 %, Coursework 25 %, Practical Exam 0 %
Exam Information
Exam Diet	Paper Name	Hours & Minutes
Main Exam Diet S2 (April/May)		2:00
Resit Exam Diet (August)		2:00

Delivery period: 2014/15 Semester 1, Part-year visiting students only (VV1)			Learn enabled: No	Quota: None
Web Timetable	Web Timetable
Course Start Date	15/09/2014
Breakdown of Learning and Teaching activities (Further Info)	Total Hours: 100 ( Lecture Hours 20, Seminar/Tutorial Hours 8, Summative Assessment Hours 2, Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 68 )
Additional Notes
Breakdown of Assessment Methods (Further Info)	Written Exam 75 %, Coursework 25 %, Practical Exam 0 %
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 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.

Assessment Information
In addition to the written exam there are two pieces of assessed coursework, which involve pen and paper exercises and programming. You should expect to spend approximately 25 hours on the coursework for this course. 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, 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. Sorting 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
Transferable skills	Rigorous mathematics reasoning
Reading list	Introduction to Algorithms (3rd Edition), Cormen, Leiserson, Rivest, Stein: . MIT Press, 2002. (Course text)
Study Abroad	Not entered
Study Pattern	Not entered
Keywords	Not entered

Contacts
Course organiser	Dr Mary Cryan Tel: (0131 6)50 5153 Email: mcryan@inf.ed.ac.uk	Course secretary	Miss Claire Edminson Tel: (0131 6)51 7607 Email: C.Edminson@ed.ac.uk