CS2999 Problem Solving for programmers -- Fall 2012

Course Work

This course consists of individual work solving programming problems (mainly from the uva collection.

Problems will be assigned by the TA in consultation with the instructor.

Problem correctness will be as judged by the online judging system, or in cases where that is not possible, by the TA and/or the instructor.

In case of dispute, the instructor will decide whether a given solution is correct.

This course is Credit/No-Credit.

To receive credit, you must have completed, and have the TA/instructor sign off on

The final two problems will count as a "Take home final", and are hence due at the end of exam period.

Note that you don't have to do every problem, only the required number (see above). Roughly in order of difficulty.

2012-09-07 UVA 10137 The Trip
2012-09-22 UVA 11035 Poker Hands
2012-09-10 UVA 1202 Finding Nemo.
2012-10-08 UVA 10954 Add All. As a hint, consider the tree of additions. Notice that you pay for given number once for every time it occurs in the tree.
2012-10-11 UVA 1262 Password
2012-10-26 UVA 413 Up and Down
2012-11-09 UVA 12023 9 point circle
2012-11-09 UVA 12421 Lexical Analyzer
2012-11-30 Edit distance using dynamic programming, from "Programming Challenges". Dan will help with test data.
2012-12-03 UVA 11285 Exchange Rates
2012-12-05 UVA 681 Convex Hull

You can also do these problems, although they may be harder, or just require more background.

2012-09-10 UVA 1205 Color a tree. This problem is really a well known scheduling problem in disguise. The solution can be found in section 2 of Horn 1972. Sample data: 1205.sample-in 1205.sample-out
2012-09-10 UVA 1201 Taxi Scheme
2012-09-10 UVA 11989 Cutting Cake This needs some geometry (intersecting lines and line segments), as well as a basic sorted list structure.
2012-09-10 UVA 11998 Wario Land This needs a graph data structure.

Extra test data can be found at uva (csmall.in for Cutting Cake, lsmall.in for Wario Land)