# Algorithms (2IL15)  4th Quartile, 2012

News

The first lecture will be on Tuesday, April 24 (10:4512:30 in Pav B2), which is normally a time slot for a tutorial, instead of on Wednesday, April 25. See also the schedule.

Below you can find information on:





















Lecturer

Mark de Berg   ( HG 7.39, mdberg@win.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 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.

Prerequisites

Data structures (2IL05) 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: Wednesday 8:45  10:30  (Aud 4)   +   Friday 13:45  15:30 (Pav B2)

      Tutorials: Tuesday 10:45  12:30 (Pav B2, Aud 11, Aud 12)   +  Thursday 13:45  15:30 (HG 6.09, Laplace -1.19, Matrix 1.60).

Notes:

      The schedule in the first week deviates from the schedule above, since there will be a lecture on Tuesday instead of on Wednesday.

      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.

Groups for tutorials

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 for Tuesday tutorial room for Thursday tutorial group 1 Mark de Berg (mdberg@win.tue.nl) Pav B2 HG 6.09 group 2 Wouter Meulemans (w.meulemans@tue.nl) Aud 11 Laplace -1.19 group 3 Chris Volk (c.volk@tue.nl) Aud 12 Matrix 1.60

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 deadlinessee 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.

Exam

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). Here is the exam from last year, exam d.d. 27/6/2011, as a practice exam.

Homework

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. The exact deadline on the given dates is 23:59 and, as already mentioned, solutions must be emailed to your instructor (see below) in PDF-format.

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.

Schedule

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 Apr 23  27 Tue LECTURE 1 in PAV B2: Introduction + backtracking. Wed --   (the lecture is on Tuesday this week) Thu Tutorial 1 Homework A.1: pdf and LaTeX source Fri Lecture 2: Greedy algorithms.   Chapter 16, Sections 16.116.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. slides Apr 30  May 4 Tue Tutorial 2 Homework A-1 Wed Lecture 3: Dynamic programming I. Chapter 15, sections 15.1 + 15.2 slides Thu Tutorial 3 Homework A.2: pdf and LaTeX source and figure cluster-tree.pdf Fri Lecture 4: Dynamic programming II. Chapter 15, sections 15.3  15.5 slides May 7  11 Tue Tutorial 4 Homework A.2 Wed -- (no lecture)  deadline for Homework Set A (= Homeworks A.1 and A.2) Thu Tutorial: Discussion of solutions to Homework Set A Graph Algorithms Fri Lecture 5: Single-Source Shortest paths. Chapter 24, except 24.4. slides May 14  18 Tue Tutorial 5 Homework B.1: pdf and LaTeX source and figure sp-tree.pdf Wed Lecture 6: All-Pairs Shortest paths. Chapter 25, except 25.2 slides Thu -- (Ascension Day: TU/e closed) Fri -- (TU/e closed) May 21  25 Tue Tutorial 6 Homework B.1 Wed Lecture 7: Max flow (part 1). Chapter 26 until (and excluding) Analysis of Ford-Fulkerson. slides Thu Tutorial 7 Homework B.2: pdf and LaTeX source and figures tree-network.pdf, flow-network2.pdf, point-assigment.pdf and network1.pdf Fri Lecture 8: Max flow (continued) + Max matching and other applications.  Rest of Section 26.2 + section 26.3. slides May 28  June 1 Tue -- (no tutorial) Wed -- (no lecture) Thu Tutorial 8 Homework B.2 Fri -- (no lecture) deadline for Homework Set B (= Homeworks B.1 and B.2) June 4  8 Tue Tutorial: Discussion of Homework Set B Selected topics Wed Lecture 9: NP-completeness. Chapter 34, sections 34.134.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.] slides Thu Tutorial 9 Homework C.1: pdf and LaTeX source and figures circuit.pdf and rectangle-packing.pdf Fri Lecture 10: NP-completeness, part II. Section 34.5. slides June 11  15 Tue Tutorial 10 Homework C.1 Wed Lecture 11: Approximation algorithms: Sections 35.1, 35.2, 35.5. slides Thu Tutorial 11 Homework C.2: pdf and LaTeX source Fri Lecture 12: Linear programming: Sections 29.1, 29.2 slides June 18  22 Tue Tutorial 12 Homework C.2 Wed -- (no lecture) deadline for Homework Set C (= Homeworks C.1 and C.2) Thu Tutorial: Discussion of solutions to Homework Set C Fri wrap-up lecture: overview, information about the exam, and more slides