CSE 332 Summer 2018 Final Exam: Thursday August 16, Friday August 17, 2018
In class
The final will be in two parts. The first in the usual time/location for section. The second in the usual time/location for lecture
A blank copy of this quarter's final: Day 1 and Day 2
Sample solutions: Day 1 and Day 2
 Exam policies
 Closed book, closed notes
 No calculators, cell phones, or other electronic devices allowed.
 Writing after time has been called will result in a loss of points on your exam.
 You will be provided with the same formula sheet you had on the midterm.
 We will treat taking the final as two separate exams. For example, on Friday you will not be able to change anything you wrote on Thursday.
 The final will focus on all material studied since the midterm.
This is roughly:Btrees, Hashing, Sorting, Graphs, Parallelization,
Concurrency, NPcompleteness
 Check the lecture calendar for links to all slides used
in class.
 Note that the material in this course tends to build on itself,
so we will expect you to still remember data structures covered earlier in the quarter or what bigO
etc. means (on both days of the exam). I will not ask you to actually *do* an AVL insertion, but we will expect
you to still have a reasonable idea of how the data structures work..
 The following list of topics is not necessarily exhaustive, but is intended to give you a feel for what we're likely to ask about. We have divided the list into what topics we intend to focus on each day.
 Topics which are significantly different from past exams have been bolded below.
Topics (not necessarily an exhaustive list):
Day 1
 Sorting
 Sorts:
 Simple Sorts: Insertion Sort, Selection Sort
 Heap Sort
 Merge Sort
 Quick Sort
 Bucket Sort & Radix Sort
 Know runtimes
 Know how to carry out the sort
 Given a scenario, choose the most appropriate sorting algorithm.
 Lower Bound for Comparisonbased Sorting
 Won't be asked to give full proof
 But may be asked to use similar techniques
 Be familiar with the ideas
 Understand the implications of this result for building any data structures we've discussed this quarter, even those on the day 2 list. (see Exercise 7).
 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 and Pack
 Given a problem, give highlevel descriptions of maps, reduces, prefixes, and packs to solve the problem
 Analysis of Parallel Algorithms
 Parallel Sorting
 Amdahl's Law
 Concurrency
 Race Conditions
 Given code, find a bad interleaving, or decide that none exists
 We will not ask you to differentiate between bad interleavings and data races
 Synchronizing your code
 Locks, Reentrant locks
 Issues of lock scheme granularity: coarse vs fine
 Issues of critical section size
 Deadlock
 We will not test your understanding of Java's synchronized statement
 Be able to write pseudocode to use Java threads & locks
Day 2
 BTrees :
 Be able to insert and delete (key,value) pairs into a Btree
 Given a page size, and sizes of keys, values, and pointers find the values of M and L (or vice versa)
 Know the meanings of temporal and spatial locality, and be able to evaluate whether given code exhibits either.
 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
 Runtimes for the different versions (though you do NOT need to memorize the equations for expected # of probes for a given load factor)
 Deletion
 How to resize a hash table when it gets too full
 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.
 Given a word problem be able to represent the problem as a graph and choose an algorithm to solve the problem (like exercise 12B)
 Graph Traversals
 BreadthFirst
 DepthFirst
 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
 P, NP, NPcomplete, NPhard
 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
NPcomplete? We didn't get to this in time to test you, but we'll discuss it in lecture
 The list of NPcomplete problems discussed differs by quarter. We don't expect you to know about Hamiltonian Cycles, or Long cycles.
Any P vs. NP question will either be about a problem we've discussed, or that is closely related to ones we've discussed.
 The definition of P given in previous quarters was more informal than ours (often omitting the decision problem requirement). so solutions may not match our definitions. If you're in doubt, please ask!
Stuff that you will NOT be tested on:
 Eclipse
 Generics
 Java syntax
Misc.:
 Note that you WILL likely be required to write Java code (in
particular ForkJoin or Java thread code), but we will not be
sticklers for Java syntax. We will care about edge cases and other details of a
correct algorithm, but not things like missing semicolons
 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.
Previous Exams
We provide some exams from previous quarters of 332 to help with
your studying. Be aware that the topics covered vary from what
will be covered on our exam  in particular previous finals do not include BTree questions
(you should look at old midterms for examples of those problems, because they are fair game this quarter),
and previous exams will test Java particulars of concurrent code (like the synchronized keyword)
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
Good luck with your exam studying!