Final Exam
Final is on Tuesday, March 19 in SMI 120 8:30-10:20am (110 minutes).
Review sessions:
- Section 10 (March 14)
- Lecture 25 (March 15)
- 3:30pm review session, ECE 125 (March 15) - see piazza pinned post
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:
- Sorting
- Sorting algorithm properties (stable, in-place)
- Quadratic sorts: insertion sort, selection sort
- Faster sorts: heap sort, merge sort, quick sort
- Runtimes of all of the above (in the best and worst case)
- Memory and Locality
- Basics of memory architecture
- Spatial and temporal locality
- Graphs
- Graph definitions (e.g., directed, undirected, weighted, unweighted, walks, paths, cycles, self-loops, parallel edges, trees, DAGs, strongly connected components)
- 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 including optimizations and implementations
- Framing/modeling problems with graphs
- P vs. NP
- Definitions of P, NP and NP Complete
- Understand what a reduction is
- Design Decisions
- Given a scenario, what ADT, data structure implementation and/or algorithm is best optimized for your goals?
- ----> What is the purpose of the ADTs we’ve learned?
- ----> Given a scenario, determine whether one data structure would be a better fit then another (and explain why)
- ----> What is the optimal implementation of an ADT for a given situation?
- What is the runtime of a data structure’s implementations of each ADT behavior?
- How can you leverage an algorithm to answer a given question?
- Pre-midterm topics
- See the full list of topics located below
The following topics will NOT be covered in the final:
- Finding the closed form big O of recursive code using Tree Method or Unrolling
- 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
Midterm key
Topics covered
You are responsible for understanding the following topics:
- ADTs and Data structures
- Lists, Stacks, Queues, Maps
- Array vs Node implementations of each
- Asymptotic analysis
- Proving big \(\mathcal{O}\) by finding a \(c\) and \(N_0\)
- Modeling code runtime with math functions, including recurrences and summations
- Finding closed form of recurrences using unrolling, tree method and master theorem
- Looking at code models and giving big \(\mathcal{O}\) runtimes
- Definitions of big \(\mathcal{O}\), big \(\Omega\), big \(\Theta\)
- BST and AVL Trees
- Binary search property, balance property
- Insertions, retrievals
- AVL rotations
- Hashing
- Understanding hash functions
- Insertions and retrievals from a table
- Collision resolution strategies: chaining, linear probing, quadratic probing, double hashing
- Heaps
- Heap properties
- Insertions, retrievals while maintaining structure with bubbling up
- Homework
For each of the following, know a high level description and runtime of each method in the class
- ArrayDictionary
- DoubleLinkedList
- ChainedHashDictionary
- ChainedHashSet
The following topics will NOT be covered in the midterm:
- Memory and Locality
- B-Trees
- JUnit specifics and JUnit syntax
In the exam, you will be provided this reference sheet, which contains some helpful identities.
You are allowed to bring a notesheet and it may be handwritten or typed. The notesheet must be 8.5 x 11 inches, and you may have content on both the front and back.
We will be scanning your exams to grade. So do not:
- write on the back sides of pages
- write in the margins or corners
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.