Description
Algorithmic Problem Solving studies the implementation and application of algorithms to a variety of problems. Topics covered will include:
 code performance analysis,
 parsing and formatting text,
 mathematics,
 advanced data structures,
 graph algorithms,
 dynamic programming, and
 computational geometry.
Evaluation is based on participation in programming contests, quizzes, and exams.
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. Basic algorithms and comfort with Java or C++ is a prerequisite.
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
Monday and Wednesday, 3:30PM4:45PM, WWH 512
Optional Homework Help Session
Friday, 5:00PM7:00PM, WWH 102
Date and time of Midterm Exam
Monday, March 3, 2014, in class. Closed book.
Date and time of Final Exam
Friday, May 16, 2014, 5:00PM7:00PM. Must bring a Laptop!
Programming Team Mailing List
Sign
up here.
Textbook
Steven and Felix Halim's Competitive Programming (Third Edition)
Office hours
Contact Sean
or contact Brett to
make an appointment. Official offices hours are below:
 Brett: Thursdays, 3:00PM4:00PM in WWH 328 or the 13th Floor
Lounge
 Sean: Mondays, 4:50PM5:50PM in WWH 328 or the 13th
Floor Lounge
Grading
 Homework: 65%
 Midterm: 15%
 Final Exam: 20%
Syllabus
 Introduction
 Data Structures
 Problem Solving Paradigms
 Graph Algorithms
 Mathematical Problems
 String Processing Algorithms
 Computational Geometry
 Advanced Topics
Homework Policy
Codebooks are allowed for standard algorithms, but all of the
submitted code must be your own. Collaboration is allowed on all
assigments except the midterm and final, but each student must
submit his/her own code. Programming assignments will be
submitted through
Virtual
Judge. More information will be posted here for each
assignment.
If you are enrolled in the course,
please register an account on Virtual Judge with username netid_CS480S14. If
you are just following the course but are not enrolled, any
username will do, but please do not suffix it with _CS480S14.
Programming Homework Instructions
Each week there will be a programming homework hosted on the
Virtual Judge, with links given below. As stated above, please
register an account on Virtual
Judge with username netid_CS480S14. Your grade will be based on
the number of problems solved correctly. All programs must take
their input from standard input, and must write their output to
standard output. Java programs must be contained in a public
class entitled Main, and they must be in the default package.
C++ programs must have a function main, and
Java programs must have a method main. If you get Judging Error
1, it means the judging queue is backed up, and you can simply
click refresh to be rejudged. If you get Judging Error 2, it
means their are serverside communication errors, and your submission
should be automatically rejudged when the communication problems are
fixed. On Judging Error 2, if you see other people getting
submissions through, you may want to resubmit.
The student ranking (not used to determine your HW grade)
is determined by how quickly you submit each
problem (measured from the start of the competition), and how many
incorrect submissions you have made (penalized 20 minutes for each
incorrect submission).
Classes
 Lecture 1.
 Lecture 2.
 Lecture 3.

Lecture 4.
 Lecture 5.
 Lecture 6.
 Lecture 7  Holiday.
 Lecture 8.
 Lecture 9.
 Lecture 10.
 Lecture 11  Midterm.
 Lecture 12.
 Lecture 13.
 Lecture 14.
 Lecture 15.
 Lecture 16.
 Lecture 17.
 Lecture 18.
 Lecture 19.
 Lecture 20.
 Lecture 21.
 Java Geometry
Library. Can also look
at
author's site for his C++ and Java
Geometry routines.
Midterm Topics and Solutions
Homeworks
 Programming
Homework 1.
Hints:
 The 3n+1 Problem: Be careful not to make any added assumptions about the
two input integers.
Additional sample
input and sample output.
 Polly The Polynomial: Time bounds are very tight on this
