2ilc0

**This is an old revision of the document!**

This is the course website for the Algorithms course 2ILC0.

9 Nov | First version of the 2016-2017 website online. |
---|

- Bart M. P. Jansen, MF 4.099, b.m.p.jansen@tue.nl, lecturer
- Aleksandar Markovic, MF 4.100, a.markovic@tue.nl, tutor
- Mehran Mehr, MF 4.100, m.mehr@tue.nl, tutor
- Astrid Pieterse, MF 4.100, a.pieterse@tue.nl, tutor
- Olav Bunte o.bunte@student.tue.nl, student assistant
- Jari de Kroon j.j.h.d.kroon@student.tue.nl, student assistant
- Martijn Struijs m.a.c.struijs@student.tue.nl
- Bart van der Vecht b.v.d.vecht@student.tue.nl
- Wouter Verlaek w.m.w.r.verlaek@student.tue.nl, student assistant

The efficiency of algorithms is of crucial importance in many applications. In the course Data Structures 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 and introduce the concept of NP-hardness (which formalizes this). 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.

In order to take this course, you must have completed and passed Data Structures (2IL50 or 2IL05). 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, heaps;
- (Balanced) binary search trees;
- Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort;
- Graph terminology, representations of graphs (adjacency lists and adjacency matrix), and basic graph algorithms (BFS, DFS, topological sort).

The weekly schedule for this course is:

- Wednesday 5+6 (13:45 - 15:30), tutorial in FLUX 1.05, FLUX 1.09, METAFORUM 13, METAFORUM 15
- Wednesday 7+8 (15:45 - 17:30), lecture in Paviljoen U46
- Friday 1+2 (8:45 - 10:30), tutorial in MATRIX 1.50, METAFORUM 14, METAFORUM 13, METAFORUM 15
- Friday 3+4 (10:45 - 12:30), lecture in Paviljoen B2

During the lectures hours, the basic theory will be taught and plenary feedback on the homework exercises may be given.

The tutorial hours are used either for working on and asking questions about the homework assignments, for discussion of the solutions to the homework exercises, and for individual feedback. Tutorial groups will be made during the first week of classes.

The assignment of groups to rooms is as follows:

- Tutorial group 1 (Aleks & ?): MF 15 on Wednesdays and MF 15 on Fridays
- Tutorial group 2 (Astrid & ?): Flux 1.09 on Wednesdays and MF 14 on Fridays
- Tutorial group 3 (Mehran & ?): Flux 1.05 on Wednesdays and MATRIX 1.50 on Fridays
- Tutorial group 4 (? & ?): MF 13 on Wednesdays and MF 13 on Fridays

The final grade will be based on two components: homework exercises and an exam.

There are six sets of homework exercises. The deadlines for these homework sets can be found in the schedule. For each set you can get up to 10 points. Your final score for the homework assignment is calculated as follows:

- take the sum of the 6 homework scores, subtract the lowest score among the 5 sets that do not deal with NP-completeness, and divide the result by 5.

In other words, the grade for the set on NP-completeness always counts, but the worst-scoring grade for the remaining 5 sets does not count.

On the exam you can score up to 10 points.

The final grade is determined as follows:

- If your exam grade is at least 5.0, your final grade is the rounded average of your homework grade and your exam grade. In other words: if your exam grade is at least 5.0, you pass if your homework grade is at least 11 minus your exam grade.
- If your exam grade is less than 5.0, your final grade is the minimum of a 5 and the rounded average of your homework grade and your exam grade. Therefore, if your exam grade is less than 5.0, you fail the course in any case.

Homework exercises must be done individually, that is, you must write the solution by yourself. 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.

You are advised to prepare the solutions using LaTeX: this usually gives much nicer results than Word, especially for mathematical formulas. Some information about LaTeX can be found on the course website of Data Structures. For describing algorithms you can use the package algo, algorithm2e, or clrscode3e (other packages exist as well). For drawing figures, you can use Ipe or yEd Graph Editor, for example.

In 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), and ask for feedback e.g. about the level of detail of your solution, or about whether the general idea of your solution is correct.

The schedule below is tentative and may be adapted during the course. Note that, for your convenience, the dates are not completely in chronological order: the deadline for the homework is listed after the last tutorial dedicated to that homework.

Date | From | thru | Location | Event | Topic and material | Homework |
---|---|---|---|---|---|---|

wed 16-11-2016 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | no tutorial | Homework set 1 | |

