Unit 1

Basic Non-Recursive

ALGORITHM MaxElement (A[0..n-1])
	maxval <- A[0]
		for i <- 1 to n-1:
			if A[i] > maxval:
				maxval <- A[i]
		return maxval
		
// O(n) complexity

Algorithm UniqueElements(A[0..n-1])
// checks whether all the elements in a given array are distinct

for i <- 1 to n-2 do:
	for j <- i+1 to n-1 do:
		if A[i] = A[j] return false

return true

// worst case O(n^2)

Algorithm MatrixMultiplication(A[0..n-1, 0..n-1], B[0..n-1, 0..n-1])
// multiplies 2 square matrices of order n 

for i <- 0 to n-1 do:
	for j <- 0 to n-1 do:
		C[i, j] <- 0.0
		
		for k <- 0 to n-1 do:
			C[i, j] <- C[i, j] + A[i, k]*B[k, j]
return C

// O(n^3)

Basic Recursive

Algorithm Fact(n)
// computes n! recursively

if n = 0 return 1
	else return Fact(n-1)*n

Algorithm Bin(n)
// outputs the number of binary digits in n's binary representationn

if n=1 return 1
else return Bin(floor(n/2)) + 1

Algorithm ToH(n, src, aux, dest)
	if(n=0) return
	ToH(n-1, src, dest, aux)
	Move disk n from Src to Dest
	ToH(n-1, aux, src, dest)

Brute Force

Algorithm SelectionSort(A[0...n-1])
// sorts a given array by selection sort

for i <- 0 to n-2 do:
	min <- i
	for j <- i+1 to n-1 do:
		if A[j] < A[min] 
			min <- j
	swap A[i] and A[min]
	
	// O(n^2)

Algorithm BubbleSort(A[0...n-1])
// sorts a given array by bubble sort

for i <- 0 to n-2 do:
	for j <- 0 to n-2-i do:
		if A[j+1] < A[j]
			swap A[j] and A[j+1]
			
// O(n^2)

Algorithm SequentialSearch(A[0..n], K)
// sequential search with a key

A[n] <- K
i <- 0

while A[i] != K do:
	i <- i+1
if i<n return i
else return -1

// O(n)

Algorithm BruteForceStringMatch(T[0..n-1], P[0..m-1])
// T = text, P = pattern

for i <- 0 to n-m do:
	j <- 0
	while j<m and P[j] = T[i+j] do:
		j <- j+1
		
	if j = m return i
	
return -1

// m(n-m+1) comparisons
O(nm) time complexity

Unit 2

Decrease and Conquer

Algorithm InsertionSort(A[0..n-1])
// sorts a given array by insertion sort

	for i <- 1 to n-1 do:
		v <- A[i]
		j <- i-1
		
		while j >= 0 and A[j] > v do:
			A[j+1] <- A[j]
			j <- j-1
		A[j+1] <- v
		
		// Worst and avg O(n^2), best O(n)

Algorithm SourceRemoval_Toposort(V,E)

L <- Empty list that will contain the sorted vertices
S <- Set of all vertices with no incoming edges

While S is non-empty do:
	remove a vertex v from S
	add v to tail of L
	
	for each vertex m with an edge e from v to m do:
		remove edge e from graph
		insert m into S
	
	if graph has edges then:
		return error (not a DAG)
		
	else return L (a topologically sorted order)

Algorithm JohnsonTrotter(n)
// generates permutations
initiate the first permutation with 1,2,......n
while last permutation is a mobile element, do:
	find largest mobile number k
	swap k with the adjacent element k's arrow points to
	reverse direction of all elements larger than k
	add new permutation to the list

Algorithm LexicographicPermute(n)
// generates permutations in lexicographical order
initialize 1st permutation
while last permutation has 2 consecutive elements in increasing order do:
	let i be the largest index such that a_i < a_(i+1)
	find largest index j such that a_j > a_i
	swap a_i with a_j
	reverse order of elements from a_(i+1) to a_n inclusive
	add new permutation to the list