- Exam policies
- Closed book, closed notes
- No calculators, cell phones, or other electronic devices allowed.
- You will be provided the same list of summations and identities you had on the midterm.
- 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.
This is roughly: Hashing, Sorting, Graphs, Parallelization,
Concurrency, NP-completeness
- Check the lecture calendar for links to all slides and ink used
in class, as well as readings for each topic.
- Note that the material in this course tends to build on itself,
so it would also be reasonable to expect you to remember the basics
of data structures covered earlier in the quarter or what big-O
etc. means. 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, especially to be able to explain what the worst-/best-case behaviors of the data structures are.
- We will not ask you to find the exact closed-form of a recurrence (e.g. using the tree method), but we may ask you to find the big-O of familiar recurrences (e.g. ones for sequential mergesort or binary search).
- We will not expect you to have memorized the recurrences or running times associated with parallel sorts, but we will expect you to be able to write recurrences for similar scenarios.
- The first page of the exam will be short-answer questions focused on the first-half of the course.
Topics (not necessarily an exhaustive list):
- Topics from the first half (see the miterm list)
- Hashtables:
- Basics of good Hash function design
- Different versions of collision resolution:
- Separate Chaining
- Open Addressing: Linear probing
- Open Addressing: Quadratic probing 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
- Know how to carry out the sort
- Lower Bound for Comparison-based Sorting
- Won't be asked to give full proof
- Know the statement of the result, and its consequences (e.g., as on Exercise 10)
- But we may ask you to determine whether a statement is implied by the bound from class
- 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?
- Topological Sort
- Dijkstra's Algorithm for Finding Shortest Paths
- 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?
Stuff that you will NOT be 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.
- 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 the
course of the proof.
- The exercises are a decent indication of the types of
questions that could be asked
Previous Exams
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.
Previous CSE 332 Exams
Exams written by Robbie Weber:
Exams written by Ruth Anderson:
Exams written by other instructors: