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 []