Week 1: Algorithm Analysis

Algorithm Analysis:

Terminology:

• Empirical analysis — involves implementing and running the algorithm and plotting a graph of time taken vs. input size
• Theoretical analysis — involves determining running time as a function of input size, n. *independent of hardware and programming language (we can analyse pseudocode in terms of the number of primitive operations — maximised in the worst case)
• Primitive operations — accessing an array index, calling functions, evaluating expressions, assigning values to variables, etc.

Big-O Notation (Time Complexity):

• Formal definition — "if there exists positive constants c and b such that f(n) ≤ cg(n) holds for all n > b, then f(n) is O(g(n))"

  Eg.

  

  • It is true that "2n is O(n²)", however we want the smallest class of functions, so we say "2n is O(n)"

• Big O — upper limit (worst case) f(n) ≤ cg(n) Big Θ — average range f(n) ≥ cg(n) Big Ω — lower limit (best case) c'g(b) ≤ f(n) ≤ c''g(n) The worst case time-complexity is generally the most important to discuss

• Polynomials: for f(n) with degree d, f(n) is O(nᵈ)

• For finding the worst case in recursive algorithms, we must understand the logic and work out how many steps are taken to reach the base case

• Complexity classes

• Generate and test algorithms: Useful when it is simple to generate new states and test whether they are a solution. This guarantees we either find a solution, or prove none exist. Eg. Checking primality by generating 2 to n-1 numbers and testing them

• Big-O is not about the exact number of operations. It's about how the number of operations changes with respect to input size. A function with O(1) complexity (constant time) could take 0.000001 seconds to execute or two weeks to execute.

Time-complexity for different operations on common data structures:

Examples: O(1)

void swap(int a[], int i, int j) {
		int tmp = a[i];  // O(1)
		a[i] = a[j];     // O(1)
		a[j] = tmp;      // O(1)
}                    // Total: O(1)

O(n)

for (int i = 0; i < n; i++) {
		// Some O(1) statements
}   // Total: O(n)

O(n²)

for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
				// Some O(1) statements
		}
}   // Total: O(n²), basically just counting how many times the innermost
    //        statements get executed, relative to n

O(logn)

for (int i = 0; i < n; i *= 2) {
		// Some O(1) statements
}   // Total: O(log₂n)
// Eg. for n = 100, the loop will execute log₂(100) times, 
//     which is 6 or 7 times

Week 2: ADTs

Abstract Data Types:

• Abstract data type: Abstract data types provide a separation between the interface and implementation. The interface only presents high-level functions that can be performed and their pre-conditions and post-conditions without us being concerned with how they are implemented
  • Users of the ADT see and use only the interface, so they are completely unaware of the underlying implementation of it
• The interface (header file) provides just the function signatures/prototypes and a description of their semantics
• Collections: Many ADTs are a collection of items, which might be simple types with an associated key.
  • Collections are categorised in terms of structure: linear, branching, cyclic, or in terms of usage: set, matrix, stack, queue, search-tree, dictionary
  • Typical functions: create(), insert(), remove(), find(), display(), etc.

Set ADT example: A typical abstract set data structure may support the declare the following functions in its header file:

Set newSet();
void freeSet(Set s);
void displaySet(Set s);
void setInsert(Set s, int data);
void setRemove(Set s, int target);
bool setIsMember(Set s, int target);
Set setUnion(Set s, Set t);
Set setIntersection(Set s, Set t);
int setCardinality(Set s);

• ADTs are also expected to implement error-handling to check that things like pre-conditions, post-conditions and whether or not the input is a valid value

Time-complexities for a set implementation using various underlying data structures:

As the person implementing an abstract data type for other users, after you decide what functions you want to supply, you have to go through each possible implementation and compare the set of time-complexities for each implementation. You choose the appropriate implementation based on which functions are most important to the specifications.

• Eg. if deletion is a common operation, then a bit-map may be the best underlying data structure to choose for implementing your set ADT

Week 3: Trees I — Binary Search Tree Basics