Final Info

Overview and Process

The test will be IN PERSON

• Time/Date: 8am-9:40am May 6th
  • The test will be set for 1 hour, 40 minutes
  • If you have USC approved accommodations, you must upload your accomodation information HERE 7 days before the exam, otherwise you will not be able to use your accommodations.
• Location: You must go the room below that matches the first letter of your LAST NAME.
  • THH 301: A-K
  • THH 202: L-S

  • THH 208: T-Z

  • If you have OSAS accommodations you should schedule your exam at the OSAS offices on the same day during OSAS hours
• The test will be taken on paper. Be prepared a pencil/pen.
• The exam is Closed book, Closed notes, Closed Internet (search/reference). You may use your mind, and blank scratch paper but nothing else. No referencing your labs, homeworks, etc.

Topics and Style

The exam is a mix of short answer, multiple choice, analysis, tracing, and coding. For coding, we will visually grade your code and be fairly lenient with small syntax errors (e.g. a missing semicolon).

Topics and Style

The final is cumulative over the topics listed below:

Unit 4 - ADTS

• List, Set, Map, Priority Queue, Queue, Stack
• ADT Identification: When to use each given a problem description

Unit 5 - STL

• Iterators and their use
• std::map usage and runtime of its operations
• std::set usage and runtime of its operations

Unit 11 - Recursive Graph & Tree Traversals Algorithms

• Graph Traversals

Unit 12 - Binary Search Trees & AVL Trees

• Binary Search Trees
• Balanced Binary Search Trees / AVL Trees

Unit 13 - Splay Trees

• Splay Trees: Understand the insertion, find, and remove operatoins and the splay process of a node to the top.

Unit 15 - Hash Tables Intro

• Be able to apply the algorithms for open- and closed-addressing insertion, removal, and find, as well as resizing/rehashing the table.
• Be prepared to code aspects of these operations.

Unit 16 - Counting

• All relevant counting rules and approaches taught in lecture and on HW

Unit 17 - Recursion: Combinations & Backtracking

• Recursion
• Combinations & Backtracking

Unit 18a,b - 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 20 - Bloom Filters & Skip Lists

• Bloom filter pros and cons
• Bloom filter operations (insert and find)
  • Don’t need to MEMORIZE false probability results, but should understand the derivation and be able to achieve similar (simpler) derivations related to probability.
• Skip lists

Unit 21 - 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 22 - 23- and 234-Trees

• structure
• insertion and find algorithms

Unit 23 - Amortized Analysis and Log Structured Merge Trees

• Approaches to performing amortized analysis
• Understand find and insert for log-structured merge trees

Practice Materials

• See relevant practice materials from MT1, MT2, MT3