Lab 3

When using a range based for loop, be careful if you are assigning the value of i to a variable that is type T&

The reference points to undefined memory

// BAD
void f(..., T& x) {
    for (auto i : vec) 
    {
        x = i;
        // this will not work!
    }
}
// BETTER
void f(..., T& x) {
    for (auto& i : vec)  // added auto&
    {
        x = i;
        // this will work!
    }
}

Arrays and Linked Lists

For array, everything is contiguous memory

Linked list is not contiguous memory

Given a pointer to an element, insert a new element after: Linked List is better O(1), array is O(n) since you have to shift all the element downstream

Given an index, update an arbitrary element: Array is best since addresses are stored O(1)

Search on sorted container: Array is good since you can random access, even binary search

Prefer vectors over "naked" arrays, even if you have to insert into the middle

Amortized Complexity:

If you apply the operation many times, what is time when on a sequence/sum of tasks

"Average" implies randomness - either random independent inputs or algorithm randomness

Amortization is NOT random - it is guaranteed

Total amortized time is an upper bound on the total actual time

Amortized != Average, Amortized is on many inputs, Average is on one input

Amortized Complexity: "How slow is an operation when you use it many times?"

• Sequential inputs, over a designed path (not random)
• Add elements to a vector repeatedly

Example: 
Perform Operation n times in a designed sequence
Total time is T
Amortized Time: T/n

Average Complexity: Looking at one operation over a random path

Vectors w/ push_back and grow

STL C++ strings are typically optimized over C strings, so C++ strings are better to use

POP QUIZ

Reverse a C-string - HOME EXERCISE

void reverse(char* str) {
    if(!str) return;  // empty c-string
    char* end; // need to find the end
    end = str;
    while(*end) ++end;
    --end;
    while(str < end) {  // avoid reversing twice  (why not '!='?)
        char temp = *str;
        *str++ = *end;
        *end-- = temp;
    }
}

C-Strings: just arrays

const char* array = "YOLO";
// read only
char array[] = "YOLO";
// puts '\0' at the end automatically
char* array = new char[5];
// no null '\0' at the end

C++ Strings: objects of string class

• Encapsulation of necessary functions: object.length( ) in C++ vs strlen(object) in C

Lab 3 Coding Problem - Given a target number, find an string expression that uses all numbers 1-9 and arithmetic operators that evaluates to the target number

• Recursive Generation OR Recursive Selection OR
  Iterative Incrementing

RECURSIVE SELECTION
string solution_with_prefix(string prefix, int target) {
    if (prefix.back() == '9')
        if (eval(prefix) == target)
            return prefix;
        else
            return "no solution";
    }
    char next_digit = prefix.back() + 1;
    string answerNone = solution_with_prefix(prefix + digit, target);
    string answerPlus = solution_with_prefix(prefix + "+" + digit, target);
    string answerMinus = solution_with_prefix(prefix + "-" + digit, target);

    if (answerNone != "no solution")
        return answerNone;
    if (answerPlus != "no solution")
        return answerPlus;
    if (answerMinus != "no solution")
        return answerMinus;
    return "no solution";
}

string solve(int target) {
    return solution_with_prefix("1", target);
}