Exams

Exam II¶

20Su Exam II 20Su Exam II Sample Solutions & Explanations

Logistics¶

The logistics for Exam II will be nearly identical to those of Exam I. It will be released on Friday, 8/21 at 12:01 AM PDT, and will be due on Saturday, 8/22 at 11:59 PM PDT, although it will be written for 1-2 hours. No submissions will be accepted after the Saturday deadline – you may not use late days on the exam! Just like Exam I, you can work solo or form groups up to 8, and you may use the same group as Exam I (although you are not required to). Also like Exam I, we will still hold office hours but the course staff will only answer clarifying or logistical questions during office hours because the purpose of the exam is for you to apply the learning you’ve done in this class.

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.

Based on your feedback from Exam I, for Exam II we will create a single centralized Piazza post with all clarifications so you can easily check to make sure you’re fully up-to-date. Lecture on 8/21 will not include any new material: instead, it will be used as additional office hours to answer logistical and clarifying questions about the exam.

Review Materials¶

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

• 373 20su Exam II Practice Problem Set [Solutions] (Written/adapted this quarter to approximate the style of our Exam II). This problem set is intended to give you a rough idea of the kinds of skills you can expect to demonstrate on the exam. Please note that it is not necessarily meant to be representative of the exam length or difficulty.
• Section 9 Final Review Worksheet [Solutions will be posted after section 9]. This worksheet gives a large number of different problems covering most of the topics on the exam.
• Post-Lecture Review Questions & Solutions. These problems, published after many of the lectures this quarter, are designed to give extra practice with the material and especially tend toward the conceptual side, which you should expect to see on the exam.
• Previous Section Worksheets & Section Review Videos (linked on 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.
• The 19au Final Exam [Solutions]. Note that this exam was prepared for a different quarter, and therefore covers a different set of topics. In particular, note that in 20su we did not cover Red-Black trees (we covered AVL trees instead) and our final exam will be less cumulatively-focused than the one from 19au. This exam was also offered in-person, so the format and types of questions may be substantially different. We recommend using this resource only as additional practice once you’ve looked at the other resources.

The best way to start preparing for the exam is to refer to the Learning Objectives listed at the beginning of each lecture, which provide a roadmap of the skills you can expect to see on the exam. Then, you can practice those skills by completing problems from the resources above – we recommend starting with the Post-Lecture Review Questions.

You don’t just have to ask homework questions in office hours – the course staff is always happy to help you review the course concepts! Feel free to talk to us about concepts or review questions in office hours, on Piazza or Discord, or in section.

Topics¶

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

• Lectures 12 - 22
• Sections 6 - 9
• Projects 3 & 4
• Exercises 3 & 4

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

• ADTs & Data Structures
  • List, Stack, Queue, Map, PriorityQueue, & DisjointSets ADTs
• PriorityQueues & Heaps
  • Heap operations
  • Implementing a Heap
  • Floyd’s buildHeap
• Graphs
  • Properties of Graphs (e.g. Directed/Undirected, Weighted/Unweighted, etc.)
  • Implementing a Graph
  • Graph Modeling
• Graph Problems
  • s-t Connectivity
  • Unweighted/Weighted Shortest Paths
  • Minimum Spanning Trees
• Graph Algorithms
  • BFS & DFS
  • Dijkstra’s Algorithm
  • Prim’s & Kruskal’s Algorithms
• Disjoint Sets
  • Implementing a Disjoint Set: QuickFind vs. QuickUnion
  • QuickUnion optimizations: Weighted, Path Compression, Using an array
• Sorting
  • Properties of Sorts: Stable, In-Place
  • Insertion sort & Selection sort
  • Heap sort, Merge sort, & Quick sort

Learning Objectives¶

The following is a list of the learning objectives associated with each lecture that form roughly the set of skills you’ll be asked to demonstrate on Exam II:

LEC 12: PQs & Heaps

• Identify use cases where the PriorityQueue ADT is appropriate
• Describe the invariants that make up a heap and explain their relationship to the runtime of certain heap operations
• Trace the removeMin(), and add() methods, including percolateDown() and percolateUp()
• Describe how a heap can be stored using an array, and compare that implementation to one using linked nodes

LEC 13: Heaps II, Interviews

• Describe how a heap can be stored using an array, and compare that implementation to one using linked nodes
• Recall the runtime to build a heap with Floyd’s buildHeap algorithm, and describe how the algorithm proceeds

LEC 14: Graphs

• Categorize graph data structures based on which properties they exhibit
• Select which properties of a graph would be most appropriate to model a scenario (e.g. Directed/Undirected, Cyclic/Acyclic, etc.)
• Compare the runtimes of Adjacency Matrix and Adjacency List graph implementations, and select the most appropriate one for a particular problem
• Describe the high-level algorithm for solving the s-t Connectivity Problem, and be prepared to expand on it going forward

LEC 15: BFS, DFS, Shortest Paths

• Implement iterative BFS and DFS, and synthesize solutions to graph problems by modifying those algorithms
• Describe the s-t Connectivity Problem, write code to solve it, and explain why we mark nodes as visited
• Describe the Shortest Paths Problem, write code to solve it, and explain how we could use a shortest path tree to come up with the result

LEC 16: Dijkstra’s Algorithm

• Describe the weighted shortest path problem and explain why BFS doesn’t work to solve it
• Trace through Dijkstra’s algorithm on a graph showing intermediate steps at each step and implement Dijkstra’s algorithm in code (P4)
• Evaluate inputs to (and modifications to) Dijkstra’s algorithm for correct behavior and efficiency based on the algorithm’s properties
• Synthesize code to solve problems on a graph based on DFS, BFS, and Dijkstra’s traversals

LEC 17: Minimum Spanning Trees

• Describe the runtime for Dijkstra’s algorithm and explain where it comes from
• Identify a Minimum Spanning Tree, and explain why the Cut and Cycle properties must be true from the definition of an MST
• Implement Prim’s Algorithm and explain how it differs from Dijkstra’s
• Describe Kruskal’s Algorithm at a high level, explain why it works, and describe why it needs a new ADT

LEC 18: Disjoint Sets I

• Describe Kruskal’s Algorithm, evaluate why it works, and describe why it needs a new ADT
• Compare and contrast QuickUnion with QuickFind and describe how the two structure optimize for different operations
• Implement WeightedQuickUnion and describe why making the change protects against the worst case find runtime
• Describe path compression at a high level and argue for why it improves runtimes despite not following an invariant

LEC 19: Disjoint Sets II

• Implement WeightedQuickUnion and describe why making the change protects against the worst case find runtime
• Implement path compression and argue why it improves runtimes, despite not following an invariant
• Describe what contributes to the runtime of Prim’s and Kruskal’s, and compare/contrast the two algorithms
• Implement WeightedQuickUnion using arrays and describe the benefits of doing so

LEC 20: Sorting I

• Implement the DisjointSets ADT as WeightedQuickUnion + PathCompression using an array, and describe its benefits
• Define an ordering relation and stable sort and determine whether a given sorting algorithm is stable
• Implement Selection Sort and Insertion Sort, compare runtimes and best/worst cases of the two algorithms, and decide when they are appropriate
• Implement Heap Sort, describe its runtime, and implement the inplace variant

LEC 21: Sorting II

• Implement Heap Sort, describe its runtime, and implement the in-place variant
• Implement Merge Sort, and derive its runtimes
• Evaluate the best algorithm to use based on properties of input data (already sorted, multiple fields, etc.)

LEC 22: Topo Sort & Reductions

• Implement Quick Sort, derive its runtimes, and implement the in-place variant
• Define a topological sort and determine whether a given problem could be solved with a topological sort
• Write code to produce a topological sort and identify valid and invalid topological sorts for a given graph
• Explain the makeup of a reduction, identify whether algorithms are considered reductions, and solve a problem using a reduction to a known problem

Exam I¶

20Su Exam I 20Su Exam I Sample Solutions & Explanations

Logistics¶

Exam I will be released on Friday, 7/24 at 12:01 AM PDT, and will be due on Saturday, 7/25 at 11:59 PM PDT. Although the exam is designed to be completed within 1-2 hours, you will have the full 48 hours 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 Saturday 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 8 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, we will hold a modified office hours schedule. 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 email and Piazza to give you a fast response in case of a technological issue.

Lecture on 7/24 (the day the exam is released) will not include any new material: instead, it will be used as additional office hours to answer logistical and clarifying questions about the exam.

Review Materials¶

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

• 373 20su Practice Problem Set [Solutions] (Written/adapted this quarter to approximate the style of our Exam I). This problem set is intended to give you a rough idea of the kinds of skills you can expect to demonstrate on the exam. Please note that it is not necessarily meant to be representative of the exam length or difficulty.
• Section 5 Midterm Review Worksheet [Solutions will be posted after section 5]. This worksheet gives a large number of different problems covering most of the topics on the exam.
• Post-Lecture Review Questions & Solutions. These problems, published after many of the lectures this quarter, are designed to give extra practice with the material and especially tend toward the conceptual side, which you should expect to see on the exam.
• Previous Section Worksheets & Section Review Videos (linked on 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.
• The 20wi Midterm Exam [Solutions] and Practice Exam [Solutions]. Note that these exams were prepared for a different quarter, and therefore cover a slightly different set of topics (you should skip any questions about red-black trees, and please note that heaps are not included on the 20su exam). These exams were also 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.

The best way to start preparing for the exam is to refer to the Learning Objectives listed at the beginning of each lecture, which provide a roadmap of the skills you can expect to see on the exam. Then, you can practice those skills by completing problems from the resources above – we recommend starting with the Post-Lecture Review Questions.

You don’t just have to ask homework questions in office hours – the course staff is always happy to help you review the course concepts! Feel free to talk to us about concepts or review questions in office hours, on Piazza or Discord, or in section.

Topics¶

Exam I will generally cover course content through Friday, 7/17. That includes the following course components:

• Lectures 1 - 11
• Sections 1 - 5
• Projects 1 & 2
• Exercises 1 & 2

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,
  • Deques
  • Making Design Decisions
• Algorithmic Analysis
  • Asymptotic Analysis
  • Big-Oh, Big-Omega, Big-Theta
  • Case Analysis
• Recursive Algorithmic Analysis
  • Recurrences
  • Master Theorem
  • The Tree Method
• Hash Maps
  • Separate Chaining
  • Hashing
• BSTs and AVL Trees
  • Invariants, specifically BST & AVL
  • AVL Rotations
• B-Trees
  • Memory characteristics
  • Caching

Learning Objectives¶

The following is a list of the learning objectives associated with each lecture that form roughly the set of skills you’ll be asked to demonstrate on Exam I:

LEC 02: Lists

• Determine whether simple code belongs to the constant, linear, or quadratic complexity classes
• Distinguish the List ADT from ArrayList and LinkedList implementations
• Compare the runtime of certain operations on ArrayList and LinkedList, based on how they’re implemented
• Describe the process of making design decisions

LEC 03: Stacks, Queues, Maps

• Describe the state and behavior for the Stack, Queue, and Map ADTs
• Describe how a resizable array or linked nodes could be used to implement Stack, Queue, or Map
• Compare the runtime of Stack, Queue, and Map operations on a resizable array vs. linked nodes, based on how they’re implemented
• Identify invariants for the data structures we’ve seen so far

LEC 04: Asymptotic Analysis

• Describe the difference between Code Modeling and Asymptotic Analysis (both components of Algorithmic Analysis)
• Model a (simple) piece of code with a function describing its runtime
• Explain why we can throw away constants when we compute BigOh bounds
• Identify whether Big-Oh (and Big-Omega, Big-Theta) statements about a function are accurate

LEC 05: Oh/Omega/Theta, Case Analysis

• Differentiate between Big-Oh, Big-Omega, and Big-Theta
• Come up with Big-Oh, Big-Omega, and Big-Theta bounds for a given function
• Perform Case Analysis to identify the Best Case and Worst Case for a given piece of code
• Describe the difference between Case Analysis and Asymptotic Analysis

LEC 06: Recurrences I, Master Theorem

• Distinguish between Asymptotic Analysis & Case Analysis, and apply both to code snippets
• Describe the 3 most common recursive patterns and identify whether code belongs to one of them
• Model recursive code using a recurrence relation (Step 1)
• Use the Master Theorem to characterize a recurrence relation with Big-Oh/Big-Theta/Big-Omega bounds (Step 2)

LEC 07: Recurrences II, Tree Method

• (Continued) Describe the 3 most common recursive patterns and identify whether code belongs to one of them
• Model a recurrence with the Tree Method and use it to characterize the recurrence with a bound
• Use Summation Identities to find closed forms for summations (Non-Objective: come up with or explain Summation Identities)

LEC 08: Hash Maps

• Compare the relative pros/cons of various Map implementations, especially given a design like the ones we cover today
• Trace operations in a Separate Chaining Hash Map on paper (such as insertion, getting an element, resizing)
• Implement a Separate Chaining Hash Map in code
• Differentiate between the “worst” and “in practice” runtimes of a Separate Chaining Hash Map, and describe what assumptions allow us to consider the “in practice” case

LEC 09: BSTs, AVL Trees

• Describe the properties of a good hash function and the role of a hash function in making a Hash Map efficient
• Evaluate invariants based on their strength and maintainability, and come up with the invariants for data structure implementations

LEC 10: AVL Trees

• (Continued) Evaluate invariants based on their strength and maintainability, and come up with invariants for data structure implementations
• Describe the AVL invariant, explain how it affects AVL tree runtimes, and compare it with the BST invariant
• Compare the runtimes of operations on AVL trees and BSTs
• Trace AVL rotations and explain how they contribute to limiting the height of the overall tree

LEC 11: Memory & Caching, B-Trees

• Contrast the CPU, RAM, the cache, and Disk in terms of their storage space and the time to access them
• Explain why arrays tend to lead to better performance than linked lists, in terms of spatial locality
• Describe how B+ Trees help minimize disk accesses and trace a get() operation in a B+ Tree (Non-objective: Be able to construct, modify, or explain every detail of a B+ Tree)