Fall 2008

Course Overview

- To appreciate the role of algorithms in problem solving and software design, recognizing that a given problem might be solved with a variety of algorithms. The student should be capable of selecting among competing algorithms and justifying their selection based on efficiency.
- To understand both the specifications and implementations of standard data structures (lists, stacks, queues, linked structures, trees, maps), and be able to select and utilize appropriate data structures in developing programs.
- To develop programs using different problem-solving approaches (divide-and-conquer, backtracking, dynamic programming), and be able to recognize when one approach is a better fit for a given problem.
- To be able to design and implement a program to model a real-world system, and subsequently analyze its behavior.
- To recognize the importance of object-oriented techniques, and be able to utilize inheritance and polymorphism to build upon existing code.

Object-Oriented Programming class design interacting classes, private data fields & public methods static, final, private methods generic classes and methods interfaces examples: Comparable, Iterable, Collection, Set, List implementing an interface, polymorphism inheritance extending a class, overriding methods, polymorphism calling super from a derived class GUI design/building Data Structures previous structures: array, ArrayList, LinkedList, Stack, Queue low-level data structures linked lists singly-linked vs. doubly linked, ListNode, header node(s) trees non-linear structure, TreeNode, recursive processing binary tree, binary search tree balanced tree variants: AVL tree, red-black tree hash table hash function, collisions, clustering, load factor, rehashing linear probing vs. quadratic probing vs. chaining iterators Iterable interface: iterator Iterator interface: next, hasNext, remove Lists List interface: get, set, add, remove, contains, indexOf, size, iterator, ... ArrayList implementation: uses dynamic array O(1) get/set, O(1) add/remove from end, O(N) get/set/add/remove from index, O(N) contains/indexOf LinkedList implementation: uses doubly-linked list O(1) get/set/add/remove at either end, O(N) get/set/add/remove from index, O(N) contains/indexOf Collections static methods: binary_search, sort, shuffle, max Sets Set interface: add, remove, contains, clear, size, iterator, ... TreeSet implementation: uses red-black tree, ordered by compareTo O(log N) add/remove/contains, iteration follows compareTo ordering HashSet implementation: uses hash table with chaining O(1) add/remove/contains (on average), iteration follows no ordering Maps Map interface: get, put, remove, containsKey, keySet, size, ... TreeMap implementation: uses red-black tree for key-value pairs O(log N) get/put/remove/containsKey, keySet returns TreeSet of keys HashMap implementation: uses hash table with chaining O(1) get/put/remove/containsKey (on average); keySet returns HashSet Algorithm Analysis big-Oh notation formal definition, rate-of-growth analysis, asymptotic behavior searching & sorting sequential search vs. binary search insertion sort vs. selection sort vs. merge sort vs. heap sort specialized sorts: frequency counts, radix sort recursion base case(s), recursive case(s), analysis via recurrence relation algorithmic approaches divide&conquer: binary search, merge sort, tree algorithms, ... greedy: optimal optimal change (U.S.), job scheduling, ... backtracking: N-queens, blob count, Boggle, Sudoku, ... dynamic: optimal change, binomial coefficient, ...