# CSE 373, Summer 2019: Exams

## 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.

• 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.

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.

• 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 topics

You are responsible for understanding the following topics:

• 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
• 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.

• write on the back sides of pages
• write in the margins or corners

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.