Related sites: Algorithms Group               Algorithms (2IL15)     OWInfo    Contact Herman Haverkort

		Introduction    Organisation    Schedule    Literature    Prerequisites

Lecturers: Herman Haverkort and Elena Mumford (office: HG 7.35, tel. 8363) Course dates: spring 2010 (quartile 3 and 4) Herman Haverkort is on vacation until the end of January. Please direct any questions about this course to Elena Mumford. To take this course, register on StudyWeb no later than 2 February! See below for details. Introduction Contents In many applications fast software is essential. Often this means that we need not only fast computers and good compilers, but also fast algorithms -- especially when we want to compute the optimal solution for a problem that has many possible (but not equally good) solutions. Examples are packing problems, scheduling problems, and shortest path computations. In this course we discuss several general techniques to solve this type of problems. We will also explore the boundaries: when are the standard techniques not satisfactory, in theory and in practice, and what alternatives do we have? Branch-and-bound, dynamic programming, greedy algorithms, approximation algorithms, randomized algorithms, I/O-efficiency and NP-completeness (P = NP?) will be the topics of this course. Goals The students learn to use standard techniques for optimisation problems, and learn about computational complexity theory and some advanced approaches to algorithm design. Follow-up courses This algorithms course provides you with the skills and knowledge needed for the algorithms courses in the Master programme Computer Science and Engineering: I/O-efficient algorithms (2IL35) Advanced Algorithms (2IL45) Geometric algorithms (2IL55) Seminar Algorithms / Graph Drawing (2IL95) If you are a BSc student and want to do a Master Computer Science and Engineering, you will need to complete Algorithms (2IL15) before you can take any of the courses mentioned above. Organisation Registration Registration for this course is done in two phases: You need to register for this course on StudyWeb no later than 2 February (registration is now open!) After that, you will need to register for a tutorial group. Registration for the tutorial groups opens when registration for the course closes. You will get a reminder by mail when it is time to register for a tutorial group. Form The course is given in the form of homework assignments and three types of meetings: lectures, once or twice a week; tutorials and office hours to help you with making the homework assignments; tutorials during which the instructors return the graded homework assignments to the students, explain the solutions, and answer any questions that arise. The course is taught in English. The homework assignments have to be typeset in English and handed in as a PDF file by e-mail to your instructor. No handwritten solutions and no other file formats will be accepted. We recommend LaTeX for typesetting (see the Data Structures (2IL05) course website for more information). If you have not typeset algorithms or produced PDF files before, then make sure you reserve plenty of time for making the first assignment, or make sure you get some practice before the course starts. The homework assignments have to be handed in at regular intervals throughout the semester (more or less every two weeks, a detailed schedule will be announced later). Each of them will be available at least ten working days before the deadline. No late assignments will be accepted in any circumstances whatsoever. To give you ample opportunities to catch up if there any circumstances that keep you from making homework for a while, we will provide 9 assignments while we only count the best 7. Assignments have to be completed by each student separately. Examination The final grade for the course will be based on the homework assignments and on a written exam. To pass the course, you need: a score of at least 70 points on your best 7 homework assignments (you can get at most 20 points for each assignment; note that homework assignments from 2008 or 2009 do not count); a score of at least 50% on the final exam; a total score of at least 55% (where each of your best 7 homework assignments counts for 1/14 of the grade, and the final exam counts for 1/2). You will be admitted to the final exam if and only if you meet the first criterion for passing, that is, if you get at least 70 points on your best 7 homework assignments. You cannot take the course material, books, home-made abstracts or calculators etc. to the exam. The exam questions will be in English, but you can answer in English or Dutch as you please. If you miss or fail the final exam, there will be a second chance later. For the second chance the same rules apply: the original homework assignments still count (no replacements will be offered for those) and you can only take the exam if you scored at least 70 points on your best 7 homework assignments. Schedule The exact class dates and times are not yet known at the time of editing this web page. OWInfo might have more information. A more precise schedule will be included in this web page in the week before the course starts. Literature [CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms (2nd edition), MIT Press, 2001, ISBN 0-262-53196-8, or the 3rd edition, 2009, ISBN 0-262-53305-7. Can be obtained through GEWIS. This is the same book as for Data Structures (2IL05), Ontwerp van Algoritmen 2 (2IA20) (sinds 2005) and Ontwerp van algoritmen 3 (2IA30). There is a website with errata for this book on www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php or www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-3e.php, respectively. Lecture notes covering some topics that are not treated in the book mentioned above. These lecture notes will be made available on this website as the course progresses. Required prior knowledge This course builds heavily on the material of Data Structures (2IL05). In practice, this led to the following results in 2008: 16 students registered for Algorithms after completing Data Structures with a 7 or more. All of them passed the first exam of Algorithms. 12 students registered for Algorithms after completing Data Structures with a 6. Of those 12 students, 5 students passed Algorithms, 2 students did all the homework assignments and both exams but still failed, 5 students dropped the course for various reasons. 26 students registered for Algorithms without succesfully completing Data Structures first. Only 5 of them (23%) passed. Ontwerp van Algoritmen 2 does not provide all required prior knowledge! To complete the Algorithms course you need knowledge of graph algorithms which are now taught in Data Structures (2IL05) but were not taught in Ontwerp van Algoritmen 2. If you want to complete Algorithms with only Ontwerp van Algoritmen 2 as prior knowledge, you need to make sure to catch up on the missing parts yourself.

OWInfo    Contact Herman Haverkort