# CSE 373, Winter 2019: Exams

## Final Exam

Final is on Tuesday, March 19 in SMI 120 8:30-10:20am (110 minutes).

Review sessions:

1. Section 10 (March 14)
2. Lecture 25 (March 15)
3. 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.

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

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