Learning materials

Midterm 1 Topic Review

On this page

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 *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

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