wed 16-11-2016 | 15:45 | 17:30 | PAVILJOEN U46 | Lecture 1A: Backtracking | handout, slides | |

fri 18-11-2016 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | Tutorial 1A | ||

fri 18-11-2016 | 10:45 | 12:30 | PAVILJOEN B2 | Lecture 1B: Greedy algorithms | CLRS Sections 16.1-16.3 | |

wed 23-11-2016 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | Tutorial 1B | ||

thu 24-11-2016 | 17:59 | Deadline homework set 1 | ||||

wed 23-11-2016 | 15:45 | 17:30 | PAVILJOEN U46 | Lecture 2A: Dynamic Programming I | CLRS Sections 15.1-15.2 | Homework set 2 |

fri 25-11-2016 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | Tutorial 2A: Dynamic Programming | ||

fri 25-11-2016 | 10:45 | 12:30 | PAVILJOEN B2 | Lecture 2B: Dynamic Programming II | CLRS Sections 15.3-15.5 | |

wed 30-11-2016 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | Tutorial 2B: Dynamic programming | ||

thu 1-12-2016 | 17:59 | Deadline homework set 2 | ||||

wed 30-11-2016 | 15:45 | 17:30 | PAVILJOEN U46 | Lecture 3A: Single-source shortest paths | CLRS Chapter 24 (except Section 24.4) | Homework set 3 |

fri 2-12-2016 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | Tutorial 3A: Shortest paths | ||

fri 2-12-2016 | 10:45 | 12:30 | PAVILJOEN B2 | Lecture 3B: All-pairs shortest paths | CLRS Chapter 25 (except Section 25.2) | |

wed 7-12-2016 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | Tutorial 3B: Shortest paths | ||

thu 8-12-2016 | 17:59 | Deadline homework set 3 | ||||

wed 7-12-2016 | 15:45 | 17:30 | PAVILJOEN U46 | no lecture | Homework set 4 | |

fri 9-12-2016 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | tutorial 4A | ||

fri 9-12-2016 | 10:45 | 12:30 | PAVILJOEN B2 | Invited guest lecture: Bas den Heijer @ ORTEC | ||

wed 14-12-2016 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | tutorial 4B | ||

thu 15-12-2016 | 17:59 | Deadline homework set 4 | ||||

wed 14-12-2016 | 15:45 | 17:30 | PAVILJOEN U46 | Lecture 5A: Flows | CLRS Chapter 26 until (and excluding) “Analysis of Ford-Fulkerson” | Homework set 5 |

fri 16-12-2016 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | Tutorial 5A: Flows | ||

fri 16-12-2016 | 10:45 | 12:30 | PAVILJOEN B2 | Lecture 5B: Applications of flows | CLRS Sections 26.2 and 26.3 | |

wed 21-12-2016 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | Tutorial 5B: Application of flows | ||

thu 22-12-2016 | 17:59 | Deadline homework set 5 | ||||

wed 21-12-2016 | 15:45 | 17:30 | PAVILJOEN U46 | Lecture 6A: NP-completeness I | CLRS Sections 34.1—34.4 | Homework set 6 |

fri 23-12-2016 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | Tutorial 6A: NP-completeness | ||

fri 23-12-2016 | 10:45 | 12:30 | PAVILJOEN B2 | Lecture 6B: NP-completeness II | CLRS Sections 34.1—34.4 | |

wed 11-1-2017 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | Tutorial 6B: NP-completeness | ||

thu 12-1-2017 | 17:59 | Deadline homework set 6 | ||||

wed 11-1-2017 | 15:45 | 17:30 | PAVILJOEN U46 | Lecture 7: To be determined | Exam practice | |

fri 13-1-2017 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | Tutorial: exam practice | ||

fri 13-1-2017 | 10:45 | 12:30 | PAVILJOEN B2 | Surprise lecture | ||

wed 18-1-2017 | 13:45 | 15:30 | FLUX 1.05, FLUX 1.09, MF 13, MF 15 | Tutorial: exam practice | ||

wed 18-1-2017 | 15:45 | 17:30 | PAVILJOEN U46 | no lecture | ||

fri 20-1-2017 | 08:45 | 10:30 | MATRIX 1.50, MF 13, MF 14, MF 15 | no tutorial | ||

fri 20-1-2017 | 10:45 | 12:30 | PAVILJOEN B2 | Lecture: What you should know on the exam | ||

2ilc0.1478772553.txt.gz · Last modified: 2016/11/10 11:09 by bmpjansen