Below you can find information on:
The efficiency (in terms of speed and memory usage) of software is of crucial importance in many applications. In the course Data structures (2IL05) you have learned how to mathematically analyze efficiency, how to use design techniques like divide-and-conquer, and you have seen efficient algorithms and data structures for basic problems such as sorting and searching. In the course Algorithms we will take this one step further, by studying more advanced design techniques and algorithms, and by studying other aspects of efficiency. Many of the topics that are covered concern optimization problems, where one wants to find not just some solution to a problem but an optimal solution. The course consists of three parts.
Algorithmic techniques for optimization. In this part of the course we study three general techniques for solving optimization problems: backtracking, dynamic programming, and greedy algorithms. Backtracking can be applied to more or less all problems but it generally yields very slow algorithms, a greedy approach can be applied to few problems but it generally gives very fast algorithms, and dynamic programming lies in between.
Graph algorithms. The second part of the course deals with algorithms for optimization problems on graphs: computing shortest paths, computing maximum flows, and finding so-called matchings.
Selected topics. In the third part of the course we study the limitations of traditional algorithm design and analysis. We consider problems for which it seems impossible to design efficient algorithms, introduce the concept of NP-hardness (which formalizes this), and consider approximation algorithms. We introduce linear programming, and see how optimization problems can be formulated as linear programs.
The course is based on the following book, which is the same book as used in the course Data structures :
[CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms (3rd edition), MIT Press, 2009. ISBN 0-262-53305-07.
Data structures (2IL05 or 2IL50) is a prerequisite for this course. Thus, you should know the following:
O-notation, Ω-notation, Θ-notation; how to analyze algorithms
Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc.
Basic data structures: linked lists, stacks, queues
(Balanced) binary search trees
Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort
Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort)
Lectures and tutorials
Lectures: Monday 13:45 15:30 (AUD 7; except March 10: Laplace -1.19) + Friday 8:45 10:30 (MF 7)
Tutorials: Friday 10:45 12:30 (Matrix 1.43, Matrix 1.50, MF 8)
The tutorials are used either for working on and asking questions about the homework exercises, or for discussion of the solutions to the homework exercises. Which tutorial is used for what can be seen in the schedule.
There are several weeks when there are no lectures and/or no tutorials. Please make sure you look at the exact schedule for details.
There are three groups for the small tutorials. In the third week of the course (Feb 14 18) you can register through Studyweb for one of these groups. For each group there is one instructor, as specified in the following table.
Maximilian Konzack (firstname.lastname@example.org)
Irina Kostitsyna (email@example.com)
Marcel Roeloffzen (firstname.lastname@example.org)
The final grade will be based on two items:
Six sets of homework exercises, two for each part of the course. For each set you can get up to 10 points, and out of these six sets, four count for the final grade: the best set for each part, plus the best set of the remaining three sets. (In other words: the best four sets count, under the condition that for each part of the course at least one set counts.) Together you can thus score up to 40 points. The homework sets are grouped into three pairs (A.1 and A.2, B.1 and B.2, C.1 and C.2) and the sets from each pair have to be handed in simultaneously; thus there are only three deadlinessee the schedule for details.
A written exam (closed book) where you can score up to 10 points.
If you score less than 20 points on the homework, then you are not allowed to participate in the written exam nor in the second-chance exam. You will fail the course and your next chance will be next year.
If you score 20 or more points on the homework, you are allowed to do the written exam and, if necessary, do the second-chance exam (herkansing). If you take the written exam (and similarly for the second-chance exam), then the final grade is computed as follows. Define G = ( score for homework + 4 x score for written exam ) / 8. If you score less than 5 points on the final exam, then you will fail the course, regardless of the points you collected with the homework and your final grade is min(5,G); otherwise, the final grade is G.
The date and the location of the exam can be found via OWinfo. The exam is closed book exam: you are not allowed to use any books, notes or other material (including calculators).
Homework exercises should be done individually: you should write the solution by yourself. Solutions must be submitted electronically in PDF-format to your instructor. Handwritten solutions and solutions made in pairs will not be graded and automatically get a score of 0 (zero) points. Do not search the Internet for solutions. Solutions copied from the Internet, or from other students, automatically get 0 points; copying is considered fraud, and students who copy may be reported to the exam committee.
The schedule below shows the deadlines for the various homework sets. You are advised to prepare the solutions using LaTeX: this usually gives much nicer results than Word, especially for mathematical formulas. For describing algorithms you can use the package algo.sty. (Other packages exist as well.) For drawing figures, you can use Ipe, for example. Solutions must be emailed to your instructor (see below) in PDF-format. The exact deadline is stated in the schedule.
Note that during the tutorials you can ask for help on the homeworks. You can even show your solutions (including typeset solutions that you are planning to hand in) to the instructor, who can then have a quick look and give feedback e.g. about the level of detail of your solution, or about whether the general idea of your solution is correct.
Below is the (preliminary) schedule for the course. Please note that the schedule may change during the course. Deadlines are indicated in red. Homework exercises will be posted in due time.
Part of the course
lectures + tutorials
Slides / Homework
Techniques for Optimization
Feb 3 7
Lecture 1: Introduction + backtracking.
Lecture 2: Greedy algorithms. Chapter 16, Sections 16.116.3.
The chapter refers several times to dynamic programming (Chapter 15), which we will discuss later. Upon first reading, you may skip the parts referring to dynamic programming.
Feb 10 14
Lecture 3: Dynamic programming I. Chapter 15, sections 15.1 + 15.2
Lecture 4: Dynamic programming II. Chapter 15, sections 15.3 15.5
Feb 17 21
Lecture 5: Single-Source Shortest paths. Chapter 24, except 24.4.
23:59 deadline for Homework Set A (= Homeworks A.1 and A.2)
Lecture 6: All-Pairs Shortest paths. Chapter 25, except 25.2
Tutorial 3: Discussion of solutions to Homework Set A
Feb 24 28
Lecture 7: Max flow (part 1). Chapter 26 until (and excluding) Analysis of Ford-Fulkerson.
Lecture 8: Max flow (continued) + Max matching and other applications. Rest of Section 26.2 + section 26.3.
March 3 7
no lectures or tutorial
March 10 14
12:00 (noon) deadline for Homework Set B (= Homeworks B.1 and B.2)
Lecture 9: NP-completeness. Chapter 34, sections 34.134.4. [NB The book sometimes contains slightly more details than I expect you to know. Have a look at the slides to see what you should know.]
Lecture 10: NP-completeness, part II. Section 34.5.
Tutorial 5: Discussion of solutions to Homework Set B
March 17 21
Lecture 11: Approximation algorithms: Sections 35.1, 35.2, 35.5.
Lecture 12: Linear programming: Sections 29.1, 29.2
Tutorial 6, group 2+3 will meet in MF8 (no tutorial in Matrix 1.50)
March 24 28
-- (no lecture)
23:59 deadline for Homework Set C (= Homeworks C.1 and C.2)
-- (no lecture)
Tutorial 7: Discussion of solutions to Homework Set C,group 2+3 will meet in MF8 (no tutorial in Matrix 1.50)
March 31 April 4
Tutorial 8: tutorial (exam preparation) instead of lecture in AUD 7 (with instructors)
wrap-up lecture: overview, information about the exam, and more
Tutorial 9: exam preparation