Exam II

Gradescope assignment link

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 Wednesday, 6/9 at 11:59pm PDT Thursday, 6/10 at 11:30am PDT, although it will be written for 1–2 hours. 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:

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.

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
    • O\mathcal{O}, Ω\Omega, Θ\Theta
    • BSTs, AVL Trees
    • Hashing
    • Heaps

Exam I

Gradescope assignment link

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:

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.

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
    • O\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