22C:30, 22C:115 Review for Exam 2
Exam 2 is scheduled for Friday, October 31st, from 10:30 to 11:20 in
Room 321, CB
Given below is a detailed list of topics that you should study for Exam 2.
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 node class
and linked list toolkit, graph class, solution to Project 1 and Homework 2,
etc.) and (iii) the following material from the textbook:
Sections 2.5 and 4.1 (on recursion), Section 4.3 (on Queues),
Section 4.4 (on Linked Lists), Sections 10.1 and 10.3 (Merge Sort and
Quick Sort), 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.
- Linked lists: How to define singly linked lists, doubly linked
lists, circular linked lists; how to perform operations such as insert,
delete, search, and clear on these data strcutures.
- Adjacency list representation: How linked lists can be
used to define the adjacency list representation for graphs; why
the adjacency list representation is often more efficient than the
adjacency matrix representation; how to perform graph operations such
as add-vertex, delete-vertex, add-edge, delete-edge, and get-neighbors
using the adjacency list representation.
- Hash tables: What a hash table is; how it can be
implemented using an array of linked lists; and how operations such
as insert, delete, and search can be performed on hash tables.
- Recursion for divide-and-conquer: How the "divide-and-conquer"
paradigm is used to design the merge sort and the quick sort algorithms;
how recursion is used to easily implement these functions.
- Recursion for enumeration: How recursion can be used to enumerate
objects such as all permutations or all subsets of a given set.
- Recursion for search with backtracking: How recursion can be
used to solve problems that involve search with backtracking such as
the 8-queens problem; how recursion can be used to implement a graph traversal
such as depth-first-search.
- Graph traversals: How graph traversals such as depth-first-search
and breadth-first-search work; what the difference between the two traversals
- Queue data structure: What operations are supported by the queue
data structure; how it is used to implement breadth-first-search.