Exams- CSE 332

Exam 1 Logistics

Friday July 25th, 09:40-10:40 AM

Location: DEM 102 (Map)

Makeup Exam

If you are sick the day of the exam do not come to the exam. Send Yafqa an email so we know why you're not there, and we will schedule makeup exams as needed. Similarly in the event of some other emergency (e.g., a car accident on your way to campus), send Yafqa an email and we'll schedule a makeup.

Exam policies

Closed book, closed notes.
No calculators, cell phones, or other electronic devices allowed.
You will be provided a reference sheet; it will look something like this reference sheet (though we might change the formatting or add some things; we won't remove anything from here though).
All material from the course from lecture 1 up to and including hash-tables is fair game; sorting will NOT be on the exam. Check the lecture calendar for links to all slides and ink used in class.

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
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
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 resizing operation)

Stuff that you will NOT be tested on:

IntelliJ
Generics
Java syntax

Misc.:

Note that you may be required to write pseudocode, but it will be evaluated as an algorithm, not as valid Java (or whatever) code
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.
The homeworks and section problems thus far 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. 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.