Midterm Exam

Date: Friday, April 26, 2024

Time: 12:30-1:20 pm

Location: CSE2 G20

Midterm exam policies

1. Closed book, closed notes.

2. No calculators, cell phones, or other electronic devices allowed.

3. Writing after time has been called will result in a loss of points on your exam.

4. You will be provided a math reference sheet during the exam.

All material from the course from lecture 1 up to and including B-trees is fair game.

Hashing and sorting will NOT be on the midterm. Check the lecture calendar for links to all slides and ink used in class, as well as readings for each topic.

Topics Include at least: (NOT NECESSARILY AN EXHAUSTIVE LIST)

• Stacks and Queues - array and linked list implementations. Runtimes.
• Big Oh (and Omega & Theta):
  • Know the definition
  • Be able to evaluate whether f(x) is O(g(x)), Big Omega, Big Theta
  • Be able to find constants c & n0 to demonstrate Big Oh, Big Omega, Big Theta
  • Examining code to determine its Big O running time.
  • Best case, worst case, average case
  • Space complexity
  • Space/Time tradeoffs
• Recurrence Relations:
  • Know closed form for common recurrence relations
  • Given a recurrence relation, solve to closed form
• Binary Heaps:
  • Structure & ordering properties
  • Related: Perfect and Complete Trees.
  • Insertion, findMin, deleteMin, increaseKey, decreaseKey, remove, buildHeap
  • Run-times for all the above; including intuition for expected O(1) for insert & O(n) for buildHeap
  • Array representation
  • D-heaps - how different/related to Binary Heaps
• Tries:
  • Find, insert & delete operations as described in P1
• Dictionary ADT: insert, find, delete
• Binary Search Trees:
  • Binary property, BST ordering property
  • Inorder, Preorder, Postorder traversals
  • Find, insert & delete
  • Run-times for all the above
• AVL Trees:
  • BST with stored height & balance property
  • Height bound resulting from balance property (you do not need to memorize the proof, but being familiar with how you construct the worst case AVL tree may be helpful)
  • Insertions; different rotation cases, no delete
  • Run-time for find & insert
• B-Trees:
  • Motivation for the B-Tree; how it can minimize disk accesses
  • Structure, ordering; use of M, L; principles behind the selection of M & L
  • Insertion, find, deletion; the rules followed for insertion and deletion will be those shown in lecture
  • Run-times of the above

Topics you will NOT be tested on:

• IntelliJ
• Generics
• Java syntax

Misc

1. Note that you may be required to write pseudocode, but it will be evaluated as an algorithm, not as valid Java (or whatever) code.

2. Writing a simple proof of some sort is a possibility. Any such proof will be intended to show that you know how to prove things. You will not be expected to have a "magic insight" in order to complete the proof.

3. The homeworks and section problems thus far are a decent indication of the types of questions that could be asked.

Previous midterms

We provide some exams from previous quarters of 332 to help with your studying. Be aware that the topics covered may vary from what will be covered on our exam - refer to the list above if you are wondering about a particular topic. Our hope is that these exams will be useful in your studying, but you should *NOT* take them as a guarantee of exactly what your exam will be like this quarter. They are provided only to help you in your studying. We recommend *taking* these exams on your own in a timed environment to get practice both with the material and with managing your time. Most students find this approach better preparation than just looking at the solutions.

• CSE 332 23au Midterm, Solution
• CSE 332 23sp Midterm, Solution
• CSE 332 23wi Midterm, Solution
• CSE 332 22su Midterm, Solution
• CSE 332 19au Midterm, Solution
• CSE 332 19wi Midterm, Solution
• CSE 332 18au Midterm, Solution
• CSE 332 18wi Midterm, Solution
• CSE 332 17au Midterm, Solution
• CSE 332 16au Midterm, Solution
• CSE 332 15wi Midterm, Solution
• CSE 332 14 sp Midterm, Solution
• CSE 332 13au Midterm, Solution
• CSE 332 13sp Midterm, Solution
• CSE 332 13wi Midterm, Solution
• CSE 332 12sp Midterm, Solution
• CSE 332 12wi Midterm, Solution
• CSE 332 11wi Midterm, Solution
• CSE 332 10su midterm Solution
• CSE 332 10sp midterm Solution

