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

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

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
```
<target> : <dependencies/prerequisites>
        <recipe/commands>
```
- example
```
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 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):
```
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:
```
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

Complexity
- Essential resources used by an algorithm
  - time \(T(n)\)
  - space \(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 \(\Omega\)
- Big \(\Theta\)
- \(T(n)\) estimation - important
  - approximation: treat each statement or expression as a constant time operation
Calculation
- addition: more complex one dominate less complex ones:
  
  \(\Theta(1) + \Theta(n) + \Theta(\log n) = \Theta(n)\)
- multiplication, e.g. \(\Theta(1)*\Theta(n)*\Theta(\log n) = \Theta(n \log n)\)
- Simplification of \(\Theta(f(n))\)
  - \(\Theta(3n^2+5n+10) = \Theta(n^2)\)
Know the complexities of well-known algorithms
- search
- sort
- sequence comparison (array equal, palindrome)

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

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 \(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. \(\Theta(\log n) > \Theta(n)\)