Algorithmic Problem Solving

CSCI-UA.0480-004

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: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 in WWH102. 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:00PM-4:00PM in WWH 328 or the 13th Floor Lounge
  • Sean: Mondays, 4:50PM-5:50PM in WWH 328 or the 13th Floor Lounge

Grading

  • Homework: 65%
  • Midterm: 15%
  • Final Exam: 20%

Syllabus

  1. Introduction
  2. Data Structures
  3. Problem Solving Paradigms
  4. Graph Algorithms
  5. Mathematical Problems
  6. String Processing Algorithms
  7. Computational Geometry
  8. 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 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 incorrect submission).


Final

  1. Problems, Inputs, and Outputs

Classes

  1. Lecture 1.
  2. Lecture 2.
  3. Lecture 3.
  4. Lecture 4.
  5. Lecture 5.
  6. Lecture 6.
  7. Lecture 7 - Holiday.
  8. Lecture 8.
  9. Lecture 9.
  10. Lecture 10.
  11. Lecture 11 - Midterm.
  12. Lecture 12.
  13. Lecture 13.
  14. Lecture 14.
  15. Lecture 15.
  16. Lecture 16.
  17. Lecture 17.
  18. Lecture 18.
  19. Lecture 19.
  20. Lecture 20.
  21. Lecture 21.
  22. Java Geometry Library. Can also look at author's site for his C++ and Java Geometry routines.
  23. Lecture 23 Exercises.
  24. Lecture 26.

Midterm Topics and Solutions

