Final Info
Overview and Process
- Time/Date: Wednesday, May 7th, 8 AM Pacific
- The test will be set for 110 minutes. The room is scheduled for 2 hours, so please be a few minutes early.
- If you have USC approved accommodations, please coordinate with Tallulah Winston-Schrader (winstons@usc.edu) and we will make preparations for your approved time. All OSAS exams will be taken at the OSAS center, please make your arrangements as soon as possible.
-
Location: (leave a blank seat between you and your neighbor, if possible)
-
Last name A - D => SLH 102
-
Last name E - Li => HAR 101
-
Last name Lo - W => SLH 200
-
Last name X - Z => ZHS 252
-
- The exam will be on paper similar to the midterm exams.
- The exam is Closed book, Closed notes, Closed Internet (search/reference/ChatGPT).
- You are allowed 1 8.5x11 handwritten (front and back) cheatsheet. No typed cheat sheets. No single-sided, taped pages to form a double-sided sheet. You will be asked to turn your cheatsheet in when you are done with the exam (so if you want it for posterity, make a copy beforehand).
Topics and Style
The final is cumulative, so questions related to any unit we have covered may appear on the exam. However, the exam will focus on the topics we have covered since the 2nd midterm:
Unit 17 - Counting
- All relevant counting rules and approaches taught in lecture and on HW
Unit 18 - Probability
- All relevant probability rules and approaches taught in lecture and on HW
- Basic probability calculation
- Conditional probability and its definition
- Law of total probability
- Definition of (mutual and pairwise) independence
- Bernoulli trials and binomial distribution
- Bayes Theorem
- Random Variables and Expected Value
- Linearity of Expectation
- Geometric Distribution
Unit 19 - Number Theory
- Definitions of modular congruence
- Performing modular arithmetic
- Modular exponentiation techniques
- Euclid’s algorithm for finding
gcd - Finding multiplicative inverses for modulo-n systems
Unit 20 - Hash Tables, Functions, and Bloom Filters
- One-way / cryptographic hash functions
- Bloom filter pros and cons
- Bloom filter operations (insert and find)
Unit 21- Skip Lists
Unit 22 - Prefix Trees and Compressed Prefix Trees
- Construction and insertion
- Finding elements
- Ways of structure nodes (arrays vs. linked lists for sparse implementations)
- Compressed prefix trees
Unit 23 - Amortized Analysis
- Approaches to performing amortized analysis