Final Exam
The final will take place on Tuesday, June 5th. It will take place
in Kane 110 from 8:30am to 10:20am (110 min)..
You are allowed to bring one 8x11 inches piece of paper for notes. You may use both front and back sides and it may be handwritten or typed.
We will have a TA-led review session on Friday, June 1 5pm in EEB 125.
Topics covered
- B-Twees:
- Motivation behind B-Trees and how they can minimize disk access
- What "M" and "L" are; principles behind the selection of M and L
- The B-Tree invariants
- How to insert and find (but not delete)
- Runtimes of the above
- Heaps:
- Structure and ordering properties.
- Insertion, findMin, removeMin, and buildHeap.
- The runtimes for all of the above
- The array vs tree representation of heaps.
- Binary heaps and d-heaps (e.g. 4-heaps).
- Sorting:
- Quadratic sorts: insertion sort, selection sort.
- Faster sorts: merge sort, quick sort.
- Understand the runtimes of all of the above (in the best and worst case).
- Analysis of recursive code:
- How to find the closed form of a recurrence using the tree method.
- How to find a big-Theta bound of a recurrence using the master method.
- Graphs:
- Graph definitions:
- Directed vs undirected
- Weighted vs unweighted
- Walks vs paths vs cycles
- Self-loops and parallel edges
- Simple vs non-simple graphs (e.g. multigraphs)
- Trees, DAGs
- Graph representations:
- Adjacency list
- Adjacency matrix
- Pros and cons of each
- Graph algorithms:
- Graph traversals: BFS and DFS
- Single-source shortest-path algorithms: Dijkstra's algorithm
- Topological sorts
- MST algorithms: Prim and Kruskal
- Disjoint sets
- P vs NP
- Understand what the complexity classes P, NP, and EXP are
- Understand how to show a decision problem is in P or NP
- Understand what a reduction is
- Understand what NP-COMPLETE and NP-HARD mean
- General skills:
- How to construct different test cases.
- Reading and mentally running code/pseudocode (to help find the runtime, to
help debug, etc...).
- Given a scenario, determine whether one data structure would be a better fit
then another (and explain why).
- How to use data structures and algorithms we've studied to help us
solve novel problems.
- Algorithm Application:
For any of the algorithms, make sure you understand:
- In what situations is this algorithm useful? What kind of data does this algorithm operate on? Is there certain states or types of data that are better suited for this algorithm?
- What are the pros and cons of using this algorithm vs other choices? Consider runtime and memory usage.
The following topics will NOT be covered in the midterm:
- Java generics and Java interfaces.
- Java syntax.
This test is technically not cumulative, though you may need some understanding of the pre-midterm material to fully understand some of these topics.
You may be asked to find the closed form of recurrences using the tree method. If so,
you will be given a cheatsheet on the exam containing any identities you will need.
Practice material
As said in lecture, these exams will not correlate 100% with the focus and concepts that will be tested in this quarter's exam. Review the topics list, use your best judgement, and ask when deciding whether it would helpful or not to study a given problem.
A few additional notes:
- Some exams refer to the "union-find" data structure and "up-trees". The "union-find"
data structure is the same thing as the "disjoint set" data structure we studied in
class. An "up-tree" is the name for each tree contained within the disjoint set.
- You may want to look at some of the practice midterms, especially if you're looking
for more practice on topics like heaps or using the tree method. (This quarter, we
both topics after the midterm; other quarters covered them before the midterm.)
Here are some practice finals from CSE 332. Some, but not all, of the material should
overlap with our course.
In particular, CSE 332 spends some time covering topics like parallelism and concurrency
that we do not. Feel free to ignore any questions that mention "parallelism", "concurrency",
"work and span", and the "ForkJoin" framework.
Midterm
The midterm will take place on Friday, April 27. It will take place in Kane 110 from 8:30am to 9:20am (50 min).
You are allowed to bring one 8x11 INCHES :) piece of paper for notes. You may use both front and back sides and it may be handwritten or typed.
Topics covered
You are responsible for understanding the following topics:
- ADTs and data structures:
- The difference between an ADT and a data structure.
- Stacks, queues, lists, dictionaries: common implementations,
runtimes, and when to use them.
- Iterators: what they are, how to implement basic ones (e.g. for array lists
and linked lists).
- Asymptotic analysis:
- Big-O, Big-Omega, and Big-Theta.
- Finding c and n0 to show that one function is in Big-O, big-Omega, or Big-Theta of another.
- Modeling runtime of a piece of code as a function possibly including a summation or a recurrence.
- Understand the difference between best-case, average-case, and worst-case
runtime.
- Trees:
- How to implement and manipulate trees including
binary search trees and AVL trees.
- Runtimes for tree operations.
- Performing AVL rotations when inserting values.
- Hash tables:
- Closed vs open addressing.
- Collision resolution: separate chaining, linear probing, quadratic probing,
double hashing.
- Basics of good hash function design.
- Load factor.
- Runtimes (best, average, and worst-case).
- Testing
- How to construct different test cases.
- Reading and evaluating code to debug
The following topics will NOT be covered in the midterm:
- Java generics and Java interfaces.
- JUnit.
- Java syntax.
- Finding the closed form of summations and recurrences
Practice material
Here are some exams and past material from past quarters from CSE 373. Keep in
mind that some of these midterms may ask questions that we do not plan on asking in
our midterm. If a problem does not obviously map to any topic listed under
"Topics Covered" above, then you can ignore it. If you are unsure, just ask on Piazza
or someone on the course staff.
Here are some practice problems from CSE 332. Most of the material should overlap
with our course.