22C:30, 22C:115 Review for Final Exam
The final exam is scheduled for Wednesday, Decenmber 17th, from 9:45 to 11:45 in
Room 321, CB
Given below is a detailed list of topics that you should study for the final Exam.
The problems on the exam will involve (i) answering questions about small code
fragments that are given and (ii) writing small code fragments to perform a
specific task. You will not be asked to write large functions or entire classes.
To prepare for the exam read (i) lecture notes and notes from discussion
sections, (ii) code posted on the course webpages (including the
solutions to Project 2 and Homework 3, Homework 3 extra credit,
etc.) and (iii) the following material from the textbook:
Chapter 3 (on running time analysis), Sections 2.5 and 4.1 (on recursion),
Chapter 6 (on trees and tree traversals), Sections 7.1, 7.2, and 7.3 (on
priority queues and heaps), Sections 9.1 and 9.2 (on binary search trees and AVL trees),
Sections 10.1 amd 10.3 (on Quick sort and Merge sort), and
Sections 12.2 and 12.3 (graph representation and DFS, BFS).
In general, focus on material that relates to what was discussed in class
and in the discussion sections.
As should be clear from the above list of topics, the primary focus of the exam
will be material covered after the second mid-term.
However, you should also review a few topics from prior to the second mid-term; these are
recursion, graphs, BFS, DFS, and sorting algorithms,
- Recursion: How recursion is used to implement divide-and-conquer algorithms;
how recursion is used in algorithms that use search with backtracking; how recursion
is implemented in most high level langauges using stacks of activation records.
Interesting examples of recursive functions such as: merge sort, quick sort, depth-first search,
tree traversals, etc.
- Running Time Analysis: The "Big Oh" notation; worst case vs best case vs average
case running time; useful sums (arithmetic series and geometric series); examples of
analysis involving nested loops, recursive functions, etc.
- Binary Trees: Representing trees; the three tree traversal algorithms (pre-order,
in-order, and post-order); height and depth of trees.
- Binary Search Trees: Definition; implementing search, insert, and delete on binary search trees;
worst case running time of these algorithms.
- AVL Trees: Definition; implementing search, insert, and delete on AVL trees;
the single rotation and the double rotation operation.
- Priority Queues and Binary Heaps:
What is the priority queue ADT? How is this ADT implemented using a binary heap?
on the operations min, insert, and delete on heaps; analysis of the worst case
running time of these operations.
- Graph traversals: How graph traversals such as depth-first-search
and breadth-first-search work; what the difference between the two traversals
is.