Quest to Solve Them All (two students from Simon Frazer University who solve many problems and document their solution strategies)
UVa Online Judge for submitting/testing problem solutions online
(if you get a "redirect loop" error in your browser when trying to access Online Judge, clear your cookies and try again)
116  Unidirectional TSP
 Find an optimalweight path through a 2D grid.
input,
output,
input2,
output2(Hint: Two hard parts are the fact that you need to print out the minweight path, and also that there can be ties that need to be broken by minimumrownumber from left to right. Think about the order in which you process columns; which ordering is better, lefttoright or righttoleft?)
Number Theory / Combinatorics; Miscellaneous Problems
Thoughts about the homework problems from last week?
This week we just did some practice problems.
There was not an overarching theme, but some of them involved number theory, so some number theory topics are listed here.
A related topic is combinatorics (the mathematics of counting).
efficiently solve a selfsimilar problem by storing partial results; often recursive in nature, but don't always have to use recursive code to solve it
greedy algorithms; backtracking
topdown DP: caching previously computed results, e.g. in an array or map.
Also called memoization
bottomup DP: build a table of values upward as you go, from start (0?) up to N.
Homework: try to solve at least one of these problems.
136  Ugly Numbers
 Find the 1500th "ugly" number whose only prime factors are 2, 3, and 5.
(Hint: How can you find the Nth "ugly" number if you know ugly numbers 1 .. N1? What is its relationship to those numbers, to one of those numbers?)
147  Dollars
 How many ways can you make change for a given amount in New Zealand dollars/coins?
input,
output(Hint: Explore each dollar/coin value exhaustively, one at a time.)
111  History Grading
 Which students' orderings of historical events have the longest sequences of events in the right order?
input,
output,
input2,
output2(Hint: This is essentially the longest increasing subsequence problem. But it can be tricky to understand the input for the 'correct' ordering. Input of 2 4 1 3 means that the first event goes at 1based index #2, the second goes at index #4, etc. So it means that the correct ordering is 3 1 4 2. Be careful to represent this properly in your code.)
116  Unidirectional TSP
 Find an optimalweight path through a 2D grid.
input,
output,
input2,
output2(Hint: Two hard parts are the fact that you need to print out the minweight path, and also that there can be ties that need to be broken by minimumrownumber from left to right. Think about the order in which you process columns; which ordering is better, lefttoright or righttoleft?)
231  Testing the CATCHER
 Given a set of missile launches, how many can the CATCHER defense system intercept?
May 8 2012 2:20 PM
Week 7 (5/8/2012)
Recursion and backtracking (see Programming Challenges Ch. 8)
Thoughts about the homework problems from last week?
Focus on problems best solved recursively.
recursion; identifying how a problem is selfsimilar
112  Tree Summing
 given a tree and an integer, is there a roottoleaf path that sums up to that integer?
(The hardest part is avoiding "time limit exceeded errors; think about efficiency!
StringBuilders are good; String concatenation, regular expressions, and unnecessary recursion are slow.)

input,
output
110  MetaLoopless Sorts
 generate source code for programs that sort arrays of input without loops
299  Train Swapping
 figure out how many swaps are needed to arrange a set of trains into order
123  Searching Quickly
 key sentence in description: "If a word appears more than once in a title, each instance is a potential keyword."

input,
output
10205  Stack 'em Up
(alt)
 perform a given set of shuffles on a deck of cards
clarification: the deck resets to its original ordering between input "cases");
torturetest input,
output
If you solve a problem, consider posting your solution in the message forum!
If you generate a better sample input for one of the above problems that tests some tricky cases, or if you have a hint that you want to share with others, consider posting that in the message forum, too.
Apr 10 2012 2:20 PM
Week 3 (4/10/2012)
Strings and text processing (see Programming Challenges Ch. 3)
Who still needs to get added to the course?
Thoughts about the homework problems from last week?
Mostly focus on string and text processing problems.
Homework: try to solve at least one of these problems. (Write a file Main.java that accepts the input from System.in and produces the output to System.out. See the example Main.java for #5118.)
Homework: Create an account on Online Judge, and try to solve one or both of these problems. Look at your nearest timepiece to get a sense of how long the problems take you.