Topics for the Final Exam

The final is open book, open notes, calculators allowed, but no computers. Schedule the exam through distance education services! The emphasis is on the second half of the class, but this means knowing concepts from the first half (e.g. recurrence relations, Big-O, etc.)

Linked Data Structures

• Concepts and in building practice (C++, Java)
• Linked list
• Add to list, remove from list, insert into list, delete all items in a list
• Queue
  • First-In First-Out
  • Enqueue, Dequeue
• Stack
  • Last-In First-Out
  • Push, Pop, Peek
• Binary Search Trees
  • Recursively traversing the tree; in-order traversal
  • How to delete and insert and search; idea of a BST for efficiently storing key/value pairs
  • Worst and best-case scenarios for building and runtime
• Balanced BST
  • How to do rotations, left or right
  • How a Treap works; how to insert or delete from the treap
  • Expected runtime for insert, delete, and find

Hash Tables

• General concepts behind a hash table and idea of efficiently looking up key/value pairs (but maybe not storing efficiently)
• Properties of a good hash function
• How to handle collisions
  • chaining
  • probing
  • double hashing
• Expected runtime

Disjoint Sets

• Simple implementations using arrays or linked lists
• Disjoint set forest
  • Why path compression and union by rank help
  • Idea of amortized runtime

Graphs

• Basic concept, edges, vertices, relationship
• Directed, Undirected
• Adjacency List vs. Adjacency Matrix, advantages/disadvantages
• Breadth First Search
• Algorithm, Purpose, space/time behavior
• Run on a graph, be able to identify when it may be useful
• Depth First Search
• Algorithm, Purpose, space/time behavior
• Run on a graph, be able to identify when it may be useful
• Detecting cycles
• DAG, Directed Acyclic Graph
• Topological sort using DFS
• Minimum Spanning Tree
• Demonstrate Kruskal and Prim's algorithms
• Runtime
• Data structures required for each
• Practical uses of MST
• Dijkstra's Shortest Path Algorithm
• Limitations
• Runtime
• Demonstrate on a graph

STL and Java Collections

• Using STL vector, map, set
• Using Java Collections Arraylist, Map