- Acquired an in-depth understanding of a variety of algorithms

- Mastered practical programming skills

- Obtained a useful personal code library

- Gained experience at presenting ideas and solutions

We will be using an automated judging software for the midterms and homework. Students will submit their problem solutions to the judge and automatically receive feedback as to the correctness and efficiency of their source code.

A similar automated judge, along with a large problem archive of over 1000 problems, is available on the University of Valladolid (Spain) website at http://acm.uva.es/p. This on-line judge can be used for practices, as well as a resource for coming up with homework problems.

The textbook is available in the bookstore and is the course textbook used in CPSC320 and CPSC420. Either of the two editions will be sufficient.

Students presenting topics will also be expected to provide small amounts of notes and sample code.

The midterms will have two phases: an in-class phase and a take home phase. The in-class phase of the midterm will be just like any ordinary computer science midterms. A series of questions will be posed, and students will need to provide possible solutions on paper (i.e. descriptions, picking algorithms). Students are highly encouraged to use pseudo code.

The take home phase will be just like the an ordinary homework. Students will need to implement solutions to some or all of the midterm questions, and submit it through the on-line judge. No collaboration is allowed for the midterm. Note that the in-class phase will have more weight.

There will be a problem set assigned for each topic, by the presenting student group. Homeworks are not intended to be time consuming; instead, they should be fairly succinct (in terms of length of solution code), and illustrate the topic at hand.

The presenters should come up with 2 to 4 homework problems that will illustrate the topic presented. A mix of "easy" problems (that uses the topic idea in a straightforward manner) and "smart" problems (that require a thorough understanding of the algorithms) is recommended.

For the rest of the class, we will be submitting our solutions to the online judge system. The system will tell us whether our code solves the problem correctly under the time limit. We can submit as many times as we want before the deadline to get it right. Late homework submissions are not accepted. Comments are not required for correct solutions, but will help earn part marks if we couldn't get the question completely.

• Dynamic Programming (backpacking, coin changing, etc)
• Brute Force Methods (backtracking, branch and bound, iterative deepening, bidirectional search)
• Graphs: Flow and Matching
• Graphs: Shortest Paths (single source, all pairs, negative weight cycle detection)
• Number Theory (GCD, modular arithmetic, fast powers, encryption)
• Computational Geometry (convex hull, line intersection)

• Background information and history (optional, but fun)
• Theory behind the algorithms (why it works, how fast it works, when does it work, etc)
• Sample code
• Sample problem that illustrate how the algorithm and the code provided may be used
• 2 - 4 homework problems for the class to try out
• Solutions to those homework problems to be presented later

Note that these materials should be ready one to two weeks before the presentation date, so that the coordinators can make sure the amount of content is appropriate and that there are no mistakes in the notes and homework.