User Tools

Site Tools


2ilc0

This is an old revision of the document!


Algorithms (2ILC0), 2nd Quartile, 2015/2016

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

News

18 April Last-minute update Due to a dental emergency I cannot be present during the exam inspection. You can look at your exams today between 12:00 and 13:00 in MF 4.103, but the tutor present there was not involved with grading the exam and so he cannot answer any questions about the exam. If you want to discuss aspects of your exam with me, email me at b.m.p.jansen@tue.nl to make an appointment. Note that, by the bachelor college regulations, I am not allowed to change your homework grade at this point because it has the status of a midterm evaluation.
14 April The re-take exam has been graded and the scores are available here. The grade for the retake exam replaces the grade for the previous exam. Afterwards, the new final score is calculated as explained below. (This means that your homework grade still affects 50% of the new grade.) You can inspect your exam next Monday (April 18) in my office (MF 4.104A) between 12:00 and 13:00. The scores are posted here unofficially, “for your convenience”; errors made here do not grant you any rights. Only the final grades as they will be registered by the administration are official.
26 Jan The exam has been graded and the scores are available here. The document includes all homework scores and a calculation of your final grade according to the rules explained below. Note that the homework score and exam score are both rounded to 1 decimal before they are combined into your final score which is rounded to the nearest integer; this works in your favor. You still have the opportunity to inspect your exam next Monday. The scores are posted here unofficially, “for your convenience”; errors made here do not grant you any rights. Only the final grades as they will be registered by the administration are official.
21 Jan The exam will be graded next week. Scores for the exam and for A6 will be posted here when we are done. You can inspect your exam, and your grades for assignment A6, on Monday the 1st of February from 12:30 - 13:30 in room MF 6.131
16 Dec By popular request I have decided to extend the deadline for homework assignment 5. The new deadline is Sunday, January the 3rd. However, I recommend that you finish your assignment this week to ensure you have a carefree Christmas vacation. Keep in mind that only your first hand-in will be graded, so double-check your answers before submitting!
14 Dec Changed the runtime bound for A.5-6 (iii) to O(n log n + (n+m) log m).
4 Dec Some students were worried they scored less points than they deserve for Part (v) of Exercise A.2-4, on account of having given pseudocode while you were not asked to give pseudocode. This should not be the case; the only reason for not scoring full points is to have mistakes or unreadable pseudocode. If you believe your solution to part (v) is correct but did not score full points, send an exact PDF copy of your original submission to b.m.p.jansen@tue.nl . As a general guideline, when the exercise does not ask for pseudocode or to make “an algorithm”, this means that you can give a correct answer without resorting to pseudocode and an answer in text is less likely to contain unintentional mistakes.
2 Dec Uploaded PowerPoint versions of all lectures
2 Dec Starting immediately, the Friday room for tutorial group 1 (supervised by Ali & Henk) has been moved from Flux 1.09 to Matrix 1.50. This puts all Friday groups close together in Matrix and makes it easier to ask other instructors for feedback on your graded assignments.
23 Nov Important notice regarding homework assignments. Submit your solutions to the tutor that is responsible for the group that you have been assigned to, not to the student assistant. Submit to the TU/e email address listed below. You should submit exactly once. To enforce this policy, only your first submission is graded; follow-up emails with corrections will be disregarded. You should therefore wait with submitting until you verified that everything is correct. Please include your name, student number, and group number on the first page.
23 Nov Updated text for exercise A2-2 (v) of homework assignment 2
20 Nov Homework assignment 2 posted, see schedule
11 Nov Assignment of students to tutorial groups has been made according to registration during the first lecture, see here. Please attend the tutorial of the group that you have been assigned to, and submit your homework solutions to your group's tutor.
04 Nov First version of the course website

Instructors and contact information

Contents

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.

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

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

Lectures and instructions

The weekly schedule for this course is:

  • Wednesday 5+6 (13:45 - 15:30), lecture in IPO 0.98; except on January 6, when we are in HELIX 1
  • Wednesday 7+8 (15:45 - 17:30), tutorial in AUDITORIUM 1, MATRIX 1.44, and MATRIX 1.60;
  • Friday 1+2 (8:45 - 10:30), tutorial in MATRIX 1.44, MATRIX 1.46, and FLUX 1.09 MATRIX 1.50;
  • Friday 3+4 (10:45 - 12:30), lecture in AUDITORIUM 2.

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. There are three tutorial groups. An assignment of students to group was made during the first lecture. Use this text file to determine what group you are in. Please attend the tutorial of the group that you have been assigned to, and submit your homework solutions to your group's tutor.

The assignment of groups to rooms is as follows:

  • Tutorial group 1 (Ali & Henk): Auditorium 1 on Wednesdays and Flux 1.09 Matrix 1.50 on Fridays
  • Tutorial group 2 (Aleksandar & Jeffrey): Matrix 1.44 on Wednesdays and Matrix 1.44 on Fridays
  • Tutorial group 3 (Max & Jules): Matrix 1.60 on Wednesdays and Matrix 1.46 on Fridays

