Computer Laboratory – Course pages 2015–16: Algorithms Skip to content | Access key help Search Advanced search A–Z Contact us Computer Laboratory Computer Laboratory Teaching Courses 2015–16 Algorithms Preparation for Computer Science Digital Electronics Discrete Mathematics Foundations of Computer Science Hardware Practical Classes ML Practical Classes Object-Oriented Programming Registration Algorithms Operating Systems Further Java Briefing Numerical Methods Software and Interface Design Course pages 2015–16 Algorithms Syllabus Course materials Information for supervisors Algorithms ticks Principal lecturers: Dr Frank Stajano, Dr Thomas Sauerwald Taken by: Part IA CST, Part IA NST, Part I PBS Past exam questions No. of lectures and practical classes: 24 + 3 (NST and PBST students take 1 practical) Suggested hours of supervisions: 6 to 8 Prerequisite courses: Foundations of Computer Science, Object-Oriented Programming This course is a prerequisite for: Artificial Intelligence, Complexity Theory, Computer Graphics and Image Processing , Prolog, Advanced Algorithms Aims The aim of this course is to provide an introduction to computer algorithms and data structures, with an emphasis on foundational material. Lectures Sorting. Review of complexity and O-notation. Trivial sorting algorithms of quadratic complexity. Review of merge sort and quicksort, understanding their memory behaviour on statically allocated arrays. Heapsort. Stability. Other sorting methods including sorting in linear time. Median and order statistics. [Ref: CLRS3 chapters 1, 2, 3, 6, 7, 8, 9] [about 4 lectures] Strategies for algorithm design. Dynamic programming, divide and conquer, greedy algorithms and other useful paradigms. [Ref: CLRS3 chapters 4, 15, 16] [about 3 lectures] Data structures. Primitive data structures. Abstract data types. Pointers, stacks, queues, lists, trees. Binary search trees. Red-black trees. B-trees. Hash tables. Priority queues and heaps. [Ref: CLRS3 chapters 6, 10, 11, 12, 13, 18] [about 5 lectures] Advanced data structures. Amortized analysis: aggregate analysis, potential method. Fibonacci heaps. Disjoint sets. [Ref: CLRS3 chapters 17, 19, 20, 21] [about 4 lectures] Graph algorithms. Graph representations. Breadth-first and depth-first search. Topological sort. Minimum spanning tree. Kruskal and Prim algorithms. Single-source shortest paths: Bellman-Ford and Dijkstra algorithms. All-pairs shortest paths: matrix multiplication and Johnson’s algorithms. Maximum flow: Ford-Fulkerson method, Max-Flow Min-Cut Theorem. Matchings in bipartite graphs. [Ref: CLRS3 chapters 22, 23, 24, 25, 26] [about 7 lectures] Geometric algorithms. Intersection of segments. Convex hull: Graham’s scan, Jarvis’s march. [Ref: CLRS3 chapter 33] [about 1 lecture] Objectives At the end of the course students should have a thorough understanding of several classical algorithms and data structures; be able to analyse the space and time efficiency of most algorithms; have a good understanding of how a smart choice of data structures may be used to increase the efficiency of particular algorithms; be able to design new algorithms or modify existing ones for new applications and reason about the efficiency of the result. Recommended reading * Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN 978-0-262-53305-8 Sedgewick, R., Wayne, K. (2011). Algorithms Addison-Wesley. ISBN 978-0-321-57351-3. Kleinberg, J. & Tardos, É. (2006). Algorithm design. Addison-Wesley. ISBN 978-0-321-29535-4. Knuth, D.A. (2011). The Art of Computer Programming. Addison-Wesley. ISBN 978-0-321-75104-1. Students hoping to receive a computer science degree from Cambridge are expected to buy, make extensive use of, and keep as reference for their future career, one of the above fundamental textbooks: those not doing so will be severely disadvantaged. The recommended choice is Cormen, Leiserson, Rivest and Stein (CLRS3, starred in the above list) which covers all topics listed and, in spite of its superb quality, is the cheapest: about 35 GBP new for over 1300 pages. The references in the syllabus are to this textbook. The other textbooks listed are excellent additions for further study but might cost more and yet not cover the entire syllabus. © 2016 Computer Laboratory, University of Cambridge Information provided by Dr Frank Stajano
