Course Description: There are many aspects to the study of data structures, and the algorithms that operate upon them. In this course, you will learn the basic skills and knowledge to develop efficient algorithms to solve computational problems and to make informed choices between different solutions for the same problem.

Prerequisites: Being able to work with basic programming constructs such as linked lists, arrays, loops ... Being able to apply standard proving techniques such as proof by induction, proof by contradiction ... Being familiar with sums and logarithms such as discussed in Chapter 3 and Appendix A of the textbook.

Format:

The course 2IL05 has three different components.

1. Lectures
2. Labs During the labs you have the opportunity to work on this week's home work assignment. One or two of the instructors will be present to answer questions.
3. Tutorials During these tutorials the instructors will explain the solutions to the homework assignments of the previous week and answer any questions that arise.

1. 6 homework assignments, the best 5 of which each count for 10% of the final grade.
2. A written exam (closed book) which counts for the remaining 50% of the final grade.

If you reach less than 50% of the possible points on the homework assignments, then you are not allowed to participate in the final exam nor in the second chance exam. You will fail the course and your next chance will be next year. If you reach less than 50% of the points on the final exam, then you will fail the course, regardless of the points you collected with the homework assignments. Your grade will be the minimum of 5 and the grade you achieved. However, you are allowed to participate in the second chance exam. The grade of the second chance exam replaces the grade for the first exam, that is, your homework assignments always count for 50% of your grade.

	LaTeX is a document typesetting software package that is widely used by mathematicians, (computer) scientists, and many others that need to typeset technical writing. This article on Wikipedia gives you some background and history.
	Our department has a MiKTeX (LaTeX for Windows) distribution that comes with a nice editing environment. Check this web-page for details and install from \\webmath1\MiKTeX29 (make sure to be logged on to the TU/e network for this to work).
	To get started with latex, read the "Not so short introduction ..." or check out this Wikibook.
	I highly recommend the (free!) drawing editor Ipe to draw figures for the inclusion in Latex documents.

Academic Dishonesty: All class work has to be done independently. You are of course allowed to discuss the material presented in class, homework assignments, or general solution strategies with me or your classmates, but you have to formulate and write up your solutions by yourself. You must not copy from the internet, your friends, or other textbooks. Problem solving is an important component of this course so it is really in your best interest to try and solve all problems by yourself. If you represent other people's work as your own then that constitutes fraud and will be dealt with accordingly.

Schedule:

	Lecture				Labs	Assignments
Week	Date	Topic	Slides	Material		Due
6	07-02-2012	Introduction.		Chapters 1 and 2.	GZ+KB	12-02-2012	A1	A1
	09-02-2012	Analysis of algorithms.		Chapters 2, 3, and 4.	KD+MB
7	14-02-2012	Heaps.		Chapter 6.	KV+MR	19-02-2012
	16-02-2012	No lecture, extra lab instead.			GZ, MB+KD
8	Carneval
9	28-02-2012	Sorting in linear time.		Chapter 8.		04-03-2012
	01-03-2012	QuickSort and selection.		Chapters 7 and 9.
10	06-03-2012	Hash tables.		Chapter 11.		11-03-2012
	08-03-2012	Binary search trees.		Chapter 12 and 13.
11	13-03-2012	Augmenting data structures.		Chapter 13 and 14.		25-03-2012
	15-03-2012	Range searching.		Computational Geometry: Algorithms and Applications, Chapter 5.
12	No lectures, labs, or tutorials.
13	27-03-2012	Elementary graph algorithms.		Chapter 22.		01-04-2012
	29-03-2012	Minimum spanning trees.		Chapter 23.
14	03-04-2012	Recap		"things you should know for the exam"

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein.
Introduction to Algorithms (3rd edition)
MIT Press, 2009.
ISBN 0-262-53305-7 (paperback)

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars.
Computational Geometry: Algorithms and Applications (3rd edition).
Springer-Verlag, 2008.

SpringerLink online version