CSCI 362: Test 1 Review

  • Introduction
    • Data Structures
    • Algorithms
    • Complexity
      • Time vs. Space
      • Best, Avg, Worst
    • C++ Overview
      • Container Classes
      • Algorithms
      • Concept of an Iterator
      • C++ Classes
        • Constructor, Destructor, Member Initialization List
        • const vs non-const member functions
        • Separation of interface (header file .h/.hpp) from implementation (source file .cpp)
    • Differences between C++ and Java
    • API documentation
      • What's always included, optional?
  • Algorithms
    • In general, know the complexities for all listed algorithms and how they work
      • You may be asked to implement or fix an incorrect implementation
    • range notation
      • inclusive begin, exclusive end
      • splitting / joining two ranges
    • Sorting
      • bubble (and optimized bubble)
      • selection
      • insertion
      • when to use each?
    • Searching
      • linear_search (std::find)
      • binary_search
        • can we always use binary search?
      • interpolation search
        • when does it work? When does it not work (well)?
        • interpolation formula/equation
        • "distance" measurement
  • Algorithm complexity
    • Big-O notation
    • Growth function
      • showing f(N) = O(N^2) and others (see lecture 2)
    • Constant time algorithms
    • Linear time algorithms
    • Quadratic time algorithms
  • C++ Templates
    • how to "templatize" a function
    • C++ Standard Library Containers
      • Sequence
        • array, vector, list
        • std::array vs C/C++ arrays vs std::vector
      • Associative
        • set, map (high-level overview)
      • Adapters
        • stack
        • queue, priority_queue (high-level overview)
  • Pointers and Dynamic Memory
    • reference vs. pointer
    • type aliases
    • operator* and operator& (conversion between references and pointers)
    • member access (. vs ->)
    • pointers and nullptr
    • reading types (right-to-left)
    • new / delete
    • new[] / delete[]
    • special functions
      • when are constructors/destructors called
      • copy assignment
      • copy constructor
      • rule of 3 (or 5)
    • std::exchange
    • this pointer
    • allocation of 2D matrix
  • Implementations of std::vector and std::list
    • insert, erase, constructor, destructor
    • iterator interfaces for each
      • list iterator vs vector iterator
      • Bidirectional vs RandomAccess
    • begin() and end()
    • std::list::splice
    • std::vector
      • changing capacity -- what needs to happen
    • std::list
      • Node class
      • Iterator class
      • circular, doubly-linked
  • Stack
    • how to implement a stack with:
      • std::vector, std::list
      • one-line calls for each
    • algorithmic complexities for each operation
    • client code for palindrome checking or integer-to-hex
In [ ]: