index.org

Studying for CSI3105

Note, I recommend cloning the repo for this and opening the org file in emacs, because then the links can be opened inside emacs, it’s more clean.

./Introduction—Part-1.pdf

• What does “design & analsis of algos” mean?
  • Correctness
  • Does it terminate?
  • Efficiency
  • Limits thereof
  • Pseudocode, no programming
• Insertion sort
  • This is the one where we start at a position and then swap backwards until it fits into place
  • ~~O(n^2)~~ in the worst case
• Big O notation
  • Big Omega (which is the less than one)
  • Big Theta (Which is the greater than one)
  • What it means to be each one
• Barometer instruction
  • One which is executed at least as often as any other one
• Limit Criterion
  • lim(f(n)/g(n))
    • Goes to 0 if f = O(g)
    • Goes to infty if f = Omega(g)
    • Goes to a real if f = Theta(g)
    • If not exist, dunno

./Introduction—Part-2.pdf

• The fibonacci numbers
  • Calculating the running time of fib(n)
  • fib(n) is exponential, but fib2(n) is not, because two n-bit numbers can be added together in a linear number of bit operations

./Chapter-2—Part-1—MergeSort.pdf

• Divide and conquer algorithms
  • Divide the problem
  • Conquer each subproblem recursively
  • Combine
• Merge sort
  • If size = 1: do nothing
  • if size >= 2: divide n numbers into two sequences, run merge sort twice, and merge it back into a sorted sequence
• Computing runtime of merge sort
  • T(n) = c if n=1, or 2T(n/2) + cn if n >= 2
  • Solving by unfolding
    • All steps are outlined in document
  • We find T(n) <= 2cnlog_2(n)
  • Therefore merge sort is Theta(n log_2(n)) if n is a power of 2

./Chapter-2—Part-2—StrassenAlgorithm.pdf

