Computer Laboratory – Course pages 2015–16: Algorithms – Course materials Skip to content | Access key help Search Advanced search A–Z Contact us Computer Laboratory Computer Laboratory Teaching Courses 2015–16 Algorithms Course materials 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 Lectures Mon-Wed-Fri 1000-1100 in Mill Lane Lecture Room 9, from Fri 2016-01-15 to Wed 2016-03-09 inclusive (12 with FMS + 12 with TMS = 24 lectures). Lec 13, 2016-02-12 Fri (5.1 Amortized Analysis) CLRS3: 17.1-17.3 Handout: pages 88-92 Slides: PDF Lec 14, 2016-02-15 Mon (5.2 Fibonacci Heaps) CLRS3: 19.1-19.3 (without amortized analysis) Handout: pages 93-98 Slides: PDF Lec 15, 2016-02-17 Wed (5.2 Fibonacci Heaps (Analysis)) CLRS3: 19.1-19.4 Handout: pages 99-102 Slides: PDF, Animations illustrating high actual cost for ExtractMin and DecreaseKey PDF (by Stella Lau), PDF (by Milos Stanojevic), PDF (by Gábor Szarka), PDF (by Patrik Turzák). Lec 16, 2016-02-19 Fri (5.3 Disjoint Sets) CLRS3: 21.1-21.3 Handout: pages 103-107 Slides: PDF Lec 17, 2016-02-22 Mon (6.1 & 6.2 Graph Searching) CLRS3: 22.1-22.4 Handout: pages 108-114 Slides: PDF Lec 18, 2016-02-24 Wed (6.3 Minimum Spanning Trees) CLRS3: 23.1-23.2 Handout: pages 115-119 Slides: PDF Lec 19, 2016-02-26 Fri (6.4 Single-Source Shortest Paths (Intro, Bellman-Ford)) CLRS3: 24.1 Handout: pages 120-122 Slides: PDF Lec 20, 2016-02-29 Mon (6.4 Single-Source Shortest Paths (Dijkstra)) CLRS3: 24.3 Handout: pages 123-125 Slides: PDF Correction on Slide 20 (Dijkstra's Algorithm 2/2): "Maintain set S of vertices u with u.delta = v.d" should be "Maintain set S of vertices u with u.delta = u.d" Lec 21, 2016-03-02 Wed (6.6 Maximum Flow (Greedy & Ford Fulkerson)) CLRS3: 26.1-26.2 Handout: pages 129-131 Slides: PDF Correction on Slide 7 (the residual capacities of the edges (4,5) and (5,4) must be swapped) Lec 22, 2016-03-04 Fri (6.6 Maximum Flow (Ford Fulkerson and Max-Flow Min-Cut Theorem)) CLRS3: 26.2 Handout: pages 131-132 Slides: PDF Proof of the easy direction of the Max-Flow Min-Cut Theorem added (Slide 12) Lec 23, 2016-03-07 Mon (6.6 Maximum Flow (Bipartite Matching), 6.5 All-Pairs Shortest Paths) CLRS3: 26.3, 25.1, 25.3 Handout: pages 125-128 Slides: PDF For the Bipartite Matching Problem, see the (expanded) slides from 2016-03-04. The correctness proof of the correspondence between Bipartite Matching and Maximum Flow was not covered and is not examiable. Lec 24, 2016-03-09 Wed (7. Geometric Algorithms) CLRS3: 33.1, 33.3 Handout: pages 135-141 Slides: PDF Correction on Slide 9 (the arguments of the function SEGMENTS-INTERSECT should be (p1,p2,p3,p4)) Glimpse at (More) Advanced Algorithm is (obviously) not examinable Slides of Lectures 13-24 in one PDF Lecture handout Distributed during the first lecture. It will be to your advantage to bring your handout to every lecture, together with a notebook with non-detachable pages and a few coloured pens. Further printed copies of the handout are available from the student administration office in the William Gates Building. An electronic copy is also available. Write to the author if you discover any errors and you'll be credited in the next edition. A printed copy of the slides for Lectures 13-24 in condensed format has been distributed in Lecture 13. An electronic copy is also available. Write to the author if you discover any errors and you'll be credited. Errata Corrige Negative lines counted from bottom of page. Page Line Errata Corrige Reported on by 34 3..4 One, like Quicksort itself, has linear cost in the average case, but has a quadratic worst-case cost. One has linear cost in the average case but, like Quicksort itself, has a quadratic worst-case cost. 2016-01-21 Simone Teufel Supervisions Please use the online Otter system, which is still somewhat experimental, and help us make it work for you by providing constructive feedback on how it could be improved. We are aware that there may be teething problems but please support us. To smooth out the transition, here is a legacy exercise sheet in pdf but new exercises will only be added to Otter from now on. Past exam questions for Algorithms I, Algorithms II, Data Structures and Algorithms and Algorithms may be of interest. If you want to own this material rather than just memorize it, attempt the questions as seriously as if you were taking the exam yourself and do not open the solution notes until after having irrevocably committed (no more changes) to your own solution. The best students already understand the wisdom of this advice; for the others, yeah, the pressure is high, the temptation is strong, the flesh is weak... If you are a supervisor Thanks for supervising. Please email frank dot stajano hyphen hyphen algs @cl.cam.ac.uk with your CRSID and ask your supervisor to tell Frank that she or he agrees that you should be supervising this course. You will then be granted access to the "information for supervisors" tab and added to the list of people who should know about supervisor-relevant stuff. Instructions for lecturers: how to edit this page © 2016 Computer Laboratory, University of Cambridge Information provided by Dr Frank Stajano
