CSE 390 B, ACM Contest Prep, Spring 2012

Week 10 (5/29/2012)

Graphs (see Programming Challenges Ch. 9, 10)

slides ( PDF)
properties of graphs: un/directed, un/weighted, a/cyclic
representing a graph: adjacency matrix, adjacency list
- tradeoffs: sparseness; memory usage; better for certain algorithms (list = finding all neighbors; matrix = A/B neighbor lookup)
graph searching: depth-first (DFS), breadth-first (BFS)
finding shortest path from a given start vertex: Dijkstra's algorithm, A*
finding all shortest paths between pairs: Floyd-Warshall algorithm (Wikipedia)
Hamiltonian path/circuit: visit every vertex exactly once (NP-complete)
Eulerian path/circuit: following every edge exactly once
topological sort

Homework: try to solve at least one of these problems.
- 429 - Word Transformation - transform one word from a dictionary into another word of the same length
- 104 - Arbitrage - find the minimum path that yields a profit
- 534 - Frogger
- 116 - Unidirectional TSP - Find an optimal-weight path through a 2-D grid. input, output, input2, output2 (Hint: Two hard parts are the fact that you need to print out the min-weight path, and also that there can be ties that need to be broken by minimum-row-number from left to right. Think about the order in which you process columns; which ordering is better, left-to-right or right-to-left?)
- 124 - Following Orders
- 200 - Rare Order

Week 9 (5/22/2012)

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).
greatest common divisor (GCD); the Euclidean algorithm for finding GCDs (and its extended version)
least common multiple (LCM) and its relation to GCD
modular arithmetic: add, subtract, multiply, divide in (mod N) domain
- congruency mod N
- using modular arithmetic to avoid overflow or simplify computations (e.g. last digit of a very large number)
- applications of, e.g. RSA
prime numbers
- prime factorization (algorithm)
- BigInteger.isProbablePrime, BigInteger.nextProbablePrime for finding prime numbers
Identifying combinatorics problems: "How many ..."
possibly helpful CSE 312 lecture notes on counting (11au) and probability (textbook)
permutations (MathWorld) and combinations (MathWorld)
binomial coefficients (MathWorld), Pascal's triangle
interesting number sequences:
- Fibonacci numbers (MathWorld)
- Catalan numbers (MathWorld)
  - number of ways to place balanced parentheses
  - number of correct associations of a binary operator
  - number of full binary trees (every node has 0 or 2 children) with N+1 leaves is Catalan(N)
  - number of diagonal paths along a 2D x/y grid from one corner to the other that don't cross over the diagonal
  - number of ways to tile a stairstep shape of height n with n rectangles
- Eulerian numbers (MathWorld)
- Homework: try to solve at least one of these problems.

Week 8 (5/15/2012)

Dynamic programming (see Programming Challenges Ch. 11)

Thoughts about the homework problems from last week?
Focus on problems best solved using dynamic programming algorithms (Algorithmist)
efficiently solve a self-similar problem by storing partial results; often recursive in nature, but don't always have to use recursive code to solve it
greedy algorithms; backtracking
top-down DP: caching previously computed results, e.g. in an array or map. Also called memoization
bottom-up DP: build a table of values upward as you go, from start (0?) up to N.
Some common DP algorithms:

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 .. N-1? 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 1-based 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 optimal-weight path through a 2-D grid. input, output, input2, output2 (Hint: Two hard parts are the fact that you need to print out the min-weight path, and also that there can be ties that need to be broken by minimum-row-number from left to right. Think about the order in which you process columns; which ordering is better, left-to-right or right-to-left?)
- 231 - Testing the CATCHER - Given a set of missile launches, how many can the CATCHER defense system intercept?

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 self-similar
backtracking (slides 1), (slides 2): choose, explore, un-choose
exhaustive search - when should / shouldn't it be used?
generating all possibilities / permutations / combinations / arrangements / ...
generating all subsets
breadth vs. depth-based searching
efficiency; pruning the decision tree; minimization/maximization and heuristic-guided searches

Homework: try to solve at least one of these problems.
- 628 - Passwords
- 155 - All Squares
- 112 - Tree Summing - given a tree and an integer, is there a root-to-leaf 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 - Meta-Loopless Sorts - generate source code for programs that sort arrays of input without loops
- 297 - Quadtrees
- 843 - Crypt Kicker (alt) - try to find a mapping of letters to decrypt a message; tricky!
- 861 - Little Bishops (alt) - a variant of 8 Queens

Week 6 (5/1/2012)

Searching and sorting (see Programming Challenges Ch. 4)

Thoughts about the homework problems from last week?
Focus on searching, sorting.
searching: Collection contains, List indexOf, lastIndexOf (sequential - O(N)), Arrays.binarySearch, Collections.binarySearch (binary - O(log N)), Map containsKey (fast) / containsValue (slow)
sorting: Arrays.binarySearch, Collections.binarySearch, Arrays.sort, Collections.sort
Comparable (internal ordering): public int compareTo(T other)
Comparator (external ordering): public int compare(T o1, T o2)
- passing a Comparator to constructor of a TreeMap/Set, PriorityQueue
- passing a Comparator to Arrays/Collections.binarySearch
applications of sorting: How is sorting related to performing these tasks?
- testing whether the elements of a collection are unique
- getting rid of duplicates
- finding the minimum, median, and/or maximum from a collection
- finding the most frequently occurring element, i.e., mode (or the frequencies of elements in general)
- performing a union or intersection on two collections
- searching for one element in a collection
stable vs. unstable sorts

