Final Info

Overview and Process

• Time/Date: Sat, Dec 14 at 11 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)

  • TBA
• There will be a one page attendance sheet with 1-2 written questions.
• The rest will be on Gradescope
• 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

Unit 24 - Log Structured Merge Trees

Practice Materials

Sample Finals

• There is a practice final available on Gradescope:
  • CSCI 104L Spring 2024 PRACTICE FINAL
• Sample Final (Spring 2014) (no solutions)

• Sample Final (Spring 2014 and others) (no solutions)

• Final Practice (Summer 2020)

• Final Practice Solutions (Summer 2020)

• Final Practice (Summer 2021)
• Final Practice Solutions (Summer 2021)