problem. Make sure to use the efficient I/O methods discussed
in class, and compute the polynomial values effciently
(
Horner's Rule). 32bit integer arithmetic is fine for
this problem.
 Newspaper: This problem has a lot of input, and uses
extended ASCII, so use efficient I/O methods and remember the
comment I made in class (about extended ASCII). Fixed the
problem statement: there should be no space before the output.
 I Can Guess The Data Structure: This problem has a lot of
input and output, so code accordingly.
 Easy Problem from Rujia Liu?: A lot of input and output, so be
careful. Requires a good way to store the data given.
 Programming
Homework 2 (graded out of 5, so 6 correct means you receive
extra
credit).
Problem E Alternative.
Hints:
 Maximum Subsequence Product: Requires BigInteger.
O(n^2) runtime is
fine. Additional
Sample Input and Additional
Sample Output.
 Open Source: Maps and or sets can be useful.
Additional
Sample Input 1 and Additional
Sample Output 1. Additional
Sample Input 2 and Additional
Sample Output 2.
 Virtual Friends: UnionFind. Additional
Sample Input and Additional
Sample Output.
 The Most Potent Corner: Bitmasks.
 Interval Product: Fenwick Trees. If you cannot read
the characters on the page, just click the pdf link in the
problem statement.
 Ping pong: Hard.
 Programming
Homework 3 (graded out of 6).
Hints:
 Ants: Classic interview problem. Greedy aspect to it.
Don't make any assumptions about the white space in the
problem (there may be missing or extra newlines
anywhere). Additional
Sample Input and
Additional Sample Output.
 Where is the Marble: Binary Search.
 Sum It Up: Complete Search.
 Block Voting: Complete Search. Try to run in
O(n*2^n).
 The Money and the Oiled Bamboo: Binary Search.
 Dynamic Frog: Greedy.
 Programming
Homework 4 (graded out of 4).
Hints: Homework 4 Hints from class.
 Ingenuous Cubrency: Coin changing problem. Result requires a 64bit integer.
Input lines may have whitespace on them, so trim them before
parsing.
 Diving for Gold: Knapsack Problem.
 Garbage Heap: Use 64bit integers for everything. Can
get a O(n^5) algorithm by looping over all possible
rectangles, and running Kadane's algorithm in the 3rd
dimension.
 Chest of Drawers: Potential state for DP/memo could be (is
above locked, drawer number, number needed to be locked).
 Test the Rods: Potential state for DP/memo could be
(site number, amount that can be sent to NCPC).
 A Grouping Problem: Harder.

Programming Homework 5 (Extra Credit).
Hints:
 Spreadsheet  Topdown memoization; make sure your
parsing is correct.
 What Goes Up  LIS from class.
 Watching the Kangaroo  Hard (not necessarily DP).
 The Dumb Grocer  Very Hard.

Programming Homework 6 (graded out of 5).
Hints:
 Battleships: Count the connected components that aren't
sunk. Remember ships cannot touch.
 Ordering Tasks: Topological sort.
 Unlock the Lock: Breadth first search over the
graph of reachable lock states.
 Place the Guards: Try to 2color each component.
Remember that each vertex must be guarded, so a component
with 1 vertex needs a guard. Additional
Sample Input and Additional
Sample Output.
 Forwarding Emails: Sneaky DFS.
 Mall Mania: Multisource BFS. That is, add multiple
items to the initial queue with distance zero. Total grid
is small.

Programming Homework 7 (graded out of 5).
Hints (difficulties from 1 to 10):
 Dark Roads (diff=4): Straightforward application of Kruskal's
algorithm.
 Lift Hopping (diff=7): Run Dijkstra on the graph of
(elevator,floor) pairs. The queue is initialized with all
pairs of the form (e,0) where elevator e can go to floor
0. Remember that switching elevators requires 60 seconds.
 Traffic (diff=6): Use Bellman Ford and note that the edge weights
are the differences in busyness cubed. Correction to
problem statement: There may be multiple blank lines between
each input test case. To address this, and any other
weirdness, make the first line of your main while loop start
with:
if (line.trim().length() == 0) continue;
Also, make sure to output '?' if the
cost is less than 3 or if the node is unreachable (negative
infinity is less than 3 in case of a negative cycle).
Additional
Sample Input and
Additional
Sample Output.
Additional
Sample Input 2 and
Additional
Sample Output 2.
 Commandos (diff=5): After running all pairs shortest path, the
answer can be computed quickly.
 Inspector's Dilemma (diff=6): For each connected component, count
the number of odd degree nodes, and use what we learned
about Eulerian graphs.
Additional
Sample Input and
Additional
Sample Output.
 Checkers (diff=5): Standard DP on a DAG. Just count the number
of paths using memoization.
 Arbitrage (diff=8): Slightly trickier Bellman Ford.
 Ants Colony (diff=9): Requires a highly tuned implementation of
Tarjan's LCA algorithm (the unionfind DFS one). Don't
reallocate any data structures unnecessarily, or
use any hashing.

Programming Homework 8 (graded out of 5).
Hints:
 GCD (diff=3): Just implement Euclid's algorithm.
 Eventually Periodic Sequence (diff=4): Use a stack to
evaluate the reverse polish notation. As numbers can get
big, use longs and mod by N after every computation.
 My Tshirt suits me (diff=7): Max flow on a bipartite
graph with an added source and sink.
 The Problem with the Problem Setter (diff=8): Max flow
on a bipartite graph where you need to output your
solution. Can just look at neighbors of each category node
to build output.
 Angry Programmer (diff=9): Min cut with vertex and edge
capacities. Even though the graph in the problem is
undirected, your graph should be directed to properly handle
the vertex capacities.
 Component Placement (diff=12): Harder min cut problem
requiring very fast implementation (in Java I didn't get
EdmondsKarp to run in time and used FIFO PushRelabel; can learn
about algorithm on internet).

Programming Homework 9 (graded out of 6).
Hints:
 Tennis Contest (diff=4): You can compute the
probability using binomial coefficients, you can look up the
negative binomial distribution, and I think even Markov
chain techniques will work. Make sure to use doubles for
all of your calculations.
 Prime Factors (diff=5): Build a sieve up to 2^16
the number, and then factor the number by testing
divisibility by the primes in your sieve.
Additional Sample
Input and
Additional Sample Output.
 Jimmy's Balls (diff=6): Come up with a formula to solve
the problem when there are only two colors. Then use this
formula to solve the 3 color case. Requires 64bit integers.
 Benefit (diff=8): The existence of a solution is
determined by C % A == 0. Use C/A and the formula for
LCM using prime factorization.
 Bachet's Game (diff=7): DP minimax decision tree. Make
sure to ignore blank lines in the input.
 Exclusively Edible (diff=6): Equivalent to a 4pile Nim
game.
 Coconuts, Revisited (diff=9): Using brute force, solve
many of the smaller cases and look for a pattern in the
solution.
 Chess Game (diff=8): Run the Markov Chain for 1000
iterations and output the expected value.

Programming Homework 10 (graded out of 5) .
Hints:
 Where's Waldorf (diff=4): Brute force. Just look in every
possible spot, and every possible direction for each
word.
 Power Strings (diff=5): Can use brute force. Test every
possible substring of viable length. Can also be done using
the KMP table: for a string x,
find suffixes of x that are prefixes of x so that the
remaining part has length dividing the length of x.
 Extend to Palindrome (diff=6): You are looking for the
longest suffix that is a palindrome. To do this, find the
longest suffix of the string that is a prefix of the
reverse using KMP.
 Glass Beads (diff=7): If the string is x, find the
lexicographically first substring of xx (x concatenated with
itself) of length x. This can be done quickly with a
suffix tree.
 DNA Sequencing (diff=9): Build the generalized suffix
tree of the two given strings. Do one DFS to find the length
of the longest common substring. Then do another DFS to print
all substrings that satisfy the requirement. The substrings in
question will always correspond to nodes of the suffix
tree. Sample
Input and
Sample Output.
 GATTACA (diff=8): Build a suffix tree, and then DFS over
the nodes to find the length of the longest repeated
substring. Then DFS one more time to output the
lexicographically first one. The answer will always be at a
node of the tree.
 Life Forms (diff=10): Build the generalized suffix tree
for the given strings. Do a DFS to find the length of the
longest common substring to more than half. Then DFS again
to output them all. They will always occur at nodes of the
tree.

Programming Homework 11 (graded out of 5) .
Hints:
 Sunny Mountains (diff=4): Sort the coordinates by x, move
righttoleft and then compute the portion of each peak that
isn't blocked by earlier peaks.
 Billiard Bounces (diff=3): Using kinematics, determine
how far the ball will travel. Then use the reflected boards
discussed in class to compute the problem.
 Nails (diff=3): Use the convex hull code to compute the
perimeter of the convex hull. Make sure to only read the
number of lines specified by the problem, as their may be
garbage data after the specified number of test cases.
 Trash Removal (diff=6): First compute the convex hull.
You may assume that one of the sides of the convex hull will
be flush against the garbage chute. Use an O(n^2) algorithm
chute width considering all sides of the convex hull and all
possible opposing points.
 How Big Is It? (diff=7): First solve the 2 circle case.
Then solve the n circle case by considering all possible
permutations of the circles. Make sure to handle the cases
2,.4,2 (giving 8), and .1,2,.1 (giving 4).
 Colliding Traffic (diff=7): For each pair of boats,
accurately solve a corresponding quadratic equation.
 Center of Masses (diff=5): The points are in no
particular order, so first compute their convex hull, and
then use the centroid of a
polygon
formula . Code this one carefully, as the time limits
are pretty strict.