COS 265 Exam Study Guide

Oral: 2026 Oct 21 (start), Final: 2026 Dec 15 8:00–10:00

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

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.

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.

Important

Your final course grade is the weighted average of category scores as long as you earn at least a C- in all grade categories (except extra credit). Please see the Syllabus for more details.

Material Topics and Content

The following provides 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.

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

Note

You are not allowed to use written/printed notes, book, or any other electronic resources during either of the exams.

Critical Thinking Skills

Note

Oral exam covers CT00.

book website

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

Note

Oral exam covers chapters 1 and 2.

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 quote by Eric s. Raymond: "Smart data structures and dumb code works a lot better than the other way around."

Note

Oral exam covers everything except tree traversal.

union-find

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?

algorithm analysis

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

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

Note

Oral exam covers stack, queue, and priority queue. We did not talk about randomized queue or set/bag, but you should still be aware of these.

sorting and shuffling

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

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