Notes on CS2040S from Week 2 Lecture 1

CS2040S_w2l1.md

CS2040S Week 2 Lecture 1

Notes from Week 2 on Data Structures and Algorithms.

Miscellaneous

• Midterm Exam: Week 7

Algorithm Analysis

Time Complexity Analysis

As we scale, we want to see which algorithms are faster for large inputs ie. asymptotic performance. T(n) is the running time of an algorithm.

Setting upper bounds
We use Big O notation to specify the upper bound on an algorithm.
By definition, T(n) = O(f(n)) if there exists a constant c > 0 and there exists a constant n_0 > 0 such that for all n > n_0, T(n) ≤ cf(n). Proving T(n) = O(n^2):

T(n) = 4n^2 + 24n + 16
     < 4n^2 + 24n^2 + n^2 
     = 29n^2 
     = O(n^2) for c = 29

Setting lower bounds
We use the Omega notation to specify a lower bound on an algorithm.

Setting tight bounds
We use the Theta notation to specify a tight bound on an algorithm.

Simple rules for time complexity

1. Order of size: 5 < loglog(n) < log(n) < log^2(n) < n < nlog(n) < n^2 < n^3 < n^n < n!
2. Time complexities of functions called successively are added and simplified based on highest power
3. Time complexities of functions called within each other are multiplied and simplified

Model of Computation

• Sequential (RAM)
• Parallel (PRAM, BSP, Map-Reduce)
• Circuits
• Turing MAchine
• Counter Machine
• Word RAM model
• Quantum Computation

Sequential Computer

All operations take constant time (addition, substraction, multiplication, comparison) and are performed one after the other.

• String concatenation
  • concatenation is not constant since the string is recreated every time (in Java)
• Loops
  • cost = # iterations * max cost per iteration
• Nested Loops (same as Loops)
  • cost = # iterations * max cost per iteration
  • consider how many times the inner loops run for
• Sequential Statements
  • cost = cost of first + cost of second
• Conditional Statements
  • cost = max(cost of first, cost of second) <= cost of first + cost of second
• Recursive Functions
  • consider the number of times function is called + cost per iteration in the general case
  • solve the recurrence relation to get time complexity

Note: Not everything in reality takes constant time.

Searching

Binary Search

• The array must be sorted
• The array must have fixed size
• The algorithm should not tamper with the indices or array contents
• The index of the target is within the range of the array
  • Error handling can be used to check whether the target index is within this range
• We use a divide/reduce and conquer strategy
  • Continuously get a middle pivot and compare with target
  • Based on face value, look at the correct half of the array
  • Repeat

public boolean binarySearch(int target, int[] arr) {
	// assumes array is sorted
	int start = 0;
	int end = arr.length;

	while (start < end) {
		int pivot = start + end) / 2;
		
		if (arr[pivot] > target) {
			end = pivot - 1;
		} else if (arr[pivot] < target) {
			start = pivot + 1;
		} else if (arr[pivot] == target) {
			return true;
		}
	}
	
	return false;	
}

Invariants
Relationship between variable sthat is always true

Loop Invariant
Relationship between variables that is true at the beginning or end of each iteration of a loop