CSCI 362: Exam 2

Thursday, April 2, 2020
8:00AM until 12:00PM

Rules / Setup
-------------

- 2 hour time limit

- Single Attempt

- CANNOT page through questions

- CLOSED NOTE / CLOSED BOOK / CLOSED INTERNET

- Topic-Based pages
  - e.g. Stacks and Queue questions will all be on one page

- Some questions will be answered through OneNote Classroom
  - All should have received an email 03/26 before 8:30AM
  - Link will be in exam. Can use web browser version
    - Become familiar drawing trees on your computer
    - Alternatively, take/upload a picture during the exam

Material
--------

Stacks and Queues
 - Operations
 - Definition of Adapter
 - Implementation
   - Vector and List
   - one-line calls to underlying container

Linked Lists
 - Implementation of various operations
 - Complexity of various operations
 - Iterator
   - begin() and end()
   - separate class, not just a pointer!
   - implementation
   - how do we dereference, increment, decrement

C++
 - For each of the following, know which header to include
 - Using std::queue and std::stack
 - Using std::list
 - Using std::set
   - insert / erase / find
   - implementation
   - complexity of operations
 - Using std::map
   - insertion (via pair)
   - operator[] vs at()
   - erase (key) or erase (iterator)
 - Iterators vs. Pointers
 - -> vs . (pointer vs reference member access)

Labs
 - Josephus
   - What is the problem
   - Tracing through an example
   - Complexity
 - Sieve
   - Problem Description
   - Tracing through an example
   - Complexity

Binary Trees
 - Definition
 - Node Representation
   - left, right, parent
 - Operations
   - find
   - insert
   - erase
 - Iterator
   - begin() and end()
   - separate class, not just a pointer!
   - implementation
   - how do we dereference
   - increment/decrement
     - in-order successor / predecessor
 - Level-Order traversal

Balanced Binary Trees
 - AVL Tree
   - Balancing Definition
     - height()
     - isBalanced()
   - Invariants (what must always be true)
   - Insertion strategy / rules
   - Rebalancing
     - Four cases: LL, LR, RL, RR
     - leftRotate()
     - rightRotate()
   - Trace through an example
 - 2-3-4 Tree
   - Balancing Definition
   - Invariants (what must always be true)
   - Components: 2Node, 3Node, and 4Node
   - Insertion strategy / rules
     - Splitting a 4Node
   - Trace through an example
 - Red-Black Tree
   - Balancing Definition
   - Invariants (what must always be true)
   - Color of a Node
   - Rebalancing
     - Color Flips
   - Trace through an example