Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
Frank Mousset, Felix Weissenberger
Thursday, 14-16 in CAB G52. (First tutorial on 18. 09. 2014)
The goal of this course is to apply the algorithmic knowledge gained in the first few years of the computer science curriculum by solving programming exercises similar to those of the ACM Programming Contests (see SPOJ online judge for example)
Each week a number of exercises (typically 3-4) will be posted on the course website. They have to be solved with a C++ program and submitted to an online judging system which will check the correctness and efficiency of the used algorithms. Solving the exercises is not compulsory, but highly recommended as the final exam will be similar to them.
Each week there will be a tutorial session during which some of the algorithmic concepts are revised and the exercises of the previous week are briefly discussed. Algorithmic concepts which are covered include: arithmetic operations on large integers, general algorithm strategies (greedy, divide & conquer, dynamic programming), basic graph algorithms (traversals, shortest path, minimum spanning tree, etc.), basic geometric algorithms (convex hull). Weeks 4, 8 and 12 are reserved for the Question & Answer session (i.e. a more detailed discussion) about the previous problems.
The final exam (6 hours) will take place during the exam session in a computer lab. The problems posed during this exam will be similar to the exercises during the semester and will be checked by the same online judging system. No documentation is allowed during th e exam except for the C++ STL documentation that is provided by the system itself.
4 Credits. Depending on the level of algorithmic and C++ knowledge we expect that the exercises for each week can be solved in 6-10 hours.
We expect a working knowledge of basic algorithms for e.g. shortest path, minimum weight spanning tree, dynamic programming etc as obtained in the lectures of the first year in computer science, in particular "Algorithmen und Datenstrukturen".
Programming knowledge (in particular in C++) is an advantage. The exercises don't require the use of advanced language features and the focus is on the algorithms. Students with no C/C++ experience should however be aware that this is not a programming course for C++ and that the language has to be learned separately.
The submission system can be found at: https://elabs.inf.ethz.ch.
The required Enrollment-Key will be handed out during the first tutorial of the semester.
The course material will be provided on https://elabs.inf.ethz.ch.
As a preparation for this course we suggest trying to solve the exercise Prime numbers. The exercise is relatively simple and should demonstrate the format of this course and the final exam.
TopCoder - format of the judge is a bit different than the one used in the course, but nonetheless contains a lot of very nice problems