• What is matrix multiplication?
• Trivial algorithm: triple for loop
• Strassen algorithm
• How can we divide and conquer?
  • Split A, B (inputs) into four separate matrices
  • Then compute the quadrants of C as products of these
    • We find no improvement.
  • However the strassen algorithm derives various intermediate matrices and then finds C as a prodcut of these matrices
    • (P_1 through P_7). Their calculations are in the notes.
    • It then derives the quadrants of C to be products of P1 through P7
  • After computing this through unfolding we then calculate that we have O(nlog_2(7) where log2(7) is approx 2.81
• There is also another algorithm by coppersmith and winograd, but that wasn’t covered, it’s very group theory heavy.

./Chapter-2—Part-3—MasterTheorem.pdf

• Master theorem
  • Let T be a function defined by parts. If
    • T(1) = 1
    • T(n) = a . T(n / b) + n^d where A >= 1, b > 1, d >= 0
      • If d > logb(a) then T(n) = O(n^d)
      • If d = logb(a) then T(n) = O(n^d log(n))
      • if d < logb(a) then T(n) = O(n^{logb(a)})
• They then use the master theorem on merge sort and strassen and binary search to find results.

./Chapter-2—Part-4—SelectionAlgorithm.pdf

• Selection algo
  • Find kth smallest number in array of n numbers
• Naive algo:
  • Sort S
  • return the element at position k
  • Runs in O(n log n)
  • Without sorting:
    • find pivot, go through array like quicksort, but instead of then sorting each sub-array, simply use the fact that it’s less than k to continually go inwards.
    • Quickselect
      • Worst case: O(n^2) if you pick bad pivots every time
      • Average case: O(n) because on average a random pivot will be close to median
      • Has a thing where they find a pivot

./Chapter-3—GraphsAlgorithms—Part-1—Intro.pdf

• Graphs!
  • Set of vertices and set of edges (V, E)
  • Graph is Undirected if each edge is a 2-set
  • Graph is Directed if each edge is an ordered 2-tuple
    • Facebook friends are undirected
    • Web page links are directed
• Adjacent edges (u, v)
  • if there is an edge between u and v.
• Incident vertex v to an edge
  • If one of the vertexes of the edge is v
• degree of u \in V
  • Equal to the num edges incident to u
• Outdegree of u \in V
  • Equal to num of edges e such that u is the starting point of e.
• Indegree of u \in V
  • Num of edges such that u is endpoint of edge
• Handshaking Lemma
  • Let G = (V, E). Then
    • Sum(deg(u)) forall u = 2|E|
      • proof: each edge counted twice lel
• How to store a graph
  • Adjacency matrix
    • In O(1) time we get whether two vertices are adjacent
    • Uses n^2 space
    • Finding all neighbours takes O(n) time
  • Adjacency list
    • Uses |V| + |E| space
    • Finding all neighbours of a vertex takes O(1 + deg(u)) time (depeneding on implementation of list)
    • Testing if (u, v) is an edge takes the same amount of time as finding all neighbours

./Chapter-3—GraphsAlgorithms—Part-2—ExploringUndirectedGraphs.pdf

• Depth first search
  • Find all vertices that can be reached from v \in V
  • Tracing of function via lines on graph?
  • It’ll generate a trees, and all the other edges are back cycles and stuff
  • Proves that DFS terminates
  • Proves that it visits all vertices that are reachable from v
    • This proof is worth reading
• Finding connected components of G = (V, E)
  • We have some algo DFS
  • Finding connected components is done by doing DFS on all unvisited nodes (which get filled out as one DFS call is done)
  • And then a number gets incremented
• Runtime:
  • First loop: O(|V|) time
  • Second loop:
    • explore(u) is called for each vertex u
    • Time spent in exlore(u) is O(1 + deg(u))
  • O(|V| + sum(1 + deg(u)) forall u) = O(|V| + |V| + 2|E|) = O(|V| + |E|)

./Chapter-3—GraphsAlgorithms—Part-3—ExploringDirectedGraphs.pdf

• Topological ordering
  • Exists on a graph that is directed and acyclic
  • such that for edge (u, v) #(u) < #(v)
  • Algo is:
    • find vertex with indegree 0
    • give u the num k
    • remove u from G
    • and so on and so forth
    • there is an example in the notes
• Prenumbers and Postnumbers
  • G = (V, E) is directed.
  • forall v \in V, the following two numbers with respect to DFS:
  • pre(v) is the first time we visit v
  • post(v) is the time when explore(v) is done
    • This uses a variable clock. Each time pre or postvisit number is assigned to a node, it gets incremented for next node
    • There is an example in the notes
    • Note: edges found in DFS are Tree edges
    • There is then a concept of forward and back edges
      • Edges going down the DFS tree are forward
      • Going up -> backwards
      • Cross edges go from one branch of the tree to another
        • Cross edges are neither forwards, backwards, nor tree edges. They are the remainder.
• To find the types of an edge:
  • Forwards:
    • (v, u) is not a tree edge
    • pre(v) < pre(u) < post(u) < post(v)
  • Back edge:
    • (v, u) not tree edge
    • pre(u) < pre(v) < post(v) < post(u)
  • Cross edge:
    • (v, u) not tree edge
    • pre(u) < post(u) < pre(v) < post(v)
• To determine whether a directed graph has a directed cycle:
  • Graph has cycle iff DFS-forest has back-edge
    • Proof in notes
  • If directed graph is cyclic:
    1. run dfs including pre/post nums
    2. for each edge test if edge is back edge (via inequality up top) 2.1 if yes then yes 2.2 if no then no
    3. Runtime: O(|V| + |E|)
  • How to compute a topolotical ordering?
    1. Run dfs
    2. Run bucket sort to sort vertices by postnumber
    3. obtain topological ordering from reverse sorted order of postnumbers
  • Bucket sort takes O(n) time, so runtime = O(|V| + |E|)
    • Proof of correctness in notes

./Chapter-3—GraphsAlgorithms—Part-4—Dijkstra.pdf

• Dijstra’s algo
  • input:
    • A directed graph G = (V, E) where each edge has a weight wt(u, v) > 0
    • a vertex s which is the source
  • Output:
    • For each vertex: \del(s, v) = len of shortest path from s to v
  • if all weights equal, this is easy, use BFS.
  • algo:
    1. for each vertex, maintain d(v), the current shortest known path
    2. start out with d(s) = 0, and d(!s) = \infty
    3. Loop:
       1. Pick a vertex u for which d(u) = \del(s, u).
       2. For each edge, (u, v), d(v) = min{d(v), d(u) + wt(u, v)}
          • But how to find u?
            • Maintain S \subset V such that for all v \in S:
            • d(v) = \del(s, v), (i.e. we know \del(s, v))
  • Algo runthrough done in notes
  • Store the set of nodes to visit in a min-heap
    • Initialization O(n)
    • One iteration:
      1. find u and delete it from Q.
         • O(log(n)) time
      2. For each edge, update d(v):
         • decrease_key : O(log(n)) time
    • Time total for iteration
      • O(log(n)) + O(outdegree(u) * log(n))
    • After some calculations, total runtime is O((m + n) log(n))
      • Note using Fibonacci heap to store Q we could do O(n log n + m time)

./Chapter-3—GraphsAlgorithms—Part-5—DijkstraCorrectness.pdf

• You know the drill, correctness proof for dijkstra’s
  • We say that a vertex v is special if all vertices on that path are in S (except v).
    • We prove by induction that if u \in S then d(u) is shortest

    path from s to u.

    • If it is not, then it is the shortest “special path” from s to u

Chapter-4—GreedyAlgorithms—Part-1—MakingChange.pdf

• Greedy algorithms arrives at a solution by making the best choice it can at any moment, and hope that locally-optimal solution leads to a global optima
• Example: determining the amount of change you can get [via the obvious algorithm, modulo and remainders]

Chapter-4—GreedyAlgorithms—Part-2—Knapsack.pdf

• The [0,1] knapsack problem
  • given:
    • n objects such that object i (1 <= i <= n) has a positive value v_i and a positive weight w_i
    • A maximum weight W
  • Output:
    • A vector X = (x_1, x_2, ... x_n) such that
      • 0 <= x_i <= 1
      • The total value Sum(map(mul, zip(X, Value))) is maximized
      • The total weight is not too heavy – Sum(map(mul, zip(X, Weight))) <= W
  • Solution:
    • Make greedy choices with respect to values per unit of weight
      • The proof is long and involves proving that the value for another combination has to have less or equal value via manipulating sums
  • this isn’t actually the “knapsack problem” that is typically found, this is a linear relaxation of said problem. We’ll cover the real knapsack problem maybe in chapter 5? [says the notes, but I don’t see them in the notes].

Chapter-4—GreedyAlgorithms—Part-3.1—MST.pdf

• Minimum spanning tree!
• given a graph G = (V, E) that is undirected and connected, each edge {u,v} has a weight wt(u,v).
  • We want to find a subgraph G' that is connected and has a minimum sum of all weights Sum(map(wt, E))
    • Trivially, it must be a tree [connected, but no cycles]
    • They give a few examples
• Fundamental lemma:
  • Given G, a weighted, undirected, connected graph, and two subsets of the nodes A and B where there is some minimum edge connecting A and B, then that edge must be in the MST.
  • Proof in notes
• Sidetrack into Union-Find data structures, also known as disjoint-set data structures:
• It’s just a data strucutre of sets that have two operations:
• Stored as a set of linked lists with the head containing the name, and each element containing a pointer to the head of their list
  • find(x) which returns the set in which is contained x
    • takes O(1) time because there is a pointer to the head
  • union(a, b, c) which takes three sets and modifies c = a \cup b, and a = b = nullset
    • a union op takes O(size(b)) time, because of setting pointers to change the head of the list
      • could also take min{map(size, a,b)} time by storing the size the head of the list
    • Time for n - 1 union operations is O(n log n)
      • Because doing unions ‘doubles (this is purely intuitive, it doesn’t actually double)’ the size of a set, you change the pointer for each element on average log_2(n) times

./Chapter-4—GreedyAlgorithms—Part-3.2—Kruskal.pdf

• Algorithm to find MST
  • Maintain a forest. In each step, add an edge of minimum weight that doesn’t create a cycle.
  • One iteration combines two trees using an edge of minimum weight
  • Store the edges by weight
• input: G = V,E, where V = {x_1, x_2, ...} and m = |E| and n = |V|.
• output: A minimum spanning tree of G.
• Algorithm:
  • Sort the edges by merge sort
  • for i = 1 to n do
    • V_i = {xi} [union-find data structure representation]
  • T = nullset
  • for k = 1 to m do
    • (u_k, v_k) = e_k
    • u_k \in V_i (here, i and j are speshul)
    • v_k \in V_j
    • if i != j
      • V_i = V_i \cup V_j
      • V_j = nullset
      • T = T \cup {{u_k, v_k}}
  • Return T
  • runtime:
    • Sorting: O(m log m) = O(m log n)
    • First for: O(n)
    • Second for:
      • T is in linked list, and this takes O(n).
      • Storing the sets in the union-find data structure means that we know the runtime if we do
      • 2m find operations and n - 1 union operations:
        • O(n) + O(m + n log n) tim
    • Total is:
      • O(m log n) + O(n) + O(m + n log n) = O(m log n)

./Chapter-4—GreedyAlgorithms—Part-3.3—Prim.pdf

• Prim Algorithm
• This one is a lot easier intuitively, because it’s more obvious that it’s correct.
• Start with a set of edge u \in ~A, and extend A with a minimum edge from an element of A to G = V \ A, and add the end of that edge to A.
• Repeat until A = G
• Algorithm:
• input: G = (V, E)
  • r = some arbitrary vertex
  • A = {r}
  • T = {}
  • while A != V do
    • find some edge of minimum weight such that u \in A, v \in V \ A
    • add to A, add to T.
  • return T
• How do we find the edge? by brute force it is O(|E|). This is obviously infeasible, as the runtime becomes O(|V|.|E|). However, we can store this in a better way.
• For each vertex in G, maintain minweight and closest
  • minweight: the minimum weight of any edge between that edge and a vertex of A.
  • closest: vertex x in A for which wt(x, y) = minweight(y)
• When we move something into A, then also update the minweights and closest of its neighbours in Q.
• Algorithm (this one is a lot more complicated than before, I’ll write it in if I get a chance later but for now go check the last page of this chapter):

./Chapter-5—Part-1—ShortestPathsAcyclic.pdf

• Dynamic programming! this is the stuff you know best.
• For some G = V, E, directed, acyclic, where each edge has wt(u, v) > 0
• Topolotical sorting:
  • Vertices are numbered such that for each edge (v_i, v_j), i < j.
• Let s = v_1, t = v_n.
• how to compute shortest path from s to t?
• Can we do better than dijkstras, using the topological sort? Yes, because we can compute the problem as we go.
• We know that the shortest path from s to t is equal to the minimum from all the nodes connected to t + the path from the start to any of these nodes
• If we compute the distances d(v_1) to d(v_n) beforehand (where d(v_x) is the distance from v_0 to it) [like the start node, s], then we can solve this in O(|V| + |E|) because you do a linear search at each node.

./Chapter-5—Part-2—MatrixChainMultiplication.pdf

• honestly these notes are pretty terse, so just read them if you have anything on optimal matrix multiplication

./Chapter-5—Part-3—LCS.pdf

• Longest common sequence
• Give two sequences, what is the longest common sequence?
• create a matrix such that c(i,j) is equal to LCS(x[..i], y[..j]), like what you did for that number partitioning problem in foobar.

./Chapter-5—Part-4—GeneralStructure.pdf

• This one doesn’t actually have any info, just that if you want to solve a problem using dynamic programming, create a recurrence relation on the problem and then cache your results and solve it bottom-up

./Chapter-5—Part-5—AllPairsShortestPath.pdf

• All pairs shortest paths
• Let G = V, E be a directed graph, where V = [1..n], and each edge is greater than 0.
• For all i and j, compute the weight of a shortest path in G from i to j, which I’ll call d(i,j) [it’s actually δ_G(i,j), but that’s cumbersome]
• Consider the shortest path from i to j, if the path has an interior vertex, it’s the path from one node to another, and this can be framed dynamically

./Chapter-5—Part-6—FinalRemark.pdf