# Algorithms (2IL15)  2014

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 & video-tape the lecture. For Fridays (and March 10) this was not possible.

Below you can find information on:





















Lecturer

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

Literature

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 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)

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.

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

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

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

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 Feb 3  7 Mon Lecture 1: Introduction + backtracking. 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. 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 cluster-tree.pdf Graph Algorithms Feb 17  21 Mon Lecture 5: Single-Source Shortest paths. Chapter 24, except 24.4. Thu 23:59 deadline for Homework Set A (= Homeworks A.1 and A.2) Fri Lecture 6: All-Pairs 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 sp-tree.pdf Feb 24  28 Mon Lecture 7: Max flow (part 1). Chapter 26 until (and excluding) Analysis of Ford-Fulkerson. 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 tree-network.pdf, flow-network2.pdf, point-assigment.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: 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.] Fri Lecture 10: NP-completeness, 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 rectangle-packing.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, group 2+3 will meet in MF8 (no tutorial in Matrix 1.50) 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 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 Mon Tutorial 8: tutorial (exam preparation) instead of lecture in AUD 7 (with instructors) Fri wrap-up lecture: overview, information about the exam, and more Fri Tutorial 9: exam preparation