Description
Programming Challenges studies algorithms from comprehension to implementation using programming contests. Topics covered will include:
- parsing and formatting text,
- mathematics,
- data structures,
- graph algorithms,
- dynamic programming, and
- computational geometry.
Evaluation is based on participation in programming contests inside and outside of class and class presentations of selected solutions.
Who should take this course
Students who would like to develop their programming and algorithmic skills by having a new set of programming challenges presented to them in each class.
Expectations
Students can expect to be challenged and practice understanding and implementing algorithmic ideas outside their skillset. Each class, a new set of problems will be presented to the students and they will be asked to solve the problems. The problems will then be discussed as a class, and each student is expected to contribute to the discussions.
Date, time, location
Tuesdays and Thursdays, 1:30PM-4:45PM, WWH 101
Textbook
Steven and Felix Halim's Competitive Programming (Second Edition)
Office hours
Contact Sean to make an appointment. Before and after class is preferred, other times are available.
Grading scheme
- Attendance (10%)
- Homework (40%)
- (# problems solved + # bonus problems solved) / # assigned problems
- Midterm presentation (20%) - July 30 in class
- Final presentation (30%) - August 15 in class.
The final must be a Powerpoint presentation that must contain:
- Abridged description of the problem so that the audience understands what is being asked.
- First thoughts and varieties of techniques thought that could be used to solve this problem, as well as any analysis used to dissuade the use of wrong techniques.
- The solution.
- An illustration of the algorithm applied to a sample input (possibly that you created, or possibly from the sample input). The algorithm should be shown to run a few steps, and the example shouldn't be too obvious.
- For DP, an explanation of the recurrence used.
- For BFS or Dijkstra's, an explanation of the states used in the queue.
- For max flow, an explanation of how to build the graph.
- Examples of corner cases you discovered.
- Possibly your code if there's anything you'd like to show, but it's not necessary.
Classes