Midterm 2 Topic Review

How to use this document

• All contents covered in Midterm I will not be specifically tested but will likely to be used in the questions.
• 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

Pointer, Memory Management

• Memory regions
  • code: code
  • static: global and static variables
  • stack: local variables and function parameters
  • heap: dynamic data
• Pointer type
  • declaration; derived type with *
  • reference operator & (variable -> it’s memory address)
  • dereference operator * (memory address -> variable/lvalue it points to)
  • nullptr
  • segmentation error (trying to access an invalid pointer)
• Dynamic data
  • new keyword
  • delete keyword
  • new and delete arrays with []
  • memory leak and how to avoid
• Differentiate from reference type
  • revisit reference type
  • know the difference

Algorithms

• C array
  • local array int arr[10];
    • size must be literal or constant
  • dynamic array int *arr = new int[10];
  • [] and * syntax interconversion arr[n] vs *(arr + n)
  • two parts in memory: pointer and data
    • local array - both parts are local
    • dynamic array - pointer is local, data is in heap
  • local array initialization syntax int arr[10] = {};
  • initialization of dynamic arrays using for loops
  • local/dynamic arrays as function parameters
  • dynamic array as as return type
• C string
  • partially filled char array
  • terminator ‘\0’ character
  • cstring header
    • strlen
    • strcmp
    • strcpy
    • strcat
• C++ string
  • methods (member functions)
  • extraction getline mixed usage
    • do-while loop to protect getline
• Building blocks of algorithms
  • for loops
  • while loops
  • degree of freedom
  • index manipulation size - 1 - i
  • know the meaning of looping variables
• Algorithms on linear data types (C array, C string, and C++ string)
  • search
    • element
    • sub sequence
    • early return
  • compare
    • two arrays - are same or are reverse
    • internal - is a palindrome
    • early return
  • aggregate/reduce
    • sequence -> single value
    • must visit all element
  • map
    • sequence -> sequence of the same size
    • can be in-place
  • filter
    • sequence -> shorter sequence
    • to be covered when vector is introduced
  • sort
    • selection
    • insertion

Advanced Array

• Multidimensional array
  • array of arrays concept (diagrams)
  • declaration
  • initialization with nested loops
  • for loop manipulation - nested
  • dynamic 2D array
    • new []
    • delete []
    • for loop
  • as function parameters
    • [] syntax - last size can be omitted
    • • syntax (preferred)
  • as a return value
    • dynamic array
  • algorithms
    • tasks done on each row/column
    • flip vertically/horizontally
    • transpose
• Object array
  • to model 2D relational table (like excel tables)
  • temporary object assignment patients[i] = Patient("John Smith", 21, 173);

Frequently Tested Contents

• must be able to finish coding on paper or plain text editor like notepad

• Write a full program project in a single file

• Write a full program project with multiple files

• text menu handling

• input with validation

• expressions with pointer/array

  • know pointer operators *, &
  • example expressions
    • e.g. if int *a = &b, the *a is same as b
    • arr[n] *(arr + n)
    • (*a)++

• C string algorithms

  • char array declaration
  • for loop based on the terminator ‘\0’
  • 1 extra space to store data
  • existing string functions: strlen, strcpy, strcmp, strcat

• dynamic array

  • why using dynamic array
  • memory allocation with new
  • memory release with delete []

• difference of in-place vs out-of-place algorithms

• 1D array algorithms IMPORTANT

  Know how to write; know how to mimic the run on paper.

  • search
  • compare two arrays, compare internally
  • sort
  • aggregate/reduce - sum, average, count, etc.
  • map

• array as function parameter

• dynamic array as the returned value of a function

• user input with mixed extractions and getlines

• 2D array

  • as function parameters very tricky!
  • allocation using for loop
  • delete using for loop
  • initialization using for loops

• 2D array algorithms

  • flip
  • transpose
  • rotate
  • initialize to a specific format

Pitfalls

• pointer
  • referring to an uninitialized pointer
  • mismatched assignment, parameter passing
    • int *a = b; // b is an int
• array
  • out of boundary index cout << arr[size];
  • mismatched passing
    • cout << average(arr[size], size);
    • cout << average(arr[], size);
  • pass without size cout << average(arr);
  • Java syntax int []arr; double average(double [] arr, int size);
  • using initialization syntax for assignment int arr[4]; arr = {1,2,3,4};
• 2d array
  • new with more than one [] int **twoD = new int[3][4]
  • bad function parameter
    • void flip(int twoDimArr[rows][cols], int rows, int cols);
    • void flip(int twoDimArr[][], int rows, int cols);
    • void flip(int [][] twoDimArr, int rows, int cols);
• dynamic array
  • Java syntax int [] arr = new int[10];
  • forget to delete []
  • use delete without []
  • 2D
    • new or delete using more than one []