CSC 427: Data Structures and Algorithm Analysis
Fall 2007
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
special purpose trees: heap (min-heap, max-heap)
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
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
Priority Queues
PriorityQueue class: peek, add, remove, size, iterator, ...
implementation uses min-heap, ordered by compareTo
O(1) peek, O(log N) add/remove
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, Huffman codes, ...
backtracking: N-queens, blob count, Sudoku, ...
dynamic: optimal change, binomial coefficient, minimal edit distance, ...