## Exam II¶

### Logistics¶

The logistics for Exam II will be nearly identical to those of Exam I. It releases on ** Wednesday, 6/2 Thursday 6/3**, and will be due on

**, although it will be written for 1–2 hours.**~~Wednesday, 6/9 at 11:59pm PDT~~ Thursday, 6/10 at 11:30am PDT

**No submissions will be accepted after the Wednesday deadline**—you may not use late days on the exam! Just like Exam I, you can work solo or form groups up to 3, and you may use the same group as Exam I (although you are not required to). Also like Exam I, course staff will

**not**answer questions about exam content during the exam. Clarifying or logistical questions will still be allowed, and course staff will still help with the last programming project (P4), but note that there will

**not**be regular office hours during finals week—

**Friday, 6/4 is the last day of regularly-scheduled office hours**.

Exam II will focus heavily on content in the second half of the course (that is, content after what was tested on Exam I). However, the exam is technically cumulative in the sense that you may still need to use Exam I topics that we built on in the second half of the course. For example, you will be asked to apply certain Exam I skills like algorithmic analysis, and reason about Exam I ADTs like Lists, Stacks, Queues, and Maps.

### Review Materials¶

Just like for Exam I, we provide a number of resources for you to use as you prepare for the exam:

- 373 20au Exam II [Solutions]
- 373 20su Exam II [Solutions]
- 373 20su Exam II Practice Problem Set [Solutions]
- Lecture slides/recordings and section worksheets from the course calendar.
- All section worksheets in this course contain many more problems than are actually covered in section, intended to give you additional practice applying the course concepts. Going back and revisiting those problems can be a great way to study.

Exams from older quarters may also be useful; however, note that these exams were offered in-person, so the format and types of questions may be substantially different. We recommend using these resources only as additional practice once you’ve looked at the other resources.

- 373 20wi Final Assignment (post-midterm content)

373 20wi Final Assignment (pre-midterm content) - 373 19wi Final [Solutions]
- 373 18au Final [Solutions]

373 18au Final Practice [Solutions]

### Topics¶

Exam II will generally cover course content through Friday, 5/21. That includes the following course components:

- Lectures 15–24
- Sections 6–8
- Projects 3–4
- Exercises 3–5

The following is an approximate list of the topics you might see on Exam II:

- Sorting
- Sorting algorithm properties (stable, in-place)
- Quadratic sorts: insertion sort, selection sort
- Faster sorts: heap sort, merge sort, quick sort
- Runtimes of all of the above (in the best and worst cases)

- Graphs
- Definitions (e.g., directed, undirected, weighted, unweighted, walks, paths, cycles, self-loops, parallel edges, trees, DAGs, etc.)
- Implementations (adjacency list, adjacency matrix, and their pros and cons)
- Traversals (BFS and DFS)
- Single-source shortest-path algorithms: Dijkstra’s algorithm
- Topological sort
- MST algorithms: Prim’s and Kruskal’s
- Framing/modeling problems with graphs

- Disjoint sets
- Coding Projects
- Implementation of each data structure
- Best/average/worst-case runtimes for each method of each data structure

- Design Decisions
- Given a scenario, what ADT, data structure implementation, and/or algorithm is best optimized for your goals?
- What is unique or specialized about your chosen tool?
- How do the specialized features of your chosen tool contribute to solving the given problem scenario?
- How expensive is this tool and its features in terms of runtime and memory?
- Given a scenario, what changes might you make to a design to better serve your goals?

- Memory and Locality
- How to leverage caching

- Pre-midterm topics
- All ADTs and data structures
- Asymptotic analysis
- Code modeling (including recurrences)
- Complexity classes
- $\mathcal{O}$, $\Omega$, $\Theta$
- BSTs, AVL Trees
- Hashing
- Heaps

## Exam I¶

### Logistics¶

Exam I releases on **Friday 4/30**, and will be due on **Friday, 5/7** at **11:59pm PDT** (more info here). Although the exam is designed to be completed within 1–2 hours, you will have a week to work on it, whenever works for you. There is no shorter timer once you start working, and you will have the option to save your work and return to it over multiple sessions. **No submissions will be accepted after the Friday deadline**—you may not use late days on the exam!

The exam will be open-note and open-internet. You may form groups of up to 3 students, with whom you can collaborate freely and submit a single exam. You may also complete the exam individually if you wish, although groups are recommended so you have someone with whom to discuss your answers.

While the exam is out, course staff will not answer questions about the course content that may appear on the midterm. You can still attend office hours, but the purpose of the exam is for you to apply the learning you’ve done in this class, and the course staff **will only answer clarifying or logistical questions during office hours**—we will not help you with specific questions, review course concepts with you, or give you hints on the exam. The course staff will be closely monitoring Ed to give you a fast response in case of a technological issue.

### Resources¶

We provide a number of resources for you to use as you prepare for the exam:

- 373 20au Exam I [Solutions]
- 373 20su Exam I [Solutions]
- 373 20su Exam I Practice Problem Set [Solutions]
- Lecture slides/recordings and section worksheets from the course calendar.
- All section worksheets in this course contain many more problems than are actually covered in section, intended to give you additional practice applying the course concepts. Going back and revisiting those problems can be a great way to study.

Exams from older quarters may also be useful; however, note that these exams were offered in-person, so the format and types of questions may be substantially different. We recommend using these resources only as additional practice once you’ve looked at the other resources.

- 373 20wi Midterm Exam [Solutions]

373 20wi Midterm Practice Exam [Solutions]- Note that these exams cover a slightly different set of topics (you should skip any questions about red-black trees).

- 373 19su Midterm Solutions
- 373 19sp Midterm [Solutions]
- 373 19wi Midterm [Solutions]
- 373 18au Midterm [Solutions]

373 18au Practice Midterm [Solutions] - 373 18su Midterm Solutions [Solutions]
- 373 18sp Midterm
- 373 18wi Practice Midterm [Solutions]

### Topics¶

Exam I will generally cover course content through Wednesday, 4/28. That includes the following course components:

- Lectures 1–14
- Sections 1–5
- Projects 1–2*
- Exercises 1–2

*It is okay if you haven’t finished Project 2 before the exam. We will focus more on the conceptual practice of hashing than testing your ability to implement it from scratch.

The following is an approximate list of the topics you might see on Exam I:

- ADTs vs. Data Structures
- List, Stack, Queue, & Map ADTs
- Linked Nodes implementations,
- Making Design Decisions

- Algorithmic Analysis
- Asymptotic Analysis
- $\mathcal{O}$, $\Omega$, $\Theta$
- Case Analysis

- Recursive Algorithmic Analysis
- Recurrences
- Master Theorem
- The Tree Method

- Hash Maps
- Hashing
- Separate Chaining
- Probing

- BSTs and AVL Trees
- Invariants, specifically BST & AVL

- Priority Queues & Heaps
- Heap operations