1 Exams

The midterm exam will be held Monday November 9, 2026 5-6pm in Smith 120 (Lecture A) and Smith 205 (Lecture B). The final exam will be held Thursday December 17, 2026 12:30-2:20pm in BAG 131 and BAG 154 (we will tell you which room to go to).

1.1 Midterm Exam

The midterm exam will be held Monday November 9, 2026 5-6pm in Smith 120 (Lecture A) and Smith 205 (Lecture B).

  • Lecture A: Smith 120
  • Lecture B: Smith 205

You MUST go to the room for the Lecture you are REGISTERED for.

We will hold a review session on Friday November 6 during our regular lecture slots.

Lecture will NOT meet on Monday Nov 9.

1.1.1 Policies

  1. Bring a photo ID with you to the exam.
  2. Closed book, closed notes.
  3. No calculators, cell phones, or other electronic devices allowed.
  4. Writing after time has been called will result in a loss of points on your exam. Be sure to put your name on your paper first.
  5. You will be provided a math reference sheet during the exam.

1.1.2 Content

All material from the course from lecture 1 up to and including AVL trees is fair game. Hashing and sorting will NOT be on the midterm. Check the lecture calendar for links to all slides used in class, as well as readings for each topic. 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:
    • Examine recursive code and give a recurrence relation
    • Given a recurrence relation, solve it to closed form
  • Priority Queues:
    • ADT operations (insert, findMin, deleteMin, increaseKey, decreaseKey, remove)
    • The Heap data structure (including the heap property, complete tree, and buildHeap)
    • Run-times for all the above, using the array representation described in lecture.
  • Trees:
    • Definitions of height, depth
    • Preorder, Inorder, Postorder traversals of binary trees
  • Dictionaries:
    • ADT operations: Find, Insert, Delete
    • 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). The delete operation for AVL Trees will NOT be covered.

Hashing and Sorting will NOT be covered on the 26au midterm.

Note that you may be required to write pseudocode, but it will be evaluated as an algorithm, not as valid Java (or whatever) code. You will NOT be tested on Java Generics.

1.1.3 Past Exams

Below we have posted several quarters’ midterm exams to help with your studying. Be advised that the question style, length, difficulty, and content may differ among quarters. Most notably, prior to autumn 2024 the course sometimes included two additional data structures on the midterm exam – Tries and B-Trees. Our hope is that these exams will be useful in your studying, but you should NOT take them as a guarantee of exactly what your exam will be like this quarter.

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, select a couple old exams to take as a simulation of the actual exam (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: