**********************
Midterm 1 Topic Review
**********************

How to use this document
========================
+ Self-test using this document to see what concepts are challenging to you
+ Course notes document is the main resource for tips, pitfalls. High priority
  in midterm preparation.
+ Review all participation activities and challenge activities in zyBook
+ Practice your ability to finish the patterns listed here from scratch without
  the help from any editor/ IDE

Topics
======

Basic Concepts
--------------
+ Algorithms
+ Data structure definition and characteristics
+ Abstract Data Type (ADT) definition and characteristics
+ relationships

Environment
-----------
+ Command-line interface (CLI)

  * add prefix ``./`` to run an executable in the current directory

+ keyboard input
+ screen output

+ Basic Linux bash command: ls, mkdir, cd, rm, mv, vi/vim, ssh
+ Compilation command: ``g++``
+ Building: ``make``
+ ``git``

  * clone
  * add
  * status
  * commit
  * push

Modular Compilation
-------------------
* g++

  - three stages in compilation:

    + preprocessing (handle directives in the cpp files)
    + compilation (cpp file to object file)
    + linking (object files to executable)

  - -c to compile (no linking)
  - -o to specify the output file name

* Header file (hpp file)

  - public declarations
  - include other headers
  - header guard
  - may include implementation as in-line methods of a class

* Implementation file (cpp file)

  - function implementations
  - include its own header if exist, and other headers to be used in the
    implementations

* Preproccessor derivatives

  - #include "filename.hpp"
  - #include <sys library>
  - header guard

* Multi-file compilation

  - Module

    + hpp/cpp file pair per class (group of classes)
    + hpp/cpp file pair per group of functions

  - Driver/Runner

    * main.cpp, test.cpp, driver.cpp or other names
    * main function

* Make

  - automate the building process
  - syntax in makefile

    .. code-block::

      <target> : <dependencies/prerequisites>
              <recipe/commands>

  - example

    .. code-block::

      main : main.o lib1.o
              g++ -o main main.o lib1.o

  - command-line invoke

    + ``make`` to build the first target
    + ``make <target name>`` to build a specific target
    + multiple targets allowed like ``make clean main``


Memory management
-----------------
+ Memory sections for C++ programs

  * static
  * code
  * stack
  * heap

+ Pointer data-type revisit

  * stores memory address
  * e.g. ``int *intPointer1;`` to define a pointer to point to an int value
  * dereference operator \*: ``cout << *intPointer1;``
  * reference operator &: ``int *intPtr1 = &a``
  * ``nullptr``
  * range not checked, need to be carefully managed by the programmer

+ Dynamic array
+ new and delete operators

  * new creates the data structure in heap memory and returns a pointer (or
    array):

  .. code-block:: c++

    int int *intPtr = new int;
    int *array1 = new int[10];
    MyClass *myObj = new MyClass();

  * delete destruct the data structure the pointer is pointing to and release
    the memory:

  .. code-block:: c++

    delete intPtr;
    delete [] array1;
    delete myObj;

+ memory leak

  * only happens in the heap memory region
  * new operations without corresponding delete operations

+ memory management in classes

  * implicitly-declared methods
  * shallow copy
  * the big three

    - what are they - destructor, copy constructor, copy assignment operator
    - when are they needed
    - how are they triggered
    - how to implement

+ reference type

  * implicitly stores memory address
  * mostly used when passing/returning values to/from a function

Algorithm Analysis
------------------
+ Complexity

  * Essential resources used by an algorithm

    - time :math:`T(n)`
    - space :math:`S(n)`

  * algorithm may not have a constant complexity

    - best case
    - worst case (most important)

  * growth of an algorithm complexity

    - lower bound - best case
    - upper bound - worst case
    - exact bound - when upper and lower bounds are same

+ Analysis

  * Big O - most important
  * Big :math:`\Omega`
  * Big :math:`\Theta`
  * :math:`T(n)` estimation - important

    - approximation: treat each statement or expression as a constant time
      operation

+ Calculation

  * addition: more complex one dominate less complex ones:

    :math:`\Theta(1) + \Theta(n) + \Theta(\log n) = \Theta(n)`

  * multiplication, e.g. :math:`\Theta(1)*\Theta(n)*\Theta(\log n) = \Theta(n
    \log n)`
  * Simplification of :math:`\Theta(f(n))`

    - :math:`\Theta(3n^2+5n+10) = \Theta(n^2)`

+ Know the complexities of well-known algorithms

  * search
  * sort
  * sequence comparison (array equal, palindrome)

Recursion
---------
+ function call mechanism

  * one stack frame in stack memory per function call
  * keeps local variables and formal parameters in the stack frame
  * may overflow

+ a function that calls itself (directly or indirectly)
+ may be an alternative way to write iterative algorithms
+ recursive definition

  * e.g. factorial, Fibonacci, binary search, merge sort
  * base case - where the recursion may stop at
  * recursive case - where the same algorithm is applied to a smaller/simpler
    case
  * may have multiple base cases and recursive cases
  * may need helper functions

+ recursive thinking

  - translate recursive definition to code
  - rewrite iterative algorithms in a recursive way

+ recursion complexity analysis

  - recursion trees diagram
  - how many round of recursive call

    * how problem size reduced in each round

  - time/space complexity each round

Frequently Tested Contents
==========================
+ **Finish coding on paper or in plain text editor like notepad**
+ **Write a full program with multiple files**
+ **Write a full class**

  * single file or multiple file
  * inline or not inline
  * with the **big-three**

+ Write function/class according to usages/tests
+ Calculate :math:`T(n)` given a snippet
+ Pass-by-ref functions/methods
+ Recursive algorithms as functions
+ Pitfalls! Find them in the notes. Some are listed here.

  * disposable object syntax ``patients[i] = Patient("John", 23);``
  * constructor triggering. E.g. copy constructor vs copy assignment
  * constructor only syntax: no return type, initializer list
  * not releasing old data in copy assignment operator overloading
  * missing destructor
  * use public/private as method prefix rather than sections
  * forget ; after } in class declaration
  * confuse :math`T(n)` with :math`\Theta(f(n))`
  * confuse ``delete`` with ``delete []``
  * confuse ``.`` with ``->``
  * confuse additive and multiplicative in analysis
  * recursive function with no termination cases
  * confusion in the order of big-O. e.g. :math:`\Theta(\log n) > \Theta(n)`