CSCI 362: Exam 1 Review

Introduction
- Data Structures and Algorithms
- Complexity
  - Time vs. Space
  - Best, Average, Worst
- C++ Overview
  - Container classes
  - Algorithms
  - Notion of Iterator, Range
  - Classes
    - Constructor
    - Destructor
    - Member initializer list
    - const member functions
  - Differences to Java

Algorithms
- Complexity for all algorithms we covered
- Range notation [lower, upper)
- Sorting
  - Bubble vs. Selection vs. Insertion
- Searching
  - Linear vs. Binary vs. Interpolation
  - Can we always use each?
  - interpolation formula / equation
- Complexity
  - Big-O
  - Growth Function f(N) < c*g(N)
  - Constant vs. Linear vs. Quadratic

C++ Templates
- Syntax for "templatizing" a function
- C++ Standard Library
  - Container: vector
  - Algorithm: fill, copy

Pointers and Dynamic Memory
- reference vs. pointer
- type aliases
- operator* and operator& (conversion between ref and ptr)
- member access (. vs ->)
- nullptr
- new and delete vs. new[] and delete[]
- reading types
- special functions
  - rule of 3
  - destructor
  - copy-assign
  - copy-constructor
- this pointer

Vector / List
- common operations
- implementation of:
  - insert
  - erase
  - constructor(s)
  - destructor
- iterator design/implementation
- resizing
- When to use EACH

Iterators
- concept of
- Bidirectional vs. Random Access