News
■ The first lecture will be on
Tuesday, April 24 (10:4512: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
contents
exam
homework
schedule
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.
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 |
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 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.
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 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.
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.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. |
|||
|
Apr 30 May 4 |
Tue |
Tutorial 2 |
Homework A-1 |
|
|
Wed |
Lecture 3: Dynamic programming I. Chapter 15, sections 15.1 + 15.2 |
|||
|
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 |
|||
|
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. |
||
|
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 |
|||
|
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. |
|||
|
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. |
|||
|
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.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.] |
||
|
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. |
|||
|
June 11 15 |
Tue |
Tutorial 10 |
Homework C.1 |
|
|
Wed |
Lecture 11: Approximation algorithms: Sections 35.1, 35.2, 35.5. |
|||
|
Thu |
Tutorial 11 |
Homework C.2: pdf and LaTeX source |
||
|
Fri |
Lecture 12: Linear programming: Sections 29.1, 29.2 |
|||
|
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 |
|||