COS 265 Exam Study Guide

There will be two exams for this semester: a mid-term oral exam and a final paper exam. Both will take place in person and without resources (no books, notes, IDEs, internet, AI, etc).

Oral	2026 Oct 21–30	30min	Euler 206
Final	2026 Dec 15	08:00–10:00	Nussbaum 101

The following sections provide a general outline of the types of questions, topics, and concepts that may appear on the exams. Use this collection of notes, bottom lines, key points, remarks, etc. as a study guide for the exams. The exam will have questions pertaining to the material covered in lectures, book readings, and projects. See the corresponding course slides, book materials, assignments, and so on if you are not confident on any of the topics or notes.

While we do not have time for an exhaustive and comprehensive exam (and I would not want to put you through that nor would I want to grade that), you are still responsible for understanding the material.

Exam Structure

The oral exam is structured to simulate a technical interview. Some of the questions might involve stepping through a snippet of code, explaining how a data structure works, providing details on an algorithm, etc. The oral exam will take no more than 30 minutes. I will have multiple 30 minute timeslots available for you to sign up starting Wed 2026.10.21 in Euler 206. You will have a maximum of 30 minutes to clearly communicate your level of understanding of the material. Sign up to take the oral exam in 2026 Oct 21–30 at dr-denning.youcanbook.me.

The final exam is structured similarly to a standardized test like the GRE or ETS. There will be a variety of problem types, such as multiple choice, true or false, and short answer. The final exam will take place during the regularly scheduled final exam time, Tue 2026.12.15 08–10 in Nussbaum 101, taking no more than 2 hours.

The examinations category accounts for 25% of the final course grade. Your exam category score will be the better of the two exam scores.

Your task is to convince me that you are a young but competent computer scientist!

Critical Thinking Skills

• CT00 Asking Good Questions
• CT01 Consulting an Expert
• CT02 Edge/Extreme Cases
• CT03 Similar Problems, Fewer Variables
• CT04 Developing Subgoals

book website

Exercises and further explanations are available from the book's website. Review the pages below.

• 1 Fundamentals
  • 1.1 Programming Model
  • 1.2 Data Abstraction
  • 1.3 Bags, Queues, and Stacks
  • 1.4 Analysis of Algorithms
  • 1.5 Case Study: Union-Find
• 2 Sorting
  • 2.1 Elementary Sorts
  • 2.2 Mergesort
  • 2.3 Quicksort
  • 2.4 Priority Queues
  • 2.5 Applications
• 3 Searching
  • 3.1 Elementary Symbol Tables
  • 3.2 Binary Search Trees
  • 3.3 Balanced Search Trees
  • 3.4 Hash Tables
  • 3.5 Applications
• 4 Graphs
  • 4.1 Undirected Graphs

General

• defn algorithm (not piece of code)
• defn data structure (not chunk of memory)
• explain difference: api and implementation
  • what is the benefit of having many implementations for a single api?
  • what is the danger of having many implementations for a single api?
• java
  • what does an interface provide?
  • what are objects? what are classes?
  • why is data abstraction a good thing? provide an example
  • what does static mean?
  • what is difference between int and Integer, double and Double, boolean and Boolean, etc.?
• what are the steps to developing a usable algorithm? how is this the scientific method?
• UML class diagrams
  • have basic understanding of simple UML class diagrams
    • class name, data members (attributes), object functions (methods)
    • class decorator (<<interface>>)
    • relationships between classes: implements, extends
    • member visibility (public:+, private:-)
  • be able to write Java code that matches a basic UML class diagram
  • be able to draw a basic UML class diagram that matches Java code
• user-defined equals(), compareTo(), Comparable
• define and explain how useful and why important
  • rank, floor, ceiling
  • binary tree, complete binary tree
  • immutability
• tree traversal: pre, in, post, level
• explain the following quote below by Eric S. Raymond.

“

Smart data structures and dumb code works a lot better than the other way around.
–Eric S. Raymond

”

Fundamentals (chapter 1)

union-find (1.5)

• what is the dynamic connectivity problem?
• what is an example/application of union-find?
• reflexive, symmetric, transitive
• how is union-find modeled?
• what if union-find was generic collection rather than using abstract integers \([0,N)%]\)? how would this change the runtime and space complexity of problem?

analysis (1.4)

• why should we care about analyzing algorithms?
• why is it generally frowned upon (in this class) to import and use additional libraries?
• know complexity curves/classifications, have example for each: constant, logarithmic, linear, linearithmic, quadratic, cubic, exponential, factorial
• be able to estimate complexity of algorithm based on its structure (assignment, for loop, two nested for loops, etc.)
• doubling hypothesis: what is it? why is it useful? when is it useful/not useful?
• tilde notation: \(\sim a N^b\)
  • what is \(a\)? what is \(N\)? what is \(b\)? what does each depend on?
