KMS (algo ver.)

for solving problems with overlapping subproblems; solve each smaller subproblem once and record results in a table to derive the overall solution

Dynamic Programming

Time complexity of Dijkstra’s Algo (adjacency matrix + array)

O(V²)

Time complexity of Dijkstra’s Algo (adjacency list + min heap)

O(ElogV)

Apply to optimization problems for difficult combinatorial problems such as Knapsack Problem (Best first rule)

branch and bound

Apply to nonoptimization problems such as N queens, Knight’s tour, and Hamiltonian circuit (DFS)

Backtracking

Upper bound formula for Knapsack Problem

ub = (tot value so far) + (rem cap)(next best ratio)

Knapsack problem worst case time complexity

O(2^n)

Tractable

solvable in polynomial time

Intractable

Not solvable in polynomial time

P

Class P, decision problems solvable in polynomial time

Undecidable

Decision problem that cannot be solved by any algorithm

NP

Non deterministic polynomial class of decision problems solvable by non deterministic polynomial algorithms:
1) Generate candidate solution
2) Verify solution’s validity in polynomial time

NP complete

Set of problems in NP reducible to any other NP problem in polynomial time. Examples such as TSP, Knapsack, SAT.
(if one problem can be solved in P time, all other NP complete problems can also be solved in P time)

NP Hard

Every NP problem can be reduced to it in polynomial time but not vice versa. May be undecidable like the Halting Problem

Sequence of unambiguous instructions for solving a problem in a finite amount of time

Algorithm

Euclid’s GCD

gcd(m,n) = gcd(n,mmodn)

Why do we measure growth

to understand how performance scales with input size

Stable

Preserves the relative order of elements

In place

Does not require extra memory to sort

Bubble sort Worst case, stable or not?, in place or not?

O(n²), stable, in place

Selection sort Worst case, stable or not?, in place or not?

O(n²), in place

counting sort Worst case, stable or not?, in place or not?

O(n+k), stable

Insertion sort Worst case, stable or not?, in place or not?

O(n²), stable, in place

Sequential search worst case

O(n)

Binary Search worst case

O(logn)

Find the shortest tour through n cities that visits each city exactly once with the least cost via exhaustive search; generate the Hamiltonian circuit

Traveling Salesman Problem

Traveling Salesman Problem worst case

O((n-1)!) = (n!)

Traveling Salesman Problem worst case (undirected)

O([(n-1)/2]!) = (n!)

Search where examine each element linearly until key is found

Sequential search

Repeatedly halves the search space until key is found

Binary search

sorts integers by counting the number of occurrences of each distinct value in the input

Counting sort

Iterates through unsorted elements and and inserts them into sorted portion

Insertion sort

Lower or same order of growth

O notation

Same or higher order of growth

Omega notation

bounded above and below; exact order of growth

Theta Notation

Given n points on a plane, find the closest pair exhaustively by considering every pair of points (Give worst case time complexity)

Closest pair problem O(2^n)

Exhaustive traversal of a graph. Visits adjacent vertices until no adjacent unvisited vertices (dead end). Uses a stack to trace operation. Checks connectivity and acyclicity. Tree and back edges.

Depth first search

Visits all vertices adjacent, then all unvisited 2 edges apart, until all visited. Uses a queue to trace operation (enqueue when discovered as neighbor, deque when visited). Checks connectivity and acyclicity. Cross edges. Checks for minimum edge path (path with the least edge count).

Breadth first search

Top down approach

Recursive

Bottom up approach

iterative

Decrease and conquer: reduced by the same constant with O(n) complexity

Decrease by a constant

Decrease and conquer (recursion): reduced by a constant factor (division) with O(logn) complexity

decrease by a constant factor

Problem divides into subproblems, sorted, then combined to get solution
T(n) = aT(n/b) + f(n)

Divide and Conquer

Mergesort worst case, in place?, stable?

O(nlogn), stable

Depth first search and BFS complexity

O(n²)

Quicksort worst case, stable?, in place?

O(n²), inplace

Divides an array according to their partition (using first element Hoare’s partition).

Algo:
From left to right, stop when element is >= p, from right to left, stop when element is <= p. Swap elements if i and j have not crossed

If i and j have crossed, partition is complete where j is split partition position

Quicksort

Preorder traversal

root-left-right

inorder traversal

left-root-right

Postorder traversal

left-right-root

Technique where problem instance is modified to be more amenable to the solution and problem instance is solved

Transform and conquer

Transformation to a simpler or more convenient instance of the same problem

Instance simplification

Transformation to a different representation of the same instance

Representation change

Transformation to an instance of a different problem for which an algorithm is already available

Problem reduction

A binary tree with keys assigned to its nodes provided that it is complete (filled to the last level as far left as possible w/o gaps) and there is parental dominance

Heap

Max heap

Largest key at root

Preprocess the problem’s input and store information obtained to accelerate solving

Input enhancement

Some processing is done before solving but deals with access structuring (for faster accessing)

Prestructuring

Technique for resolving collisions using linked lists in a hash table

Open hashing

Technique for resolving collisions using linear probing in a hash table

Closed hashing

A greedy grab of the best alternative available in the hopes that a sequence of locally optimal choices will lead to a globally optimal solution to the entire problem. Each step where a choice is made, must be feasible, irrevocable, and locally optimal

Greedy technique

A subset of edges in a weighted, connected, and undirected graph that connects all vertices without cycles while minimizing the total weight of the edges

Minimum spanning tree

Constructs a mst through a sequence of expanding subtrees by attaching to the nearest vertex not already in the tree but connected to any vertex in the tree

Prim’s algorithm for vertices

Constructs an mst as an expanding sequence of subgraphs that are always acyclic but not necessarily connected during construction

Kruskall’s algorithm for edges

Heap time complexity

O(logn)

Construct a heap for an array and apply root deletion operation n-1 times

Heapsort

Place keys in tree in given array order and heapify

Bottom up heap construction

Attach key to the last leaf of existing heap and sift upward to its place

Top down heap construction

Where parental node keys are stored in first floor(n/2) positions and leaf keys are stored at last ceil(n/2) positions, and parents position i corresponds to children's position 2i and 2i+1. 0th element is unused or a sentinel value greater than every element in the heap

Using an array to store the heap

Heapsort with an increasing sorted array Time complexity, array is inplace?, stable?

O(nlogn), inplace