Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

ACM Lab

Lecturer:

Angelika Steger

Assistants:

Frank Mousset, Felix Weissenberger

Time and Place:

Thursday, 14-16 in CAB G52. (First tutorial on 17. 09. 2015)

Contents:

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: general algorithm strategies (complete search, greedy, divide & conquer, dynamic programming), basic graph algorithms (traversals, minimum spanning tree, etc.), basic geometric algorithms (convex hull).

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.

Workload/Credits:

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.

Prerequisites:

Programming knowledge (in particular in C++) is an advantage. Students with no C/C++ experience should be aware that this is not a programming course for C++ and that the language has to be learned separately. Note that the exercises don't require the use of advanced language features and the focus is on the algorithms.

Submitting your solutions:

The submission system can be found at: https://moodle-app2.let.ethz.ch.

The required Enrollment key will be handed out during the first tutorial of the semester. If you miss this tutorial, contact the assistants of the course.

Course material:

The course material will be provided on https://moodle-app2.let.ethz.ch.

Literature:

T. Cormen, C. Leiserson, R. Rivest, C. Stein
Introduction to Algorithms, MIT Press, Third Edition, 2009 (or any other edition)
R. Sedgewick:
Algorithms in C++: Graph Algorithms, Addison-Wesley, 2001
S. Skiena, M. Revilla:
Programming Challenges, Springer, 2003
A. S. Arefin:
Art of Programming Contest, Gyankosh Prokashoni, 2006, Download

Additional exercises:

SPOJ online judge

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