• "no excuse for not running experiments to understand costs"
• alan turing suggested that it's acceptable to count only the operations essential to the algorithm rather than every single operation. why is this important?
• what is the difference between big-oh (\(O\)) notation and tilde (\(\sim\)) notation?
• see and understand summary slides!
• be able to estimate memory usage of different data types or classes. (i will provide a table with each primitive and its byte usage)
• how can caching affect runtimes?
• defn: amortized analysis

collections (1.3)

• difference between stack, queue, priority queue, randomized queue, symbol table, set/bag, ...
  • where are items added? removed? which item is most efficient to remove?
• how to represent / implement with different elementary data structures (ex: list or array)
  • pros/cons/applications for each data structure
  • what are the differences in runtime and space complexities
• defn: underflow, overflow, data loitering (be able to describe when each of these may happen or how to handle these properly)
• generics
  • why is it better to use generics rather instead of casting to Object?
  • why is it better to use generics rather than having an implementation for each type?
  • why are generic collections not always great for primitive types?
• defn: iterator, iterable (why is it important for a collection to be iterable?)
• java.util.ArrayList implements List interface, which provides a rich API. why is this a problem?
• stack-based calculator
• implementation of binary tree
  • how to implement as linked nodes vs. array?
  • what is necessary for these to work?
  • runtime and space analysis

sorting (chapter 2)

sorting and shuffling (2.1, 2.2, 2.3)

• defn: stable sorting (which algorithms are stable?)
• defn: total order
  • antisymmetry, transitivity, totality (give examples or counter-examples)
• Comparable and Comparator interfaces
• features, invariants, key parts of sorting algorithms: selection sort, insertion sort, shellsort
• shuffling
• lower-bound runtime for any sorting algorithm
• defn: lower bound, upper bound, optimal algorithm

priority queues (2.4)

• definition
• minimum pq vs. maximum pq
• binary heap
  • invariants
  • what does "just enough" ordering mean
  • how to represent as array
  • how to insert and delete (how to maintain binary heap)
  • considerations of binary heap
• properties of multiway heaps

searching (chapter 3)

symbol tables (3.1)

• definition
• using different representations (simple: seq search, bin search)
  • how to implement each operation
  • runtime of ops

binary search trees (3.2)

• definition
• invariants
• how to find min, max, rank, floor, ceiling
• delete min, max, arbitrary
• implement as linked nodes vs. array
  • runtime and space analysis
• best, typical, worst case
• difference between binary search and binary search tree

geometric representations of BSTs

• 1d range search
• interval stabbing query
• orthogonal line segment intersection
• 2d search: grid, quadtree, 2D tree, BSP tree
  • properties of each. pros/cons of each
• kD trees
  • define
  • how do they work?
  • why should we care?
  • worst case? how to improve?
• orthogonal rectangle intersection

balanced search trees (3.3)

• definition
• in general, difference between standard BST and balanced search tree
• 2-3 trees
  • how are they different from BSTs?
  • invariants
  • worst case height of 2-3 tree? best case? average case?
  • runtimes
• rb trees
  • invariants
  • elementary ops; why are they useful? what do they do?
  • worst case height of LLRB? best case? average case?
  • runtimes
  • define LLRB
• b-trees
  • define
  • why are they useful? how are they useful?
• convert from 2-3 to rb, or rb to 2-3

hash tables (3.4)

• define
  • hashCode()
  • hash() hashing function
  • hash collision
• desired properties for hash function
• separate chaining
• linear probing
• how to resize if full or empty

graphs (chapter 4)

undirected graphs (4.1)

• define
  • graphs, vertex, edge
  • path, cycle
  • vertex degree
  • connected, connected component
  • dense, sparse, clique
• fundamental ops of undirected graph
• how to implement higher-level ops from fundamental ops?
• adjacency-matrix vs. adjacency-lists
• DFS vs. BFS
• runtime of BFS
• look at graph-processing challenges

assignments

be able to summarize the key learning points and data structures of each of the assignments

1. P01_Hex
2. P02_DataTypes
3. P03_Sorting
4. P04_Pathfinding
5. P05_KDTrees
6. P06_HollywoodCenter

slides

1. S00_Intro
2. S01_UnionFind
3. S02_AlgorithmAnalysis
4. S03_BagsQueuesStacks
5. S04_ElementarySorts
6. S05_MergeSort
7. S06_Quicksort
8. S07_PriorityQueue
9. S08_SymbolTables
10. S09_BinarySearchTrees
11. S10_BSTGeometry
12. S11_BalancedSearchTrees
13. S12_HashTables
14. S13_UndirectedGraphs