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,
- 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.
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:30PM-4:45PM, WWH 512
Optional Homework Help Session
Friday, 5:00PM-7: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:00PM-7:00PM. Must bring a Laptop!
Programming Team Mailing List
Steven and Felix Halim's Competitive Programming (Third Edition)
or contact Brett to
make an appointment. Official offices hours are below:
- Brett: Thursdays, 3:00PM-4:00PM in WWH 328 or the 13th Floor
- Sean: Mondays, 4:50PM-5:50PM in WWH 328 or the 13th
- Homework: 65%
- Midterm: 15%
- Final Exam: 20%
- Data Structures
- Problem Solving Paradigms
- Graph Algorithms
- Mathematical Problems
- String Processing Algorithms
- Computational Geometry
- Advanced Topics
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
Judge. More information will be posted here for each
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 server-side 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
- Lecture 1.
- Lecture 2.
- Lecture 3.
- Lecture 5.
- Lecture 6.
- Lecture 7 - Holiday.
- Lecture 8.
- Lecture 9.
- Lecture 10.
- Lecture 11 - Midterm.
- Lecture 12.
- Lecture 13.
Midterm Topics and Solutions
- The 3n+1 Problem: Be careful not to make any added assumptions about the
two input integers.
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). 32-bit integer arithmetic is fine for
- 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.
Homework 2 (graded out of 5, so 6 correct means you receive
Problem E Alternative.
- Maximum Sub-sequence Product: Requires BigInteger.
O(n^2) runtime is
Sample Input and Additional
- Open Source: Maps and or sets can be useful.
Sample Input 1 and Additional
Sample Output 1. Additional
Sample Input 2 and Additional
Sample Output 2.
- Virtual Friends: Union-Find. Additional
Sample Input and Additional
- 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
- Ping pong: Hard.
Homework 3 (graded out of 6).
- 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
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
- The Money and the Oiled Bamboo: Binary Search.
- Dynamic Frog: Greedy.
Homework 4 (graded out of 4).
Hints: Homework 4 Hints from class.
- Ingenuous Cubrency: Coin changing problem. Result requires a 64-bit integer.
Input lines may have whitespace on them, so trim them before
- Diving for Gold: Knapsack Problem.
- Garbage Heap: Use 64-bit integers for everything. Can
get a O(n^5) algorithm by looping over all possible
rectangles, and running Kadane's algorithm in the 3rd
- 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).
- Spreadsheet - Top-down 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).
- 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 2-color each component.
Remember that each vertex must be guarded, so a component
with 1 vertex needs a guard.
- Forwarding Emails: Sneaky DFS.
- Mall Mania: Multisource BFS. That is, add multiple
items to the initial queue with distance zero. Total grid