Homework: try to solve at least one of these problems.
- Practice problem - Rating the Field (not in the Online Judge, but was shown in class) - input, output, solution
- 102 - Ecological Bin Packing
- 10152 - ShellSort (alt)
- 156 - Ananagrams
- 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
- 131 - The Psychic Poker Player
- 140 - Bandwidth
- 10041 - Vito's Family (alt)

Week 5 (4/24/2012)

Collections, data structures (see Programming Challenges Ch. 2)

Thoughts about the homework problems from last week?
Focus on problems that benefit from using Java's collection framework (java.util).
Choosing the right data structure to solve a problem:
- an array (Hey, sometimes they're the best choice; but when?)
- List: ArrayList vs LinkedList
- Set: HashSet vs LinkedHashSet vs TreeSet
- Map: HashMap vs LinkedHashMap vs TreeMap
- others: Stack, Queue, PriorityQueue, Deque
- BitSet (for bit methods, see also: Integer, BigInteger)
compound data structures: list of lists, map of sets, ...
methods you might not know about:
- all collections: addAll/retainAll/removeAll (set union/intersection/difference), toArray
- Arrays.asList (a fast and easy way to declare a List<T> with given elements in it)
- ArrayList: constructor(capacity), subList, listIterator
- TreeSet: ceiling/floor, first/last, headSet/tailSet, descendingSet
utility class: Arrays (methods: asList, binarySearch, copyOf, copyOfRange, equals, deepEquals, fill, sort, toString, ...)
utility class: Collections (methods: binarySearch, copy, fill, frequency, indexOfSubList, max, min, nCopies, replaceAll, reverse, rotate, sort, shuffle, swap, ...)

Homework: try to solve at least one of these problems.
- 10038 - Jolly Jumpers (alt) - differences between neighbors in a sequence of integers
- 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"); torture-test input, output
- 10315 - Poker Hands (alt)
- 120 - Stacks of Flapjacks (alt)
- 10041 - Vito's Family (alt)
- 10026 - Shoemaker's Problem (alt)

Week 4 (4/17/2012)

Integers, real numbers, arithmetic, number theory (see Programming Challenges Ch. 5, 7)

Thoughts about the homework problems from last week?
Mostly focus on numeric, mathy problems.
int vs. long; long literals (e.g. 123456789012345L)
Integer and Double and Long static methods
- Integer.parseInt, Double.parseDouble, Long.parseLong
- Integer/Long bit methods: bitCount, highestOneBit, lowestOneBit, numberOfLeadingZeros, numberOfTrailingZeros, reverse, reverseBytes, rotateLeft, rotateRight
perils of using double: roundoff errors; 0.0 vs. -0.0; NaN; Infinity vs. -Infinity; ulps; Double methods
java.math.BigInteger and java.math.BigDecimal for representing very large numbers (immutable)
- BigInteger.valueOf(long) (flyweighting), new BigInteger(String)
- add/subtract/multiply/divide/mod, pow, gcd, compareTo, toString, radix stuff, and/or/not/xor, isProbablePrime, nextProbablePrime
Math static methods (abs, ceil, cos, exp, floor, hypot, log, log10, max, min, random, round, signum, sin, sqrt, tan, toDegrees/Radians)
- Java's "static import" feature: import static java.lang.Math.*;
java.util.Random for random numbers
working with bases other than base-10: Integer.parseInt(String, radix), Integer.toString(int, radix), Long.parseLong(String, radix), Long.toString(int, radix), new BigInteger(String, radix), System.out.printf, String.format
greatest common divisor (GCD); the Euclidean algorithm for finding GCDs (and its extended version)
least common multiple (LCM) and its relation to GCD
modular arithmetic: add, subtract, multiply, divide in (mod N) domain; congruency mod N; applications e.g. RSA
prime numbers
- prime factorization (algorithm)
- BigInteger.isProbablePrime, BigInteger.nextProbablePrime for finding prime numbers
aside: discuss Google Code Jam problems

Homework: try to solve at least one of these problems.
- 10018 - Reverse and Add (alt)
- 10183 - How Many Fibs? (alt)
- 701 - The Archeologist's Dilemma (alt)
- 10035 - Primary Arithmetic (alt)
- 10006 - Carmichael Numbers
- 10168 - Summation of Four Primes
- 10104 - Euclid Problem
- 10139 - Factovisors
- 10127 - Ones (alt) - watch your runtime!
- 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.

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.
- String class methods
- String.format and System.out.printf for formatted output (formatting codes)
- which methods are fast, which are slow? (indexOf, length, substring, toUpperCase, ...)
- the String + operator; how does it work?
- StringBuilder (StringBuilder(int size); append; toString...)
- regular expressions with String.matches, String.replaceAll (vs replace), String.split, java.util.regex.Pattern
- String and char
  - ASCII, Unicode
  - printable vs. non-printable characters
  - String methods: charAt, toCharArray, replace
  - char vs. int; char vs. Character; Character class methods
- some string algorithms: edit (Levenshtein) distance, longest common subsequence

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.)

Week 2 (4/4/2012)

Basic problems and contest details (skim Programming Challenges Ch. 1)

How should we spend our time? How do you want to structure these sessions? (Pick random Online Judge problems? Follow a course like Stony Brook's?)
How does a successful 3-person team organize itself?
What kinds of problems appear on the typical contest?
Finding "the easy problem" - Which of the following problems (from 2007 Pac NW Regionals) is "the easy one"? option 1, option 2, option 3

Reference problem solution: Main.java for problem 5118: Always Follow the Rules in Zombieland
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.
- 4065 - Rock, Paper, or Scissors?
- 4071 - "Bubble Gum, Bubble Gum, in the dish, how many pieces do you wish?"

Week 1 (3/28/2012)

No meeting

We didn't meet; class was not created yet.

CSE 390 B, ACM Programming Contest Prep, Spring 2012

General Links