Table of Contents

Exams

The course staff will scan, upload and grade exams on Gradescope .

1 Exam 1

The Midterm Exam will be held on Wednesday July 22 during our normal lecture session.

We will hold a review session on Monday July 20 at 5:00pm in Sieg 134.

1.1.1 Midterm Solutions

Sample solutions: pdf

1.2 Policies

Closed book, closed notes except for a 1-page 2-sided reference sheet of your own creation.
No calculators, cell phones, or other electronic devices allowed.
No writing after time is called, make sure you put your name on your paper first.
You will be provided a math reference sheet during the exam.

1.3 Content

The exam will cover all material from the beginning of the quarter up through AVL Trees. This includes:

Abstract Data Types and Data structures:
- Their Definitions and Differences
- Examples
Stacks and Queues:
- Array and Linked List implementations and running times
- ADT Operations
Asymptotic Complexity:
- Definition of big-oh, big-omega, big-theta
- Identifying whether f(n) belongs to O(g(n)) (or big-omega, big-theta)
- Finding constants c and n0 to demonstrate this
- Identifying running times (best case and worst case) of example code
Recurrence Relations:
- Given a recurrence relation, solve it to closed form
Priority Queues:
- ADT operations (insert, findMin, extract, increaseKey, decreaseKey, remove)
- The Heap data structure (including the heap property, complete tree, and buildHeap)
Trees:
- Definitions of height, branching factor
- Preorder, Inorder, Postorder traversals of binary trees
Dictionaries:
- ADT operations
- Binary Search Trees: Definition, algorithms and running times of dictionary operations
- AVL Trees: Definition, algorithms and running times of dictionary operations (including the definition of rotations and when to do them).

1.4 Past Exams

Below I have several quarters’ midterm exams. Be advised that the question style, length, difficulty, and content may differ among quarters. Most notably, prior to autumn 2024 the course included two additional data structures on the midterm exam – Tries and B-Trees.

Overall, here is how I would recommend that you use these sample exams to prepare.

First, study on your own without using any of the provided sample exams. To do this, review the exercises, lecture slides, and section materials. If there are things included in these that you find confusing or do not recall, seek clarification. This can be done by reviewing lecture recordings, talking with classmates, or attending office hours.
Next, use the past exams below to evaluate your preparedness. Attempt some problems, then compare your answer against the solution provided. If they differ, try to diagnose whether your answer is equally valid, or else where you may have a misconception (you’re welcome to come to office hours for help!).
Once you are confident with your ability to answer questions in the past exams, take the practice exam above as a simulation of the actual exam (so create your reference sheet and then set aside a 50 minute block of time to take the exam from start to finish). Then trade exams with a friend so that they can compare your solutions to the answer key and give you feedback.
Use this feedback to decide where to review.

Past Exams:

2 Exam 2

The Final Exam will be held at 5:00pm-7:00pm on Thursday, August 20, in Sieg 134. An alternate time slot of 8:40am-10:40am Friday, August 21, will be available for those with an unavoidable time conflict.

A review session for the Final Exam will be held Tuesday, August 18, from 5:00pm-7:00pm (likely in Sieg 134, but pending confirmation).

2.1 Policies

Closed book, closed notes except for two 1-page 2-sided reference sheets of your own creation.
No calculators, cell phones, or other electronic devices allowed.
No writing after time is called, make sure you put your name on your paper first.
You will be provided a reference sheet during the exam.

2.2 Content

The final exam is cumulative, and as such all midterm exam content (listed above) is eligible for testing on the final exam.

In addition to the midterm exam content, the final exam will cover:

Hash Tables
- Principles of good hash function design
- Insert/Delete/Find using these collision resolution strategies:
  - Separate Chaining
  - Linear Probing
  - Quadratic Probing
  - Double Hashing
- Strengths and weaknesses of each collision resolution strategy
- Load Factor, including how to calculate it and how it interacts with collision resolution
- Rehashing
Sorting
- Definitions, procedures, running times, and other properties of these algorithms:
  - Insertion Sort
  - Heap Sort
  - Merge Sort
  - Quick Sort
  - Bucket Sort
  - Radix Sort
Graphs
- The definitions of the many terms presented in the graphs section, including:
  - node/vertex
  - edge, edge weight
  - directed/undirected graph
  - (in/out) degree
  - complete graph
  - simple graph
  - path, simple path, and cycle
  - connected graph
  - DAG
  - tree
  - Any other definitions presented in the slides
- Graph data structures (adjacency list, adjacency matrix) and the advantages and disadvantages of each.
- Graph Traversals (breadth-first search and depth-first search)
- Dijkstra’s Algorithm
- Prim’s algorithm and Kruskal’s Algorithm
Parallelism:
- ForkJoin Parallelism
- Efficiency analysis (including work, span, perfect linear speedup, and Amdahl’s Law)
- ForkJoin applications:
  - Reduce: Parallel sum, max, find, etc.
  - Map: vector addition, function application, etc.
- Two-Pass parallel algorithms, e.g. Parallel Prefix Sum
- Parallel Filter/Pack
Concurrency
- Race Conditions:
  - Data Races
  - Bad Interleavings
- Code Synchronization:
  - Locks, reentrant locks
  - Java’s Synchronized statement
  - Lock scheme granularity (coarse vs. fine)
  - Critical section size
  - Deadlock
Complexity: P, NP, EXP, basic Reductions.

Note: You will may be asked to write java code using ForkJoin and/or threads. We will not require your syntax to be perfectly correct, but it should be correct enough that we can verify your code would be correct if you had access to an IDE to highlight any syntax issues that were present. That is, we expect major algorithmic steps and edge casesto be correct, but don’t necessarily expect all keywords or semicolons to be perfect.

2.3 Past Exams

We have provided links to past exams below. Be advised that in other quarters the final exam has included P/NP content. Your final exam for this quarter will not include that material. Additionally, in some previous quarters Hashing was covered on the midterm, and so the quantity of that content on the exams varies. You may also find some minor topics that we did not cover in these exams. If something seems unfamiliar, check if that topic appears in the list of content above. I recommend that you mostly use these exams to evaluate your preparedness rather than as a study guide.