Pierre Flener
The main objective is to make you familiar with some fundamental principles and methodologies of algorithm and data-structure design and evaluation. We will use the functional programming language Standard ML (SML) as the teaching medium. You will learn when to use each discussed algorithm and data structure, when not to, and what to consider when designing or choosing an algorithm or data structure. The lectures are in English, by the instructor, and have a slight theoretical flavour, but with many examples. Also see the popular-science description of this course.More practice of algorithm and data-structure design (via programming in SML) is acquired through assignments. Several assignments are to be prepared at home, then tried on the computer in labs under assistant supervision, then submitted, and finally graded, but also discussed in lessons by the assistants.
The following two textbooks were used:CLRS could be replaced by the following textbook:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (second edition) (errata). The MIT Press, 2001. (called CLRS below)
- Michael R. Hansen and Hans Rischel. Introduction to Programming using SML (errata). Addison-Wesley, 1999. (called HR below)
- Anany Levitin. Introduction to the Design & Analysis of Algorithms. Addison-Wesley, 2003. (called L below)
- Introduction & Revision
(read Chapter 1 of CLRS; also revise Chapters 1-9, 17, and 18 of HR)- Algorithm Analysis 1
(read Chapter 3 of CLRS; you may skip everything about little-oh and little-omega)- Algorithm Analysis 2 & Sorting
(read Chapters 2, 4, and 7 as well as pages 123-126 of CLRS; you may skip everything about invariants as well as Sections 4.4 and 7.3)- Stacks and Queues
(read pages 197-199 and Section 10.1 of CLRS)- Trees
(read Sections B.5 and 10.4, as well as Chapter 12 of CLRS; you may skip Section 12.4; AVL trees are not covered in CLRS, but in Section 6.3 of L; also revise Chapter 8 of HR)- Heaps
(read Chapters 6 and 19 of CLRS; you may skip Section 6.4; binomial heaps are not covered in L)- Hashing
(read Chapter 11 of CLRS and self-study Section 11.4; you may skip Sections 11.3.3 and 11.5)- Greedy Algorithms
(read page 370 as well as Sections 16.2 and 16.3 of CLRS; you may skip the proof and everything about dynamic programming)- Graphs
(read Section B.4, pages 525-526 and 580-587, as well as Sections 22.1, 22.2, and 24.3 of CLRS)- Constraint Processing
(this material is not covered in any of the textbooks)- Conclusion
(this material is not covered in any of the textbooks)
Assignment archive of previous academic years:
Exams from previous academic years are archived at the AD1 course instance of 2008. There are no solutions in distributable form for these exams.