• To understand fundamental data structures (lists, stacks, queues, sets, maps, and linked structures) and be able to implement software solutions to problems using these data structures.
• To achieve a working knowledge of various mathematical structures essential for the field of computer science, including graphs, trees, and networks.
• To develop analytical techniques for evaluating the efficiency of data structures and programs, including counting, asymptotics, and recurrence relations.
• To be able to design and implement a program to model a real-world system, selecting and implementing appropriate data structures.

Data Structures
  Java review, arrays, generics, iterators
    inheritance, interfaces, polymorphism
  Collections
    List interface: ArrayList, LinkedList
    Set Interface: TreeSet, HashSet
    Map interface: TreeMap, HashMap
    Stack class, Queue interface
  low-level structures
    linked lists: singly vs. doubly, dummy nodes, iterators
    trees: hierarchical, recursive processing, binary search trees,
           heaps, heap sort, array implementation
    graphs: adjacency matrix vs. list
    hash tables: hash functions, load factor, rehashing
      collisions, probing vs. chaining, clustering
  
Math Structures
  functions & sets
    bijections, mappings, sequences, sets & subsets 
  linear structures
    lists, sets, maps
  nonlinear structures
    trees: root, leaf, child, path, height, weight, ...
      binary search trees, balanced trees (red-black, AVL), heaps
    graphs: vertex, edge, adjacent, incident, degree, path, ...
      simple vs. directed, weighted vs. unweighted
      depth first search, breadth first search, finite state machines
  counting techniques
    bijection rule, product rule, sum rule, division rule,
    generalized product rule, n choose k, inclusion/exclusion rule,
    pigeonhole principle
  proof techniques
    direct proof, proof by contradiction, proof by induction
   
Algorithm Analysis
  algorithm analysis
    best vs. average vs. worst case analysis
    big-Oh notation, rate-of-growth analysis, big-Omega & big-Theta
    searching and sorting
      standard algorithm analysis, specialized sorting algorithms
  recursion
    recursive algorithms, recurrence relations
 
Assignments
  1. java review & design (ISBN numbers)
  2. queues & music (piano player)
  3. algorithm analysis (comparing algorithms & timing Collections.sort)
  4. lists & linked structures (HybridList)
  5. recursion & binary trees (induction proofs & tree methods)
  6. text & maps (kth-order approximations)