Final Exam

Date: Thursday June 6, 2024

Time: 8:30-10:20 am

Location: CSE2 G20

Final exam policies

1. Closed book, closed notes.

2. No calculators, cell phones, or other electronic devices allowed.

3. Writing after time has been called will result in a loss of points on your exam.

4. You will be provided a math reference sheet during the exam.

The final is cumulative, which means we can ask you about any topic from the whole class. That said, we will put significantly more focus on the second-half of the course. I will not ask you to actually *do* an AVL insertion or a B-tree insertion/deletion, but having a reasonable idea of how these work would be a good idea. This is roughly: Hashing, Sorting, Graphs, Parallelism, Concurrency, NP-completeness.

Topics Include at least: (NOT NECESSARILY AN EXHAUSTIVE LIST)

• Topics from the first half (see the midterm list)
• Hashtables:
  • Basics of good Hash function design
  • Different versions of collision resolution:
    • Separate Chaining
    • Open Addressing: Linear probing
    • Open Addressing: Quadratic probing
    • Open Addressing: Double hashing
  • Strengths/weaknesses of the above versions
  • Load factor
  • Run-times for the different versions (though you do NOT need to memorize the equations for expected # of probes for a given load factor)
  • Deletion
  • Rehashing (that is, the process of resizing a hash table)
• Sorting
• Sorts:
  • Simple Sorts: Insertion Sort, Selection Sort
  • Heap Sort
  • Merge Sort
  • Quick Sort
  • Bucket Sort & Radix Sort
• Know run-times and properties (stable, in-place, etc.)
• Know how to carry out the sort
• Lower Bound for Comparison-based Sorting
• Won't be asked to give full proof
• But may be asked to use similar techniques
• Be familiar with the ideas
• Graphs - In general, know how to carry out the operation/algorithm & running time.
• Graph Basics
  • Definition; weights; directedness; degree
  • Paths; cycles
  • Connectedness
  • DAGs
• Graph Representations
  • Adjacency List
  • Adjacency Matrix
  • What each is; how to use it; pros and cons of each.
• Graph Traversals
  • Breadth-First
  • Depth-First
  • What data structures are associated with each?
• Dijkstra's Algorithm for Finding Shortest Paths
• Topological Sort
• Prim's Algorithm for Finding Minimum Spanning Trees
• Kruskal's Algorithm for Finding Minimum Spanning Trees
• Use of Disjoint Sets in Kruskal's Algorithm
• Parallelism
• ForkJoin Parallelism, and Associated Terms (Work, Span, etc.)
• ForkJoin Applications, ex: Parallel Summing of an Array
• Reduce: parallel sum, multiply, min, find, etc.
• Map: bit vector, string length, etc.
• Be able to write Java fork join code for simple maps & reductions
• Parallel Prefix Sum Algorithm, Filters, etc.
• Analysis of Parallel Algorithms
• Parallel Sorting
• Amdahl's Law
• Concurrency
• Race Conditions
• Data Races
• Bad Interleavings
• Synchronizing your code
  • Locks, Reentrant locks
  • Java's synchronized statement
  • Issues of lock scheme granularity: coarse vs fine
  • Issues of critical section size
  • Deadlock
• Be able to write pseudo-code for Java threads & locks
• P, NP, NP-completeness
• What does each of these classes mean
• Examples of problems in each class
• What to do if you think the problem you are trying to solve is NP-complete?

Topics not tested on

• IntelliJ
• Generics
• Java syntax

Misc

• Note that you WILL likely be required to write Java code (in particular Fork-Join or Java thread code), but we will not be sticklers for Java syntax. Edge cases and other details of a correct algorithm - yes, semicolons - no.

Good luck with your exam studying!