Final
The final will take place on Thursday, March 15. It will take place
in Gowen 301 from 2:30pm to 4:20pm (110 min)..
The exam is closed book, closed notes. You may not use a calculator or any other
electronic device.
We will have two review sessions:
- Monday, Mar 12: 4:30 to 6:30 in EEB 125
- Tuesday, Mar 13: 4:#0 to 6:30 in EEB 105
In addition, we will be holding shortened office hours during finals week:
- Monday, Mar 12: 2:30 to 4:30 in the 4th floor breakout
- Tuesday, Mar 13: 2:30 to 4:30 in CSE 216
- Wednesday, Mar 14: 2:30 to 4:30 in CSE 216
There will be no extra office hours on Thursday or Friday.
Topics covered
This test is cumulative, but skewed towards new material. This means
you are expected to understand everything we studied before the midterm, but the bulk of
the questions will be related to new content.
In particular, you are responsible for also understanding the following topics:
- Heaps:
- Structure and ordering properties.
- Insertion, findMin, removeMin, and buildHeap.
- The runtimes for all of the above, including why insert is
on average O(1) and why buildHeap is
worst-case O(n).
- 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.
- Linear sorts: counting sort.
- Understand the runtimes of all of the above (in the best and worst case).
- Understand on a high level why comparison-based sorts have a lower bound of
\(n\log(n)\) on runtime.
- Understand on a high level why adaptive and hybrid sorts exist.
- Understand the core idea behind divide-and-conquer.
- 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
- Pre-midterm topics
- See the full list of topics located below.
- 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.
The following topics will NOT be covered in the midterm:
- Java generics and Java interfaces.
- JUnit.
- Java syntax.
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
We will be releasing a practice final designed for this quarter a little
later this week. In the meantime, here are some exams and practice material
from past quarters of CSE 373.
A few additional notes:
- One note of warning: some past quarters emphasized sorting and de-emphasized graphs.
In this quarter, we de-emphasize sorting and emphasized graphs.
- 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
About the exam
The midterm is scheduled on Friday, February 2. It will
take place in Gowen 301 from 3:30pm to 4:50pm (80 min).
The exam is closed book, closed notes. You may not use a calculator or any other
electronic device.
We will have two review sessions:
- Monday, Jan 29, 4:30 to 6:30 in Gowen 201
- Tuesday, Jan 30, 4:30 to 6:30 in Gowen 201
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, sets: 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:
- The intuition and formal definitions of Big-O, Big-Omega, and Big-Theta.
- Applying the definitions to show that one function is in Big-O, Big-Omega, or
Big-Theta of another (both informally, and formally by finding c and n0).
- How to model different aspects of a piece of code (e.g. the runtime, the
integer output...) as a summation or a recurrence.
- Examine existing code and informally find its Big-O running time.
- Understand the difference between best-case, average-case, and worst-case
runtime.
- Trees:
- How to implement and manipulate trees (abstract syntax trees,
binary search trees, AVL trees...).
- Binary search trees: how to implement get, put, and remove.
- AVL trees: how to implement get and put (but not remove).
- Runtimes for the above.
- The BST and AVL invariants.
- Performing AVL rotations when inserting values.
- Hash tables:
- Closed vs open addressing.
- Collision resolution: separate chaining, linear probing, quadratic probing,
double hashing.
- Strengths and weaknesses of the above.
- Basics of good hash function design.
- Load factor.
- Runtimes (best, average, and worst-case).
- Rehashing.
- Systems and memory:
- Understand on a basic level how computers manage memory
(accessing disk vs RAM vs the cache, why the cache exists, pages and
cache lines).
- Spatial and temporal locality.
- Understand on a high level how the all of the above can affect
runtime performance.
- B-Trees:
- Motivation behind B-Trees and how they can minimize disk accesses.
- 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.
- 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).
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 (may be on final).
- Heaps (will be on the final).
- Sorting algorithms (will be on the final).
Practice material
Here is a practice exam designed for this quarter. The problems asked
in this practice exam are roughly representative of the kinds of problems
you may be asked in the actual midterm.
Our practice midterm should be roughly about the same difficulty or possibly
slightly harder then the actual midterm.
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. In particular, you should ignore any questions about sorting and heaps.
You can also ignore any question that asks you to find the closed form of
summations or recurrences.
Here are some practice problems from CSE 332. Most of the material should overlap
with our course.