Review Sessions
Final
The final will be given over two parts.
- Day 1 is held in your registered quiz section (August 22).
- Day 2 is held during the last scheduled lecture (August 23, 1:10pm - 2:10pm).
For Day 1, it is important that you
attend your officially registered quiz section.
The course staff reserves the right to otherwise deduct points.
In the exam, you will be provided this reference
sheet,
which contains some helpful identities.
You are allowed to bring a notesheet
to Day 2 only 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
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.
A list of final topics are given here. In particular, you should
review the different expectations for Day 1 and Day 2.
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
- Determining best and worst case situations for code and data structure implementations and the resulting runtimes
- Finding closed form of recurrences using tree method and master theorem
- Looking at code and 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 invariant, AVL invariant
- Insertions, retrievals
- Basics of deletion (but not exact rules)
- AVL rotations
- Hashing
- Understanding hash functions
- Insertions and retrievals from a table
- Collision resolution strategies: chaining, linear probing, quadratic probing, double hashing
- Programming Projects
For each of the following, know a high level description and runtime of each method in the class
- ArrayDictionary
- DoubleLinkedList
- Testing and Debugging
- 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:
- Heaps
- 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:
- Relevant problems on section handouts
- Exercise
- Slides
- Review sessions
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.