14.1. Final Exam¶
14.1.1. Final Exam Structure¶
In the regular classroom at the time specified for your section by the University.
100 points
Format
Similar to Midterms
The questions of of types that we can autograde: Multiple Choice, True/False, fill-in-the-blank, etc.
40-45 questions
While the official time available is 2 hours, the exam is not too much longer than the midterms.
Anything covered during the semester is fair game, but the focus is on material not covered in the midterms, plus some integration questions.
14.1.2. Topics (1)¶
Section 7.17-18: Huffman Coding Trees
An example of a Full Binary Tree, and a Trie
Chapter 9: File Processing
Fundamental differences between RAM and peripheral storage, and how they affect performance and program implementation.
Buffer pools: How they work and the LRU replacement algorithm
External Sorting principles
Chapter 11: Memory Management
Sequential Fit methods: First Fit, Circular First Fit, Best Fit, Worst Fit
Buddy Method
Failure policies and garbage collection
14.1.3. Topics (2)¶
Chapter 12: Indexing
What is an index?
Linear Indexing
Principles of tree-based indexing (goals to minimize disk accesses)
2-3 Trees and B-trees
Focus on B+ Trees.
Know the basic algorithms for insert and delete.
Chapter 13: General Trees
Union/FIND algorithm and what it is used for
General tree representations
Sequential tree representations and serialization
14.1.4. Topics (3)¶
Chapter 14: Graphs
Representations: Adjacency Matrix and Adjacency List
Graph Traversals: Depth First and Breadth First
Topological Sorting (two algorithms)
Shortest Paths problems
Single-source shortest paths: Dijkstra’s algorithm (and two approaches to implementing minVertex)
All-pairs Shortest Paths: Floyd’s Algorithm
Minimal Cost Spanning Trees: Prim’s Algorithm (similar to Dijkstra’s algorithm) and Kruskals’s algorithm (uses Union/FIND)
Chapter 15
Skip Lists: Randomized Algorithm
(You don’t need to know the spatial data structures)
14.1.5. Topics (4)¶
Integration questions:
Be prepared for questions that ask about what is the best data structure or algorithm for a given situation.
In particular, know when is the most appropriate time to use various search structures like Hash Tables, BSTs, Linear Index, B-tree.
