News
■ We are working on a solution to the overlap in time with other courses. Quite likely this will mean that on Mondays (except March 10) we move to AUD 7 & videotape the lecture. For Fridays (and March 10) this was not possible.
Below you can find information on:
lecturer
contents
exam
homework
schedule
Kevin Buchin ( MF 7.39, k.a.buchin@tue.nl )
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 divideandconquer, 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 socalled 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 NPhardness (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 02625330507.
Data structures (2IL05 or 2IL50) is a prerequisite for this course. Thus, you should know the following:
Onotation, Ω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)
Notes:
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.
instructor  room  
group 1  Maximilian Konzack (m.p.konzack@tue.nl)  Matrix 1.43 
group 2  Irina Kostitsyna (i.kostitsyna@tue.nl)  MF 8 
group 3  Marcel Roeloffzen (m.j.m.roeloffzen@tue.nl)  Matrix 1.50 
Grading scheme
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 secondchance 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 secondchance exam (herkansing). If you take the written exam (and similarly for the secondchance 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 PDFformat 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 PDFformat. 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  week  lectures + tutorials  Slides / Homework  
Techniques for Optimization  Feb 3 7  Mon  Lecture 1: Introduction + backtracking.  
Fri  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.  
Fri  Tutorial 1  Homework A.1: pdf and LaTeX source  
Feb 10 14  Mon  Lecture 3: Dynamic programming I. Chapter 15, sections 15.1 + 15.2  
Fri  Lecture 4: Dynamic programming II. Chapter 15, sections 15.3 15.5  
Fri  Tutorial 2  Homework A.2: pdf and LaTeX source and figure clustertree.pdf  
Graph Algorithms  
Feb 17 21  Mon  Lecture 5: SingleSource Shortest paths. Chapter 24, except 24.4.  
Thu  23:59 deadline for Homework Set A (= Homeworks A.1 and A.2)  
Fri  Lecture 6: AllPairs Shortest paths. Chapter 25, except 25.2  
Fri  Tutorial 3: Discussion of solutions to Homework Set A  Homework B.1: pdf and LaTeX source and figure sptree.pdf  
Feb 24 28  Mon  Lecture 7: Max flow (part 1). Chapter 26 until (and excluding) Analysis of FordFulkerson.  
Fri  Lecture 8: Max flow (continued) + Max matching and other applications. Rest of Section 26.2 + section 26.3.  
Fri  Tutorial 4  Homework B.2: pdf and LaTeX source and figures treenetwork.pdf, flownetwork2.pdf, pointassigment.pdf and network1.pdf  
Carnival  March 3 7  no lectures or tutorial  
Selected topics  March 10 14  Mon  12:00 (noon) deadline for Homework Set B (= Homeworks B.1 and B.2)


Mon  Lecture 9: NPcompleteness. 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.]  
Fri  Lecture 10: NPcompleteness, part II. Section 34.5.  
Fri  Tutorial 5: Discussion of solutions to Homework Set B  Homework C.1: pdf and LaTeX source and figures circuit.pdf and rectanglepacking.pdf  
March 17 21  Mon  Lecture 11: Approximation algorithms: Sections 35.1, 35.2, 35.5.  
Fri  Lecture 12: Linear programming: Sections 29.1, 29.2  
Fri  Tutorial 6,  Homework C.2: pdf and LaTeX source  
March 24 28  Mon   (no lecture)  
Thu  23:59 deadline for Homework Set C (= Homeworks C.1 and C.2)  
Fri   (no lecture)  
Fri  
March 31 April 4  Mon  Tutorial 8: tutorial (exam preparation) instead of lecture in AUD 7 (with instructors)  
Fri  wrapup lecture: overview, information about the exam, and more  
Fri  Tutorial 9: exam preparation 