COSC 300 – Advanced Data Structures

# Spring 2018 Final Study Guide

Final Time: 5/2/2018, 8:30 AM – 10:30 AM

The final will be two hours long with 12-15 questions plus a bonus question. Questions may be multiple choice, fill-in the blank questions, short answer questions, or program fragments. The final is cumulative but will stress what we have done in the second half of the semester. Below are the topics that were covered in the second half.

# Objectives

• Understand the benefits and additional complexity of balancing a BST: AVL, Splay, Randomized, BST, and 2-3-4 Tree (Red-Black Tree).
• Know how rotations
• Understand the usefulness of hashing, the average and worst-case complexity of hash table operations, and basic collision resolution
• Know how to write good hash function and to recognize a bad
• Know the different kinds of graphs: Undirected/Directed, Unweighted/Weighted, Multi-graphs, Symbol Graphs, and the useful graph
• Recognize a problem that is amenable to representation by a graph and one which can be solved by a graph
• Be familiar with sorting algorithms that are especially useful for strings and know their
• Be familiar with the basic algorithms for substring search and pattern matching, and their
• Be familiar with types of algorithms: dynamic programming, divide-and-conquer, Monte Carlo, Las Vegas, brute force.
• Know how regular expressions are used, what languages they represent, and how to convert them to NFAs and
• Know that there are undecidable problems, and be able to give an example of a decidable problem and an undecidable
• Understand the basic complexity class: P, NP, NP-hard, and NP-complete, know how to show a problem is in one of the class, and know example problems in each
• Understand how reductions and poly-time reductions work, and be able to reduce one closely related problem to

# Concepts

• Balanced Trees
• Rotation: Single and Double
• Hashing
• Collision Resolution
• Uniform Hashing Assumption
• Re-hashing
• Graphs: Undirected/Directed, Unweighted/Weighted, Multi-
• Path (graph)

• Connected Component (graph)
• Spanning Tree, Spanning Forest
• Sparse Dense Graph
• Shortest Path (unweighted/weighted), single-source/multiple-destination, all pairs
• DFS Numbers (pre- and post-)
• Articulation Points (Critical Vertices)
• Bridges (Critical Edges)
• Cycle
• Colorability
• Connectivity (graph)
• Directed Acyclic Graph (DAG)
• Types of Edges: Tree, Back, Down, Side (directed graph)
• Reachability
• Transitive Closure
• Topological Sort
• Strongly Connected Components (directed graph)
• Kernel (directed graph)
• Minimum Spanning Tree (Cartesian place, graph)
• Cut property (graph)
• Graph Separation Theorem
• String Sorting
• Substring Search
• Monte Carlo Algorithm
• Las Vegas Algorithm
• Pattern Matching
• Regular Expression: Concatenation, Disjunction, Closure?
• Kleene Star
• Language
• Epsilon Transition (NFA)
• Kleene’s Theorem
• Decision Problem
• Decidability Undecidabilty
• Tractable Intractable
• Reducibility

?

?

• Map: find, add, modify, delete, but not list
• Indexed Priority Queue: add (with priority), remove (highest priority), update
• String symbol table

?

# Data Structures

• AVL Tree
• 2-3-4 Tree
• Red-Black Tree
• Randomized BST
• Splay Tree

• Hash set
• Hash table
• Edge list (graph)
• String
• Search trie
• Ternary search trie
• Deterministic finite automata
• Non-deterministic finite automata

?

# Algorithms

• Hash codes: modular hashing, folding, mid-square, extraction
• Separate chaining
• Linear probing
• Double hashing
• Depth-first search
• Priority-first search
• Finding articulation points
• Finding bridges
• Cycle detection
• Directed depth-first search
• Warshall’s algorithm
• Kosaraju’s algorithm
• Tarjan’s algorithm
• Prim’s algorithm
• Kruskal’s algorithm
• Dijsktra’s algorithm
• Floyd’s algorithm
• Counting sort
• Key-index sorting
• Three-way quicksort
• Knuth-Morris-Pratt substring search algorithm
• DFA construction
• Boyer-Moore substring search algorithm
• Rabin-Karp fingerprint match substring search algorithm
• Thompson’s algorithm
• NFA with epsilon transitions to NFA without epsilon transitions construction
• NFA to DFA construction

?

• P
• NP

• NP-hard
• NP-complete

?

# Problems

• Halting Problem
• Traveling Salesman problem
• Boolean Satisfiability
• 3SAT
• Shortest Path
• Longest Path
• Eulerian Circuit
• Hamiltonian Circuit