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 is.

• Queue data structure: What operations are supported by the queue data structure; how it is used to implement breadth-first-search.