CSC 321: Data Structures
Fall 2012
Final Review
- 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, ...
depth first search, breadth first search, topological sort
finite state machines
DFA vs. NDFA, pattern recognition, regular languages/expressions
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 (anagram finder)
2. queues & music (piano player)
3. algorithm analysis (book exercises & timing Collections.sort)
4. linked structures (LinkedString for DNA sequences)
5. recursion & binary trees (tree methods & inductive proofs)
6. sets & maps (book reviews)