Exam II

20Au Exam II Solutions

Logistics

The logistics for Exam II will be nearly identical to those of Exam I. It will be released on Wed, 12/16 at 8:30 AM PST, and will be due on Friday, 12/18 at 8:30 AM PST, although it will be written for 1-2 hours. No submissions will be accepted after the Friday deadline – you may not use late days on the exam! Just like Exam I, you can work solo or form groups up to 6, and you may use the same group as Exam I (although you are not required to); you are also more than welcome to use the same Discord Channel as last time to find a group. Also like Exam I, we will host a modified 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.

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 [Solution]
  • 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 review (materials posted later)
  • Class session practice problems and solutions posted each day on the calendar.
  • 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 Ed or Discord, or in section.

Topics

Exam II will generally cover course content through Wednesday, 12/2. That includes the following course components:

  • Lectures 11 - 24
  • Sections 5 - 9
  • Projects 3 & 4
  • Exercises 3 - 5

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
  • B-Trees
    • Memory characteristics
    • Caching
  • 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 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)

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()

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: Topo Sort & Reductions

  • Describe the runtime for Dijkstra’s algorithm and explain where it comes from
  • Define a topological sort and determine whether a given problem could be solved with a topological sort
  • 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

LEC 18: Minimum Spanning Trees

  • Identify a Minimum Spanning Tree
  • Describe the Cut and Cycle properties must be true from the definition of an MST and explain how Prim’s Algorithm utilizes the Cut property for its correctness
  • Implement Prim’s Algorithm and explain how it differs from Dijkstra’s

LEC 19: 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

LEC 20: 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 21: Traveling Salesperson (TSP)

  • None! This was an optional lecture.

LEC 22: P vs. NP

  • None! This was an optional lecture.

LEC 23: Sorting I

  • 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 in-place variant

LEC 24: Sorting II

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

Exam I

20au Exam I 20au Exam I Sample Solutions & Explanations

Logistics

Exam I will be released on Monday 10/26 at 8:30 AM PDT, and will be due on Wednesday, 10/28 at 8:30 AM PDT 12:30 PM PDT (more info here). 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 Wednesday 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 6 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 have a modified policy for how much support we can provide in office hours and the message board. 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.

Lecture on 10/26 (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 Exam [Solution]
  • 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.
  • There will be a review session Sunday 10/25 from 6:00 pm to 8:00 pm (more info here). We will give students some time to work on this practice exam (solutions here).
  • See class session handouts/solutions for each day (linked on course calendar.
  • Previous Section Worksheets (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 our Exam 1). 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 Ed 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 - 10
  • Sections 1 - 4
  • 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,
    • 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

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