News
Nov 30: Lecture of December 10 has been canceled θ Work
on experimentation project in the week of December 610.
Below
you can find information on:
lecturer
contents
schedule
Mark de Berg
( HG 7.39, mdberg@win.tue.nl )
This course introduces a number of advanced
algorithmic techniques and concepts. This will on the one hand broaden your
algorithmic knowledge because you will see a number of new concepts, and on the
other hand deepen your understanding because of the more advanced nature of the
topics. The course consists of three parts:
Randomized algorithms. Randomization is a powerful tool in the design of
algorithms. For many algorithmic problems, randomized solutions are simpler
than their deterministic counterparts and, hence, often more efficient in
practice. The first part of Advanced Algorithms teaches you some basic design
and analysis techniques for randomized algorithms.
Approximation algorithms.
For some optimization problems it is possible to compute exact solutions
efficiently. For other problems, however, this is hard and one would like to
compute an approximate solution to the problem at hand. The second part of
Advanced Algorithms focuses on algorithms for doing this.
Geometric
Algorithms. Geometric data play a fundamental role in many
application areas, such as robotics, computer graphics, CAD/CAM, and so on. The
third part of Advanced Algorithms gives a short introduction into the
area of geometric algorithms and data structures. As such it also serves as an
introduction into much of the research performed in the Algorithms Group. An
extensive study of this topic is offered in the course geometric algorithms
(2IL55).
In order to successfully take this course, you should
already have a basic knowledge of algorithms and mathematics. Heres a short
list of what you are supposed to know:
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, shortest
paths)
Dynamic
programming, greedy algorithms
All this can be found in [CLRS].
A basic introduction to probability theory (which nevertheless covers most of
what you need to know about probability theory for this course) can be found here.
Lectures and tutorials
Lectures: Wednesday 8:45
10:30, Laplace 1.19
Tutorials: Friday 10:45
12:30, HG 6.09. During
the tutorials you can ask for extra explanations on the theory, and you can ask
for feedback on the homework exercises you are currently working on. NB: I will
only give feedback on homework exercises if you already spent enough time on
them yourself. In practice this means that I only help you with exercises from
a given week if you can already show me (partial) solutions to most of the
exercises from that week.
Note: there are several weeks when there
are no lectures and/or no tutorials. Please make sure you look at the exact schedule for details.
For most lectures, there will be Course Notes that you can downloadsee the schedule. If you find any
errors, please let me know so I can correct them. Some other lectures
(especially the ones about geometric algorithms) are based on material from the
book:
[BKOS] M. de Berg, O. Cheong, M. van Kreveld, and M.
Overmars. Computational Geometry: Algorithms and Applications (3rd
edition). Springer-Verlag, 2008.
You do not have to buy this book, since we will only
cover a small part of it. However, the book is mandatory for the course geometric
algorithms (2IL20), so if you plan to also take that course you might as
well buy the book now. And it is a very nice book anyway :-)
If you do not want to buy [BKOS]
you will have to make your own notes during these lectures. Alternatively, you
may want to make copies of the relevant chapters for your personal use. (I have
a reader with all the material in my office.)
There will be no written exam.
Instead there will be two types of assignments.
Homework exercises
(3/4 of the final grade). For
each of the three main topics of the course (randomized algorithms,
approximation algorithms, geometric algorithms) there will be a set of homework
exercises. For each set you can score a maximum of 10 points, so you can score
up to 30 points in total for the homework exercises. The homework exercises are
done individually, that is, everyone must hand in her/his own solutions. See
below for more details on the homework exercises.
Experimentation
project (1/4 of the final grade). You also have to do a small
experimentation project, for which you can get a maximum of 10 points. The
experimentation project is done in pairs of students―see below for
details.
Final grade.
1.
You need a minimum score of 17 points on the homework
exercises, and a minimum score of 5.5 points on the implementation project;
otherwise the final grade is FAIL.
2. If
you meet the requirements in 1. then the final grade is given by
( score for
homework + score for experimentation project )
/ 4
where the grade is rounded to the nearest integer (with .5 rounded up.) Note
that this implies that you always pass the course if you meet the requirements
in 1.
If you
fail the course, you can redo the implementation project and/or one or more
sets of homework exercises to replace the set(s) with the lowest score(s) (so
if you scored 4, 5, 7 for the exercises on randomized, approximation and
geometric algorithms, respectively, and you want to redo two sets, then you
should redo randomized algorithms and approximation algorithms).
As mentioned above, these
exercises are done individually: you
should solve them and write the solution by
yourself. Solutions must be printed
and handed in on paper. Handwritten
solutions, solutions that have been emailed, 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.
There will be homework exercises
every weeksee the schedule belowbut you only have to hand them in at the end
of every part of the course. 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.
In the experimentation project
you have to experimentally investigate some randomized algorithms. This is done
in pairs. (You should find your own partner.) Each
pair of students must email me (mdberg@win.tue.nl) their names before September 8. I will then
assign topics. You must write a 10-page paper about your experimental
investigations. In fact, one important goal of the project is to practice
writing a (in this case, experimental) paper.
Here is more information on
the experimentation project.
Here is a document with some advice on writing (algorithmic) papers. (Not all
of it maybe relevant for the paper you have to write on the experimentation
project, but parts of it may also be useful when you are writing your masters
thesis, for example.)
Submission of homework exercises and the paper on the
experimentation project must be done on paper; email submissions are not
accepted. You can give me the paper in the break of the lecture, give it to me
in my office (HG 7.39), or put it in my mailbox which is opposite room HG 7.22.
The same holds for the paper on the experimentation project.
Schedule
Below is the (preliminary) schedule for the course. Please note that the schedule may change during the course.
Days when there are no lectures or tutorials are indicated with light blue shading, deadlines are indicated
in red.
The dates for the tutorials are also indicated. Homework exercises will be
posted in due time.
|
week |
lecture + tutorial |
material |
Homework |
|
Aug 30 Sept 3 |
Sept
1: lecture. Introduction to randomized algorithms |
||
|
Sept
3: no tutorial |
|||
|
Sept 6 10 |
Sept 8: Inform me by email who your partner is for the
experimentation project |
||
|
no lectures and tutorials: work on
homework exercises |
|||
|
Sept 13 17 |
Sept 15: lecture. Selection
and sorting |
||
|
Sept 17: tutorial |
|||
|
Sept 20 24 |
Sept 22: lecture: Randomized
search structures |
||
|
Sept 24: tutorial. |
|||
|
Sept 27 Oct 1 |
Sept
29: lecture. Routing in parallel computers + |
||
|
Oct
1: tutorial |
|||
|
Oct 4 8 |
no lectures and tutorials: finish
homework on randomized algorithms; work on experimentation project |
||
|
Oct 11 15 |
Oct 13: Hand in homework exercises on randomized algorithms |
||
|
Oct 13: lecture. Introduction to
approximation algorithms |
|||
|
Oct 15: tutorial. |
|||
|
Oct 18 22 |
Oct 20: lecture. Approximation via
LP rounding |
||
|
Oct 22: tutorial |
|||
|
Oct 25 29 |
exam period no lectures and
tutorials; work on experimentation project and on homework |
||
|
Nov 1 5 |
exam period no lectures and
tutorials; work on experimentation project and on homework |
||
|
Nov 8 12 |
Nov 10: Hand in preliminary version of paper on
experimentation project |
||
|
Nov 10: lecture.Polynomial-time
approximation schemes |
|||
|
Nov 12: tutorial |
|||
|
Nov 17 19 |
Nov 17: lecture. The travelling
salesman problem. See http://www.tsp.gatech.edu/ for lots of
information on TSP, including the TSP game. |
||
|
Nov 19: tutorial |
|||
|
Nov 22 26 |
no lectures and tutorials: finish
homework on approximation algorithms; work on experimentation project |
||
|
Nov 29 Dec 3 |
Dec 1: Hand in homework exercises on approximation algorithms |
||
|
Dec 1: lecture. Introduction to
geometric algorithms: convex hulls |
[BKOS] Chapter 1 |
||
|
Dec 3: tutorial |
|||
|
Dec 6 10 |
no lectures and tutorials: work on
experimentation project |
||
|
Dec 13 17 |
Dec 15: lecture. Low-dimensional
linear programming |
[BKOS] Sections 4.1, 4.3, 4.4 |
|
|
Dec 17: tutorial |
|||
|
Dec 20 24 |
Christmas holidays no lectures |
||
|
Dec 27 31 |
Christmas holidays no lectures |
||
|
Jan 3 7 |
no lectures and tutorials: work on
homework on geometric algorithms and on experimentation project |
||
|
Jan 10 14 |
Jan 12: lecture. Binary space
partitions |
[BKOS] Sec 12.112.4 |
Homework: pdf, LaTeX, figure: segments.pdf |
|
Jan 14: tutorial |
|||
|
Jan 26 |
Hand in homework exercises on geometric algorithms |
||
|
Jan 31 |
Hand in final version of paper on experimentation project |
||