Homeworks

  1. Programming Homework 1.

    Hints:

    1. The 3n+1 Problem: Be careful not to make any added assumptions about the two input integers. Additional sample input and sample output.
    2. 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 this problem.
    3. 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.
    4. I Can Guess The Data Structure: This problem has a lot of input and output, so code accordingly.
    5. Easy Problem from Rujia Liu?: A lot of input and output, so be careful. Requires a good way to store the data given.

  2. Programming Homework 2 (graded out of 5, so 6 correct means you receive extra credit). Problem E Alternative.

    Hints:

    1. Maximum Sub-sequence Product: Requires BigInteger. O(n^2) runtime is fine. Additional Sample Input and Additional Sample Output.
    2. 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.
    3. Virtual Friends: Union-Find. Additional Sample Input and Additional Sample Output.
    4. The Most Potent Corner: Bitmasks.
    5. Interval Product: Fenwick Trees. If you cannot read the characters on the page, just click the pdf link in the problem statement.
    6. Ping pong: Hard.

  3. Programming Homework 3 (graded out of 6).

    Hints:

    1. 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.
    2. Where is the Marble: Binary Search.
    3. Sum It Up: Complete Search.
    4. Block Voting: Complete Search. Try to run in O(n*2^n).
    5. The Money and the Oiled Bamboo: Binary Search.
    6. Dynamic Frog: Greedy.

  4. Programming Homework 4 (graded out of 4).

    Hints: Homework 4 Hints from class.

    1. Ingenuous Cubrency: Coin changing problem. Result requires a 64-bit integer. Input lines may have whitespace on them, so trim them before parsing.
    2. Diving for Gold: Knapsack Problem.
    3. 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 dimension.
    4. Chest of Drawers: Potential state for DP/memo could be (is above locked, drawer number, number needed to be locked).
    5. Test the Rods: Potential state for DP/memo could be (site number, amount that can be sent to NCPC).
    6. A Grouping Problem: Harder.

  5. Programming Homework 5 (Extra Credit).

    Hints:

    1. Spreadsheet - Top-down memoization; make sure your parsing is correct.
    2. What Goes Up - LIS from class.
    3. Watching the Kangaroo - Hard (not necessarily DP).
    4. The Dumb Grocer - Very Hard.

  6. Programming Homework 6 (graded out of 5).

    Hints:

    1. Battleships: Count the connected components that aren't sunk. Remember ships cannot touch.
    2. Ordering Tasks: Topological sort.
    3. Unlock the Lock: Breadth first search over the graph of reachable lock states.
    4. 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. Additional Sample Input and Additional Sample Output.
    5. Forwarding Emails: Sneaky DFS.
    6. Mall Mania: Multisource BFS. That is, add multiple items to the initial queue with distance zero. Total grid is small.

  7. Programming Homework 7 (graded out of 5).

    Hints (difficulties from 1 to 10):

    1. Dark Roads (diff=4): Straightforward application of Kruskal's algorithm.
    2. 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.
    3. 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.
    4. Commandos (diff=5): After running all pairs shortest path, the answer can be computed quickly.
    5. 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.
    6. Checkers (diff=5): Standard DP on a DAG. Just count the number of paths using memoization.
    7. Arbitrage (diff=8): Slightly trickier Bellman Ford.
    8. Ants Colony (diff=9): Requires a highly tuned implementation of Tarjan's LCA algorithm (the union-find DFS one). Don't reallocate any data structures unnecessarily, or use any hashing.

  8. Programming Homework 8 (graded out of 5).

    Hints:

    1. GCD (diff=3): Just implement Euclid's algorithm.
    2. 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.
    3. My T-shirt suits me (diff=7): Max flow on a bipartite graph with an added source and sink.
    4. 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.
    5. 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.
    6. Component Placement (diff=12): Harder min cut problem requiring very fast implementation (in Java I didn't get Edmonds-Karp to run in time and used FIFO Push-Relabel; can learn about algorithm on internet).

  9. Programming Homework 9 (graded out of 6).

    Hints:

    1. 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.
    2. 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.
    3. 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 64-bit integers.
    4. 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.
    5. Bachet's Game (diff=7): DP minimax decision tree. Make sure to ignore blank lines in the input.
    6. Exclusively Edible (diff=6): Equivalent to a 4-pile Nim game.
    7. Coconuts, Revisited (diff=9): Using brute force, solve many of the smaller cases and look for a pattern in the solution.
    8. Chess Game (diff=8): Run the Markov Chain for 1000 iterations and output the expected value.

  10. Programming Homework 10 (graded out of 5) .
  11. Hints:

    1. Where's Waldorf (diff=4): Brute force. Just look in every possible spot, and every possible direction for each word.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.

  12. Programming Homework 11 (graded out of 5) .
  13. Hints:

    1. Sunny Mountains (diff=4): Sort the coordinates by x, move right-to-left and then compute the portion of each peak that isn't blocked by earlier peaks.
    2. 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.
    3. 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.
    4. 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.
    5. 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).
    6. Colliding Traffic (diff=7): For each pair of boats, accurately solve a corresponding quadratic equation.
    7. 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.

  14. Programming Homework 12 (graded out of 9).
    1. Tour (diff=7): Bitonic Travelling Salesperson, will discuss in class.
    2. Subsequence (diff=4): Sliding window algorithm (Chap. 9.31).
    3. Knight Moves (diff=5): BFS.
    4. Stupid Sequence (diff=8): Setup an equation for the first 7 terms of the sequence, and solve for the coefficients using row reduction. See if your coefficient solution matches the rest of the values.
    5. Frosh Week (diff=6): Modified merge sort (Chap. 9.14).
    6. Finding Paths in Grid (diff=9): Matrix exponentiation.
    7. Editing a Book (diff=9): Bidirectional search (discussed in class).
    8. Complex Numbers (diff=6): De Moivre's theorem, will discuss in class. Sample Input and Sample Output. Here is some helpful sample code for sorting and formatting: code.
    9. Contemplation! Algebra (diff=7): Harder than 7, but will be 7 after class discussion. Sample Input and Sample Output
    10. Base i-1 (diff=4): Harder than 4, but will be 4 after class discussion.
    11. Cipher (diff=10): Will discuss in class.
    12. Code Permutations (diff=15): Will discuss in class. Sample Input and Sample Output.
    13. Robot (diff=9): 3x3 Matrix multiplication and vector addition for the arm movement. 3d line segment intersection for the testing. Only test for intersections that actually hit the arm and not the ones that hit the servos. Also, only test for when the servo goes strictly below the floor, and not just touches it. Sample Input and Sample Output. Here is some sample geometry code.
    14. Cave Crisis (diff=20): Very hard; will discuss in class. Sample Input and Sample Output
    15. Generalized Matrioshkas (diff=5): Use stacks to keep track of left and right dolls and the total size of the dolls at a given level.