Final
Final is on Tuesday, June 11 in CSE G20 8:30-10:20am (110 minutes).
In the exam, you will be provided this reference sheet, which contains some helpful identities and theorems.
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
Review sessions:
- Section 10 (June 6)
- 4pm review session, PAA 102
- Lecture 30 (June 7)
Final topics
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
- Visual tree representation and heap properties
- Array implementation
- 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
- Graphs
- definitions (e.g., directed, undirected, weighted, unweighted, walks, paths, cycles, self-loops, parallel edges, trees, DAGs, etc.)
- implementations (Adjacency list, Adjacency matrix, and their pros and cons)
- traversals (BFS and DFS)
- Single-source shortest-path algorithms: Dijkstra's algorithm
- Topological sort
- MST algorithms: Prim and Kruskal
- Disjoint sets
- Framing/modeling problems with graphs
- P vs. NP
- Definitions of P, NP and NP Complete
- Understand what a reduction is
- Coding Projects
- Implementation of each data structure
- Best / average / worst case runtime for each method of each data structure
- Testing (coming up with test cases (see hw3 problem 8))
- Debugging (locating code with bugs (see hw3 problem 8))
- Design Decisions
- Given a scenario, what ADT, data structure implementation and/or algorithm is best optimized for your goals?
- ----> What is unique or specialized about your chosen tool?
- ----> How do the specialized features of your chosen tool contribute to solving the given problem scenario?
- ----> How expensive is this tool and its features in terms of runtime and memory?
- Given a scenario, what changes might you make to a design to better serve your goals?
- Pre-midterm topics
- all ADTs and data structures
- Asymptotic analysis
- ----> Code Modeling (including recurrences)
- ----> Complexity Classes
- ----> Big O, Omega, Theta
- BSTs, AVL Trees
- Hashing
The following topics will NOT be covered in the final:
- Finding the closed form of recursive code using Tree Method
- Writing Java / JUnit syntax.
- Java code / pseudocode for you to read may show up on the exam, but if you need clarification on syntax you may ask.
Recommended final practice material
Below are some exams and past material from past quarters from CSE 373:
Other useful studying material is listed below and can be found on the website:
Other final practice material
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.
-
Some practice finals are 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
Midterm topics
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 tree method and master theorem
- Looking at code models and giving simplified, tight 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
- Homework
For each of the following, know a high level description and runtime of each method in the class
- ArrayDictionary
- DoubleLinkedList
- Testing and Debugging (added 4/27)
- Reading a given piece of code and understanding potential bugs
- Constructing possible test cases for a given piece of code.
The following topics will NOT be covered in the midterm:
- Unrolling Recurrences
- Writing Java / JUnit syntax.
- Java code / pseudocode for you to read may show up on the exam, but if you need clarification on syntax you may ask.
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
Recommended midterm practice material
Below are some exams and past material from past quarters from CSE 373:
Other useful studying material is listed below and can be found on the website:
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 the class discussion board or ask someone on the course staff.
Other midterm practice material
Here are some more past exams and practice exams that you may also use. But know that these are probably less relevant for the current quarter than the recommended materials mentioned in the previous section.