CSC 321: Data Structures
Spring 2024

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.

Tue, May 7 (1:00-2:40)	The test will be in-person, via Blueline. It is closed notes, closed books, closed neighbors, ... You must bring a laptop to class (or use one of the lab machines). It will be graded out of 100 points, but there will be 105 points available. So, you can miss 5 points and still be perfect!
Format same as midterm	factual knowledge: TRUE/FALSE, multiple choice conceptual understanding: short answer, discussion synthesis and application: explain/trace/modify code, evaluate the efficiency of a code segment, ...
Study advice	review online lecture notes review the online texts (if not mentioned in class, won't be on test) look over quizzes, homework assignments, midterm exam reference other sources for examples, different perspectives
Course material	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, PriorityQueue class Graph interface: DiGraphList, DiGraphMatrix, GraphList, GraphMatrix 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, clustering, probing vs. chaining 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, self-balancing 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 (credit card verification) 2. queues & efficiency (ArrayQueue vs. LinkedList) 3. lists & linked structures (ComboList) 4. proofs & counting (induction proofs, counting) 5. lists, trees & tries (Trie, memory/access comparisons) 6. treesets & text processing (WordSet) 7. maps & finite state machines (FSM, PathTracer, pathFinder)