Grading scheme

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 sets 1-5, and divide the result by 5.

In other words, the worst-scoring homework out of the first 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 assignments

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.

Schedule

Please note the schedule below is tentative and may be adapted during the course.

Date From thru Location Event Topic and material Homework
Wed 11-11 13:45 15:30 IPO 0.98 lecture 1A backtracking handout, slides pdf slides pptx Homework 1 pdf zip The zip file with the LaTeX source also includes a file with the LaTeX source of the pseudocode in the handout.
Wed 11-11 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 no tutorial
Fri 13-11 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 tutorial 1A First half of homework 1 along with all the exercises in the handout
Fri 13-11 10:45 12:30 AUD 2 lecture 1B greedy algorithms slides pdf slides pptx CLRS 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.
Wed 18-11 13:45 15:30 IPO 0.98 no lecture
Wed 18-11 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 tutorial 1B Second half of homework 1, and the practice exercises for lecture 2A
Fri 20-11 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 no tutorial
Fri 20-11 10:45 12:30 AUD 2 lecture 2A dynamic programming I slides pdf slides pptx CLRS Sections 15.1-15.2
Sun 22-11 23:59 By email Deadline homework set 1
Wed 25-11 13:45 15:30 IPO 0.98 lecture 2B dynamic programming IIslides pdf slides pptx CLRS Sections 15.3-15.5 Homework 2 pdf zip
Wed 25-11 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 tutorial 2A First half of homework 2, together with the practice exercises on dynamic programming
Fri 27-11 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 tutorial 2B Second half of homework 2, together with the practice exercises on dynamic programming
Fri 27-11 10:45 12:30 AUD 2 lecture 3A single-source shortest paths slides pdf slides pptx CLRS Chapter 24 (except Section 24.4)
Sun 29-11 23:59 By email Deadline homework set 2
Wed 2-12 13:45 15:30 IPO 0.98 lecture 3B all-pairs shortest paths slides pdf slides pptx CLRS Chapter 25 (except Section 25.2) Homework 3 pdf zip
Wed 2-12 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 tutorial 3A First half of homework 3, together with the practice exercises on shortest paths
Fri 4-12 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 tutorial 3B Second half of homework 3, together with the updated practice exercises on shortest paths
Fri 4-12 10:45 12:30 AUD 2 lecture 4A maximum flow slides pdf slides pptx CLRS Chapter 26 until (and excluding) “Analysis of Ford-Fulkerson”
Sun 6-12 23:59 By email Deadline homework set 3
Wed 9-12 13:45 15:30 IPO 0.98 lecture 4B applications of max flow slides pdf slides pptx CLRS Sections 26.2 and 26.3 Homework 4 pdf zip
Wed 9-12 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 tutorial 4A First half of homework 4
Fri 11-12 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 tutorial 4B Second half of homework 4
Fri 11-12 10:45 12:30 AUD 2 lecture 5A linear programming slides pdf slides pptx CLRS Sections 29.1 and 29.2
Sun 13-12 23:59 By email Deadline homework set 4
Wed 16-12 13:45 15:30 IPO 0.98 surprise lecture by Bas den Heijer @ ORTEC: Engineering Highway Hierarchies slides pptx (highway hierarchies are not part of the exam material) Homework 5 pdf zip
Wed 16-12 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 tutorial 5A First half of homework 5
Fri 18-12 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 review tutorial Second half of homework 5
Fri 18-12 10:45 12:30 AUD 2 overview lecture
Sun 3-1-2016 23:59 By email Deadline homework set 5
Wed 6-1 13:45 15:30 HELIX 1 lecture 6A NP-completeness slides pdf slides pptx CLRS Sections 34.1—34.4 Homework 6 pdf zip
Wed 6-1 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 no tutorial
Fri 8-1 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 tutorial 6A First half of homework 6
Fri 8-1 10:45 12:30 IPO 0.98 lecture 6B NP-completeness slides pdf slides pptx CLRS Sections 34.1—34.4
Wed 13-1 13:45 15:30 IPO 0.98 what is expected on the exam slides pdf slides pptx
Wed 13-1 15:45 17:30 MATRIX 1.44, MATRIX 1.60 AUD 1 tutorial 6B Second half of homework 6
Fri 15-1 08:45 10:30 MATRIX 1.44, MATRIX 1.46, FLUX 1.09 exam practice tutorial
Fri 15-1 10:45 12:30 AUD 2 programming contest puzzles & answering your questions about the exam material puzzles slides pdf puzzles slides pptx follow-up courses slides pdf follow-up courses slides pptx
Sun 17-1 23:59 By email Deadline homework set 6
2ilc0.1460970834.txt.gz · Last modified: 2016/04/18 11:13 by bmpjansen