Computer Laboratory – Course material 2009–10: Algorithms I Skip over navigation | Access key help ||| Computer Laboratory Course material 2009–10 Computer Laboratory > Teaching > Course material 2009–10 > Algorithms I Additional Topics Advanced Category Theory in Computer Science Advanced Computer Design Advanced Graphics Advanced Systems Topics Advanced Topics in Computer Systems Advanced Topics in Concurrency Advanced Topics in Programming Languages Algorithms I Information for supervisors Algorithms II An Algebraic Approach to Internet Routing Artificial Intelligence I Artificial Intelligence II Automated Reasoning Basic Rewriting Theory Bioinformatics Building an Internet Router » Business Studies Categorical Logic Category Theory for Computer Science Chip Multiprocessors Comparative Architectures Compiler Construction Complexity Theory Computation Theory Computer Design Computer Graphics and Image Processing Computer Vision Concepts in Programming Languages Concurrent and Distributed Systems 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 Labs » Computer Laboratory – Course material 2009–10: Economics and Law Floating-Point Computation Foundations of Computer Science Further Java Group Project Group Project Briefing Hardware Practical Classes How to Study Computer Science Human-Computer Interaction Information Retrieval Information Theory and Coding Innovative user interfaces Interactive Formal Verification Introduction to Security Introductory Logic Logic and Proof Low Power Embedded Systems Programming Mathematical Methods for Computer Science Natural Language Processing Network Architecture Object-Oriented Programming Operating Systems Optimising Compilers Part IB Assessed Exercise Briefing Probability Professional Practice and Ethics Programming in C and C++ Programming in Java Prolog Quantum Computing Registration Regular Languages and Finite Automata Research Methods » Current Research Topics Security Semantics of HOT Languages Semantics of Programming Languages Set Theory for Computer Science Software Design Software Engineering Software Verification Specification and Verification I Specification and Verification II System on Chip Design and Modelling System-on-Chip Design and Modelling (Part II) Topics in Concurrency Topics in Logic and Complexity Topics in Security: Forensic Signal Analysis Types Unix Tools Algorithms I 2009–10 Principal lecturer: Dr Robert Harle Taken by: Part IA CST, Part IA NST, Part I PPS Syllabus Past exam questions: Algorithms I, Algorithms Information for supervisors (contact lecturer for access permission) Course Overview This course is intended to expose IA students to the basics of algorithms. It does so by: analysing a range of sorting algorithms; introducing established algorithm strategies (divide and conquer, etc); introducing and analysing a series of data structures from stacks to red-black trees Course Notes The course handout was written by Dr Frank Stajano and is an excellent document around which to base your studies. It is itself based on the course textbook Introduction to Algorithms by Cormen. et al. You can download the PDF here. Although the notes are excellent, they are not my preferred format for lecture presentation. Consequently I use a set of slides that I annotate during lectures. These you can download here (including annotations): Lecture 1 (Intro, asymptotic analysis, assertions, insertion sort) Lecture 2 (Insertion, selection, bubble, binary insertion and mergesort algorithms and analysis) Lecture 3 (Quicksort) Lecture 4 (Quickselect, Heapsort, Distribution Sort) Lecture 5 (Algorithm design) Lecture 6 (Elementary data structures) Lecture 7 (Basics of Binary Search Trees) Lecture 8 (Red-Black Trees) Lecture 9 (AVL Trees, B-Trees) [Corrected after lecture] Lecture 10 (Hash Tables) Lecture 10 (Prioriry Queues and Binomial Heaps) Lecture 12 The course material was covered in the first 11 lectures, so there is no twelth lecture per-se. However, I will turn up on wednesday at 10am and students are free to come and ask questions or have me go over parts of the course if they wish. Examples Sheet The lecture notes contain a series of exercises meant primarily to focus and challenge the reader as they go. They are not intended for supervisions per se, although a subset are certainly appropriate. To help guide supervisions, I have produced an examples sheet that picks out some of the exercises from the notes and supplements them with some others I dreamed up. This sheet was updated as the course went on and the (hopefully) final version is here: download the examples sheet In addition, you should have no difficulty in finding other exercises in the textbook or others like it. Sorting Competition Many congratulations to all who entered. The results were very impressive - almost everyone's algorithm beat the native Java sort method on at least one aspect! © 2010 Computer Laboratory, University of Cambridge Please send any comments on this page to Dr Robert Harle Last modified 2010-05-21 23:14 by Robert Harle
