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:B-trees, Hashing, Sorting, Graphs, Parallelization,
Concurrency, NP-completeness
- 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 big-O
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 run-times
- Know how to carry out the sort
- Given a scenario, choose the most appropriate sorting algorithm.
- 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
- 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 high-level 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 pseudo-code to use Java threads & locks
Day 2
- B-Trees :
- Be able to insert and delete (key,value) pairs into a B-tree
- 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
- 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
- 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
- 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
- P, NP, NP-complete, NP-hard
- 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? We didn't get to this in time to test you, but we'll discuss it in lecture
- The list of NP-complete 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 Fork-Join 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 B-Tree 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!