Algorithms

Question 1

Lomuto’s

Answer 1

1. start with s at pivot and i at s+1
2. when item is smaller than pivot, increment s and then swap s with i

Question 2

QuickSort

Answer 2

if(left < right):
split = partition
sort left half and right half

Question 3

ways to improve QuickSort

Answer 3

1. better pivot selection
2. do insertion sort on smaller sets
3. eliminate recursion

Question 4

selection (find nth biggest value)

Answer 4

1. sort set
2. find nth value

Question 5

quickselect (find nth biggest value)

Answer 5

1. choose pivot
2. partition & place pivot
3. if n < pivot, search in left half
4. if n > pivot, seach in right half
5. else, you found it!

Question 6

Master Theorem
T(n) = aT(n/b) + n^d

Answer 6

a < b^d: theta (n^d)
a = b^d: theta (n^d logn)
a > b^d: theta (n^(logb (a) ) )

Question 7

Closest Pair

Answer 7

1. sort points by x coordinate
2. divide set into left and right halves on graph
3. find the closest pair in each half & assign the smaller distance to D
4. put points on within either side of the vertical line by a distance of D in a separate array
5. sort this array by y coordinates
6. for each point, consider only pairs that are within D distance away from each other
7. find the closest pair in this set and set its distance to D’
8. the closest pair is one of the minimum between D and D’

Question 8

Generic Graph Search

Answer 8

1. mark source as explored, all others unexplored
2. while there is an edge (v, w) with v explored & w unexplored:
3. choose some edge w (in an alg specific way, depending)
4. mark w as explored

Question 9

Proof of GraphGenericSearch

Question 10

What is BFS (Breadth-First Search)?

Answer 10

looks at a graph in layers. layer 0 is the root, layer 1 has the neighbors of the root, layer 2 has the neighbors of the neighbors, etc.
- best used for shortest path distances

Question 11

How to implement BFS in linear time (O(n)) using a queue?

Answer 11

1. mark the source explored, initialize Q
2. while Q is not empty:
3. remove the vertex from the front of the queue and call it v
4. for each edge (v, w) in v’s adj list:
5. if w is unexplored, then add it to the end of Q and mark it explored

Question 12

What is a Queue?

Answer 12

First in - first out DS

Question 13

What is Depth-First Search (DFS)?

Answer 13

go as deep as you can and only backtrack when necessary
- special case of generic graph search

Question 14

How to implement DFS in linear time (O(n)) using recursion?

Answer 14

1. mark source explored
2. for each edge in S’s adj list, if V is unexplored, then DFS (G, V)

Question 15

How to implement DFS in linear time (O(n)) using a stack?

Answer 15

1. mark all vertices unexplored, initialize a stack
2. while S is not empty:
3. pop V from front of S
4. if V is unexplored, then mark it explored. for each edge in v’s adj list, push W to the front of S

Question 16

What is a Stack?

Answer 16

Last in - first out DS

Question 17

What is topological sort?

Answer 17

an ordering that follows the directions in a directed graph
- can only occur in graphs that do not have directed cycles

Question 18

How to use DFS to compute topological sort of a directed acyclic graph?

Answer 18

1. mark all vertices explored
2. curlabl

Question 19

What is a strongly connected component (scc)?

Answer 19

A maximum subset of vertices such that there is a directed path from any vertex to any other vertex in the subset

Question 20

How to use DFS to compute the strongest connected components of a directed graph?

Answer 20

Kosaraju’s algorithm:
1. Grev = graph with directions reversed
2. Call DFS on each V of Grev to find position f(v) for V
3. Call DFS on each V of G from highest to lowest f(v)

Question 21

Kosaraju pseudocode

Answer 21

1. First pass of DFS computes f(v): TopoSort(Grev)
2. Second pass of DFS finds SCC in reverse topological order
   Mark all V unexplored, #scc = 0
   For each vertex, in increasing order of f(v):
   If V not explored, then SCC++ & DFSSCC (G,v)

Question 22

2 basic operations of heaps

Answer 22

1. Insert into heap
2. Extract min (value with smallest key)

Question 23

When to use a heap?

Answer 23

When application requires fast min or max computations on a dynamically changing set

Question 24

Heapsort

Answer 24

1. Insert all items into heap
2. Extract min n # of times

Question 25

Dijkstra’s

Answer 25

1. initialize a table with source = 0, everything else = ∞
2. for the node of focus, update the adj nodes with their cost. if sum thus far + weight < previously assigned weight, change it. otherwise dont.
3. pick the smallest value node
4. continue

Question 26

Prove Dijkstra’s

Answer 26

see image

Question 27

Scheduling Problem: specifies the order in which to do certain jobs for fastest completion time

Answer 27

total time = work(sum of times before it) + work …. and so on

Question 28

What to do when there are 2 attributes in greedy algorithms?

Answer 28

check if differences or ratios work better

Question 29

cut and paste technique

Answer 29

the optimal solution is made up of optimal subsolutions

Question 30

steps to the cut and paste proof

Answer 30

1. lets assume the algorithm is not optimal
2. then lets replace the suboptimal subsolutions with optimal* ones
3. by assumption, the solutions is already comprised of optimal solutions.
4. therefore the algorithm must be optimal

Question 31

memoization

Answer 31

1. fill in the table
2. traceback

Question 32

Prim’s

Answer 32

1. choose a source
2. follow 3 - 4 until done
3. identify fringe vertices
4. choose minimum out of those and add it to MST if it DOES NOT form a cycle
5. return & exit

Question 33

kruskals

Answer 33

1. sort edges in increasing weight order
2. keep picking smallest edge while cycle is not created