Exams

Final Exam Policies and Logistics

Cancelled due to UW’s shutdown, but see below.

Extra assignments:

• A mandatory Gradescope assignment covering post-midterm topics. This will be released at 4:30pm on Monday, March 16th and is due at 4:30pm on Thursday, March 19th. The format will be similar to a reading quiz (ie, online only; question formats include multiple-choice, fill-in-the-blank, short-answer, and long-answer), except that you won’t receive immediate feedback about whether your answer is correct/incorrect.
• An optional Gradescope assignment covering the midterm topics. This optional assignment’s logistics (eg, format, timing, policies) are identical to the mandatory assignment except that it will be worth a small amount of post-curve extra-credit.

See this Piazza post for more information.

Final Exam Topics Mandatory Final Assignment

The exam final assignment will cover all topics from section, homeworks, and lecture; any topic covered during the entire quarter is considered “fair game”. ~~However, we will skew the exam towards topics introduced after the midterm: approximately 1/3 of the exam will cover topics from the first half of the course and the remaining 2/3 will cover the latter topics.

In addition to the midterm topics listed below, we may include:

The final assignment (see above announcement) includes the following topics:

• Graphs
  • Representations: Adjacency Lists, Edge Sets, Adjacency Lists; How to Choose a Graph Representation
  • Traversals: BFS, DFS; Applications of BFS and DFS
  • Shortest Path Algorithms: Dijkstra’s, A* Search
  • Minimum Spanning Trees, Prim’s, Kruskal’s; Applications of MSTs
  • Topological Sort (aka Topological Ordering): Applications; When it’s Possible; Finding a Topological Sort
• Disjoint Sets ADT
  • WeightedQuickUnion: representation and characteristics
  • Path compression
  • Applications
• Tries
  • How and When to Use
  • Trie Representations: Simple Trie, Hash-table-based, BST-based, Ternary Search Tree
  • Prefix Searches with Tries
• Reductions
  • Difference from Decomposition
  • High-level Description and Process
• Sorting Algorithms
  • Determining Time and Space Complexity
  • Sorting Concepts: Inversions, Stability
  • SelectionSort: How to Implement; Time/Space Complexity; When to Use
  • HeapSort: How to Implement; Time/Space Complexity; When to Use; In-Place Variant
  • MergeSort: How to Implement; Time/Space Complexity; When to Use
  • InsertionSort: How to Implement; Time/Space Complexity; When to Use; In-Place Variant; Best- vs Worst-Case
  • QuickSort: Partitioning (as a concept); How to Implement; Time/Space Complexity; Best- vs Worst-Case
  • RadixSort

Assignment PDFs

Although the assignments were released via Gradescope, we are also providing PDF versions as study materials for future quarters. Please ask your teaching staff for the answers and/or an answer key.

• Mandatory Final Assignment (post-midterm)
• Optional Final Assignment (pre-midterm)

Midterm Policies and Logistics

Date/Time: Friday, Feb 14th. 3:30-4:20 (our usual lecture time).

Location: KNE 210 and KNE 220. Depending on your student ID, please go to:

• KNE 210: If your student ID is odd (ends with 1, 3, 5, 7, 9).
• KNE 220: If your student ID is even (ends with 0, 2, 4, 6, 8).

Review Session: There will be a TA-led review session Thursday, Feb. 13, 4:30-6:30 PM, in ARC 147. Bring your questions, and best of luck studying!

For the exam, you should bring:

• An erasable pencil or pen
• Eraser
• Notes sheet: you may bring up to one 8.5 x 11 inch sheet of paper, single-sided, with handwritten (not printed) notes

During the exam, we will provide:

• Exam and scratch paper
• Timekeeping (we will project a large clock at the front of the room)

To minimize disruption to other students, you may not leave your seat in the first 10 minutes or last 5 minutes of the exam. If you need to use the restroom, please bring your phone and exam to a staff member.

Midterm Topics

The exam will cover all topics from section, homeworks, and lecture up to and including Friday, Feb 7th. In other words, it may consist of the following topics:

• ADTs
  • List
  • Stack and Queue
  • Map and Set
  • Deque
  • Priority Queue
  • Difference between ADTs and Data Structures
• Testing/Debugging Concepts
  • Terminology (eg, test case, debugger)
  • Debugging concepts: minimal working example, reproducing bugs, experimentation, and assumptions
  • Design of testable code
• Algorithm Analysis
  • Asymptotic analysis: why/how we do it
  • Case vs asymptotic analysis (see also TA-made study guide)
  • Common summations used in asymptotic analysis
  • Big-O, Big-Theta, and Big-Omega
• Binary Search
• Trees
  • Binary Search Trees
  • B-Trees
  • Left-leaning Red-Black Trees
  • Tree traversals: pre-, in-, post-order
• Hashing
  • Hash functions
  • Hash tables: separate chaining and open addressing
• Binary heaps
  • Percolating up and down
  • buildHeap
• Multi-dimensional Data
  • Spatial partitioning: uniform, quadtrees, k-d trees

Midterm Practice

• 20wi:
  • Practice Midterm [Solutions] (Written this quarter to reflect the style and approximate difficulty you can expect on the actual midterm)
  • TA-Compiled Problems from Past Midterms [Solutions] (Compiled from past quarters; less specific to 20wi, but still useful practice)
• 19au:
  • Midterm Exam (Solutions) (Skip question 5)

If you need additional practice, last quarter’s Midterm Recommended Problems are a good supplement.

The current CSE 373 was redesigned in 19au. While individual exam/review questions from previous quarters can also be useful, we do not recommend doing old practice exams in full, since the scoping is likely different.

Midterm Results

The actual midterm is here (solutions are here). The median was 89 points (equal to 84.7%) and the standard deviation was 9.4 points (equal to 8.9%).