CSC 321: Data Structures
- 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.
Java review, arrays, generics, iterators
inheritance, interfaces, polymorphism
List interface: ArrayList, LinkedList
Set Interface: TreeSet, HashSet
Map interface: TreeMap, HashMap
Stack class, Queue interface, PriorityQueue class
Graph interface: DiGraphList, DiGraphMatrix, GraphList, GraphMatrix
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, clustering, probing vs. chaining
functions & sets
bijections, mappings, sequences, sets & subsets
lists, sets, maps
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
bijection rule, product rule, sum rule, division rule,
generalized product rule, n choose k, inclusion/exclusion rule,
direct proof, proof by contradiction, proof by induction
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
recursive algorithms, recurrence relations
1. java review & design (credit card verification)
2. queues & efficiency (ArrayQueue vs. LinkedList)
3. linked structures (SpliceString, splice onto end)
4. linked structures (SpliceString, splice into middle)
5. recursion & binary search trees (height & weight, avg search cost)
6. maps & finite state machines (FSM PathTracer, pathFinder)