22C:21 Computer Science II: Study Guide for Final
The final is open notes/book. It is from 2:15-4:15 in
Room 1505 SC (our classroom) on Monday, 5/8.
For the final you should read (i) your notes from lectures
and discussion sections, (ii) problem sets and their solutions,
(iii) projects and their solutions,
(iv) sample code, (v) relevant material from the textbook, and
(vi) Lafore's code.
From the text book read: Chapter 4 (exluding the material on
parsing arithmetic expressions), Chapter 6, Chapter 7 (excluding
the material on radix sort), Chapter 8 (excluding the material
on Huffman codes), Chapter 12, Chapter 13
(only pages 615-642), Chapter 14 (only pages 687-707).
The final exam is comprehensive in the sense that material covered
before the midterm such as running time analysis, linked lists,
etc. will be quite relevant.
However, the focus will be on material covered after the midterm.
A detailed list of these topics is below.
Specific topics, that the final covers, are:
- Adjacency list representation of graphs: how to
implement the methods addEdge, deleteEdge,
deleteVertex, etc. of the myGraph class
if we change the underlying representation from an adjacency
matrix representation to an adjacency list representation;
determining the running times of these methods as a function
of the number of vertices and the number of edges in the graph;
comparing these running times with corresponding running times
in the adjacency matrix implementation.
A bit of this is covered in Chapter 13 on Graphs.
- Simple examples of recursion: computing Fibonacci numbers,
linear search, binary search, etc. Drawing recursion trees that show the
execution of recursive algorithms.
- Implementing divide-and-conquer sorting algorithms using recursion:
mergeSort and quickSort, the merge function
and the partition function, and running time analysis of these
improving the running time of quickSort by using median-of-three
rule and randomization;
the recursive solution to the Towers of Hanoi problem.
Chapters 6 and 7.
- Implementing backtracking using recursion:
the knapsack problem and its solution,
the Queens problem and its solution, and
depth first traversal.
Chapters 6 and 13.
- The Stack ADT and the connection between recursion and stacks:
activation records and the system stack; translating recursive functions
into equivalent functions that make explicit use of the stack;
examples such as: the stack based fibonacci function and the
stack based solution to the Towers of Hanoi problem.
Chapters 4 and 6.
- The Queue ADT and implementing breadth-first search:
different implementations of the Queue ADT, application of the
Queue ADT to breadth first search, and computation of the breadth first search
Chapters 4 and 13.
- The PriorityQueue ADT and binary heaps:
what a binary heap is and
how the PriorityQueue ADT is implemented by a binary heap,
implementation of a binary heap using an array,
the running times of binary heap operations.
- Heap Sort and Dijkstra's shortest path algorithm:
using a binary heap to sort in O(n log n) time;
Dijkstra's shortest path algorithm and its two implementations:
one that runs in O(n^2) and the other (based on binary heaps)
that runs in O((m+n) log n) time.
Chapters 12 and 14.
- Skip lists:
how skip lists generalize the notion of linear lists, what role
randomization plays, implementation of the skip list operations.
Problem Set 12 and the links therein.
- Binary Search trees:
what a binary search tree is, the implementation of the three binary
search tree operations, and their running time.
The final contains 5 problems, each worth 40 points.