We meet every Tuesday, 2:30 - 3:20pm, in CSE room 203.

General Links

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

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:
  • 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, ...)

Week 4 (4/17/2012)

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

Week 3 (4/10/2012)

Strings and text processing (see Programming Challenges Ch. 3)

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

Week 1 (3/28/2012)

No meeting

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