Final Exam
Final is on Tuesday, December 11 in Kane 220 2:30-4:20pm (110 minutes).
The exam is closed book, closed notes.
You may not use a calculator or any other electronic device.
In the exam, you will be provided this reference sheet, which contains some helpful identities and theorems.
Review sessions:
- Section 10 (December 6)
- Lecture 29 (December 7)
- TA-lead extra review session (December 9, 2-5pm in Smith Hall 120)
Final practice exam:
- Final practice exam:
Unsolved | Solved
- Use this exam as a practice for the exam and question formats than as a study material. Refer section 09 and other section material for problem for study material.
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
- The array vs tree representation of heaps
- Binary heaps and d-heaps (e.g. 4-heaps)
- Memory and Locality
- Memory architecture
- Spatial and temporal locality
- Sorting
- Sorting algorithm properties (stable, in-place)
- Quadratic sorts: insertion sort, selection sort
- Faster sorts: merge sort, quick sort
- 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 (e.g., directed, undirected, weighted, unweighted, walks, paths, cycles, self-loops, parallel edges, trees, DAGs)
- Graph representations (Adjacency list, Adjacency matrix, and their pros and cons)
- Graph traversals (BFS and DFS)
- Single-source shortest-path algorithms: Dijkstra's algorithm
- Topological sorts
- MST algorithms: Prim and Kruskal
- Disjoint sets
- Framing/modeling problems with graphs
- 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.n
- Pre-midterm topics
- See the full list of topics located below
The following topics will NOT be covered in the final:
- B-Trees
- Java generics and Java interfaces.
- Java syntax.
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 as "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.
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
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
- 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 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
- Strengths and weakness of the above
- 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
- Design Decision
- Given a scenario, determine whether one data structure would be a better fit then another (and explain why).
- Given a task and a set of possible implementations, argue for a particular implementation as most suitable for the task. What assumptions are you making? What are the pros and cons of different implementations of the same ADT?
- Heap
- Structure and ordering properties
- Insertion, findMin, and removeMin
- The runtimes for all of the above
The following topics will NOT be covered in the midterm:
- Java generics and Java interfaces.
- JUnit.
- Java syntax.
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 class discussion board
or someone on the course staff.
Here are some practice problems from CSE 332. Most of the material should overlap
with our course.