Computer Laboratory – Course material 2008–09: Algorithms I Skip over navigation | Access key help ||| Computer Laboratory Course material 2008–09 Computer Laboratory > Teaching > Course material 2008–09 > Algorithms I Additional Topics Advanced Graphics Advanced Systems Topics Algorithms I Algorithms II Artificial Intelligence I Artificial Intelligence II Bioinformatics Business Studies Comparative Architectures Compiler Construction Complexity Theory Computation Theory Computer Design Computer Graphics and Image Processing Computer Systems Modelling Computer Vision Concepts in Programming Languages Concurrent Systems and Applications Databases Denotational Semantics Digital Communication I Digital Communication II Digital Electronics Digital Signal Processing Discrete Mathematics I Discrete Mathematics II Distributed Systems E-Commerce ECAD ECAD Labs » Economics and Law Floating-Point Computation Foundations of Computer Science Foundations of Functional Programming Group Project Group Project Briefing Hardware Practical Classes How to Study Computer Science Human-Computer Interaction Information Retrieval Information Theory and Coding Introduction to Security Logic and Proof Long Vacation Java course Mathematical Methods for Computer Science Natural Language Processing Operating Systems I Optimising Compilers Part IB Assessed Exercise Briefing Probability Professional Practice and Ethics Programming Methods Programming in C and C++ Programming in Java Prolog Quantum Computing Registration Regular Languages and Finite Automata Security Semantics of Programming Languages Software Design Software Engineering Specification and Verification I Specification and Verification II System-on-Chip: Design and Modelling Topics in Concurrency Types Unix Tools Algorithms I 2008–09 Principal lecturer: Dr Frank Stajano Taken by: Part IA CST, Part IA NST, Part I PPS Syllabus Past exam questions Past exam questions can be found under Algorithms but also, for historical reasons, under Data Structures and Algorithms (the parent course for both Algorithms I and Algorithms II). Since these courses have been restructured several times over the years, be sure to select questions dealing with topics covered in this year's syllabus. Assessed exercises (required) The only way to really learn about algorithms and data structures is to program them yourself. Every Friday, for three Fridays, a new challenge will appear on this page. You will have to submit your solution (via email) by the following Wednesday in order to receive your tick. Tick 1 (issued 2009-04-24, due 2009-04-29) Tick 2 (issued 2009-05-01, due 2009-05-06) Tick 3 (issued 2009-05-08, due 2009-05-13) Lecture handouts A handout, covering the whole course, will be distributed during the first lecture. Bringing your handout to every lecture, together with a paper notebook with non-detachable pages and a few coloured pens, will be to your advantage. Further printed copies of the handout are available from the student administration office. An electronic copy is available (also in large print): please do not print it again yourself and please do not circulate it outside cam.ac.uk. Note that you will also need a textbook and that the handout is not a substitute for one. Errata corrige If you find any errors in the handout, please email me and I'll credit you here and in the next edition. Page Line Errata Corrige Found on by 12 9 of insertsort len(a)-1 len(a)-2 2009-04-23 author, but also during lecture 1 by an enterprising student in the front row before I had actually published this correction; if you are him, tell me your name and I'll credit you here! 20 7 Θ(n lg n) O(n lg n) 2009-04-27 author 22 22 of binaryInsertSort for j from i to k-1: for j from k-1 to i: 2009-04-28 Rasmus Kyng 23 12 of bubblesort len(a)-1 len(a)-2 2009-04-27 Chloë Brown 23 13 of bubblesort a[k-1] a[k+1] 2009-04-27 Chloë Brown 24 14 of mergesort return a copy of a return a 2009-04-28 Rob Harle 24 26 of mergesort a3[i3] a3[i3++] 2009-04-28 Rob Harle 28 big formula in the middle of the page c() f() (replace all three occurrences) 2009-04-28 author 32 29 to 35 of heapSort listing k i (replace all five occurrences) 2009-04-30 author n/a n/a I wrongly said in lecture 2 that you could stop mergesort early and do a final pass over the quasi-sorted array. This trick won't work with mergesort because at each pass of merge the worst-case distance between the entries and their ideal destination might approximately double. 2009-04-27 another smart student (who?) during lecture 2 © 2009 Computer Laboratory, University of Cambridge Please send any comments on this page to Dr Frank Stajano Last modified 2009-05-02 13:44 by Frank Stajano
