|
|||||||||||||||||||||||||||
|
|||||||
|
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.
IntroductionContentsIn 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. GoalsThe students learn to use standard techniques for optimisation problems, and learn about computational complexity theory and some advanced approaches to algorithm design.Follow-up coursesThis algorithms course provides you with the skills and knowledge needed for the algorithms courses in the Master programme Computer Science and Engineering:
OrganisationRegistrationRegistration for this course is done in two phases:
FormThe course is given in the form of homework assignments and three types of meetings:
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. ExaminationThe final grade for the course will be based on the homework assignments and on a written exam. To pass the course, you need:
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. ScheduleThe 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
Required prior knowledgeThis course builds heavily on the material of Data Structures (2IL05). In practice, this led to the following results in 2008:
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. |
|
||||||||||||||||