Join StudySoup for FREE

Get Full Access to
UVM - Cs 224 - Study Guide

Description

Reviews

CS224 Midterm Exam Study Guide

The emphasis of the exam is on the concept and intuition and the review of topics studied in class. Review lecture slides and reinforce the understanding from textbook. Textbook sections relevant to each topic are shown in parentheses at the end of the topic.

Chapter 2. Basics of Algorithm Analysis

o Justify the argument that an algorithm is efficient if its running time complexity can be expressed as a polynomial function of the problem size. (2.1)

o A poly-time algorithm holds the desirable scaling property. There exists constants c > 0 and d > 0 such that on every input of size N, its running time is bounded by cNd steps. Don't forget about the age old question of Aggregate expenditure represents what?

o Justification: Using a poly-time algorithm works in practice because the algorithms people develop almost always have small constants (c) and small exponents (d).

Don't forget about the age old question of What is oxidative organisms?

o A problem is “computationally tractable” if there is a worst-case poly-time algorithm that solves the problem

o Clarify the distinction among the running time complexities expressed in big-Oh (O), bigomega (Ω), and theta (Ө) notations. (2.2) We also discuss several other topics like How to understand the concept of socialization?

o Big-Oh(O) – Upper bound; running time can reach no greater than O.

o Bigomega (Ω) – Lower bound of running time.

o Theta (Ө) – Tight-bound; running time is no greater and no less than Ө. o Formal definition and proof of running time complexities. (2.2)

Formal Definitions

o Big-Oh: T(n) = O(f(n)) if there exist constants c > 0 and n0 ≥ 0 such that for all n ≥ n0 we have T(n) ≤ c · f(n).

o Bigomega: T(n) = Ω(f(n)) if there exist constants c > 0 and n0 ≥ 0 such that for all n ≥ n0 we have T(n) ≥ c · f(n).

o Theta: T(n) = Θ(f(n)) if T(n) is both O(f(n)) and Ω(f(n)).

Proofs

(2.5) Let k be a fixed constant, and let f1, f2, . . . , fk and h be functions such that fi = O(h) for all i. Then f1 + f2 + . . . + fk = O(h). Don't forget about the age old question of What are the 6 drivers of credibility?

Let f be a polynomial of degree d, in which the coefficient ad is positive. Then f = O(nd).

Proof. We write f = a0 + a1 n + a2n2 + . . . + adnd, where ad>0. The upper bound is a direct application of (2.5). First, notice that coefficients aj for j < d may be negative, but in any case we have ajnj ≤ |aj|nd for all n ≥ 1. Thus each term in the polynomial is O(nd).

Since f is a sum of a constant number of functions, each of which is O(nd), it follows from (2.5) that f is O(nd).

o Analyze an algorithm to derive its asymptotic running time complexity. (2.2)

Example: Deriving asymptotic run time of Breadth First Search algorithm Total = O(n) + O(m) = O(m + n) If you want to learn more check out What is extended problem-solving?

Chapter 3. Graphs We also discuss several other topics like How do you find the marginal cost?

o Graph representation: adjacency list, adjacency matrix, and their comparison.

Adjacency List

o Checking if (u, v) is an edge takes O(deg(u)), where deg(u) is the number of neighbors of u

o Identifying all edges takes Θ(m + n)

Adjacency Matrix

o Checking if (u, v) is an edge takes Θ(1)

o Identifying all edges takes Θ(n2)

o Graph connectivity: completely connected graph, minimally connected graph. The relationship between the number of edges and the number of vertices in each of the two.

Minimally Connected Graph: A graph with the smallest amount of edges needed to create a path to every node; the removal of a single edge would leave a disconnected graph

Number of Edges: n – 1, where n is the number of nodes/vertices

Completely Connected Graph: A graph in which each pair of vertices is directly connected by an edge.

Number of Edges:

o For undirected: n(n-1)/2, where n is the number of nodes

o For directed: n(n-1), where n is the number of nodes

o Analyze the running time complexity of breadth-first search algorithm when a graph is represented using an adjacency list or an adjacency matrix. (3.2)

BFS with adjacency list: O(m + n)

o It takes O(n) for the initialization (the first line).

o There are at most n lists L[i] to set up, so initializing an empty list L[i+1] takes total O(n) time during the execution of the While loop.

o The part “If Discovered[v]…” takes O(1).

o Each node u is visited exactly once during the execution of the While loop, and for each node, there are deg(u) incident nodes.

o So, the total run-time of the While loop is proportional to the summation of deg(u) over all nodes, which equals Σu∈V deg(u) = O(2m) = O(m). o So, total O(m+n).

BFS with adjacency matrix: O(n2)

o It takes O(n) for the initialization (the first line).

o There are at most n lists L[i] to set up, so initializing an empty list L[i+1] takes total O(n) time during the execution of the While loop.

o The part “If Discovered[v]…” takes O(1).

o Each node u is visited exactly once during the execution of the While loop, and for each node, there are n nodes to check.

o So, the total run-time of the While loop is proportional to n2

o So, total O(n2) + O(n) = O(n2).

o Give an argument for or against building a recursive algorithm for BFS. (3.2)

Because BFS most often uses a queue (FIFO) data structure to keep track of visited nodes, and it involves observing one layer of nodes at a time, a recursive algorithm would not be ideal. A recursive algorithm would make more sense for DFS, which has a recursive nature of searching as deep as possible before returning back.

o Give the key distinction between the queue structure used for BFS and DFS. (3.2)

BFS uses a FIFO queue structure, which pushes elements out of the queue in the order they were added, while DFS uses a LIFO queue (aka stack) that pushes most recently added elements out first.

o Outline the bipartite testing algorithm based on the BFS algorithm and show its correctness (3.4)

Lines in bold have been added to the BFS algorithm to test for bipartiteness. Algorithm:

// Set Discovered[s] = true and Discovered[v] = false for all other v

// Set Color[s] = red

// Initialize L[0] to consist of the single element s

// Set the layer counter i = 0

// Set the current BFS tree T = ∅

// While L[i] is not empty

// Initialize an empty list L[i +1]

// For each node u in L[i]

// For each edge (u,v) incident to u

// If Discovered[v] = false, then

// Set Discovered[v] = true

// Add edge (u,v) to tree T

// Add v to list L[i +1]

// If i+1 is odd, set Color[v] = blue

// Else, set Color[v] = red

// End If

// End For

// End For

// Increment layer counter i by one

// End While

// Scan all edges and determine whether there is any edge that has the same color on both end-nodes

Correctness:

By assigning blue to odd numbered layers and red to even numbered layers, we are essentially saying, only the nodes in those layers can have those respective colors. Thus, if we find that a particular node has been assigned the same color as a node in a preceding or following layer, this will indicate that these nodes belong to an odd numbered cycle, which means we have identified our graph is bipartite.

o Outline the strong-connectivity testing algorithm using BFS and show the running time complexity. (3.5)

Algorithm

// Pick any node s.

// Run BFS from s in G.

// Build Grev (reverse the direction of every edge in G).

// Run BFS from s in Grev (set Discovered[v] back to false each time node v is discovered) // Return true iff every node is reachable from s in both BFS in G and BFS in Grev (if Discovered[] is empty)

Running Time Complexity: O(m + n)

Explanation:

o Each BFS step takes O(m + n).

o Building Grev can be done in O(m + n).

o Traverse all edges in adjacency list exactly once to construct new

adjacency list with traversed edges. (Mark end of each list so adding new node takes constant time).

o Scanning Discovered array to find if any vertices are left over takes O(n). o Total time: O(3m + 3n + n) = O(m + n).

o Outline the topological sorting algorithm and show the running time complexity. (3.6) Algorithm

// Maintain count[] for remaining number of incoming edges to node w // Maintain set S of remaining nodes with no incoming edge

// Initialize count[w] for each node w and initialize S

// Repeat until S is empty {

// Remove one node v from S.

// Decrement count[w] for every w with an incoming edge from v,

// and add w to S if count[w] has become 0.

}

Running Time Complexity: O(m + n) (with G in adjacency list)

o Initializing count[w] for every w requires scanning through adjacency list which takes O(m + n).

o Removing each node exactly once is executed exactly n times (for n

nodes) so takes O(n).

o Decrementing count[w] for every w with incoming edge from v takes the number of outgoing edges from v for each iteration which totals to O(m), since there are m edges in total.

o Total: O(2m + 2n) = O(m + n).

Chapter 4. Greedy Algorithms

o State why a greedy algorithm does not always guarantee an optimal solution.

Greedy algorithms are not fit for every situation but work well when a greedy choice can be made at every stage of a problem and when a solution for part of the problem is also a solution to the entire problem. Sometimes, there are algorithms that prove to be more optimal than a greedy strategy, but it all depends on the given problem.

o For each of the following problems, state the optimal greedy strategy and justify its optimality, and find an optimal solution given a problem instance; given a greedy strategy, prove or disprove if it is an optimal strategy:

o Interval scheduling (4.1)

Earliest finish time

o Interval partitioning (4.1)

Earliest start time

o Minimum lateness (4.2)

Earliest deadline

o State the greedy strategy of the Dijkstra’s shortest path algorithm and justify why it ensures an optimal solution. (4.5)

Start at the source node s and follow the path to t that chooses each edge, which minimizes the total distance from s to t.

o Show the shortest paths as they are constructed during the execution of the Dijkstra’s algorithm. (4.5)

Example:

o State the similarity and dissimilarity between the Dijkstra’s shortest path algorithm and the Prim’s minimum spanning tree algorithm. (4.5)

While both algorithms are concerned with finding a shortest path, Dijkstra’s shortest path algorithm is used to find the shortest path between two nodes, s and t, but is not necessarily concerned with hitting every node if it does not have to in order to reach t, while Prim’s is a MST algorithm, that finds the shortest path which touches every node in the graph. In addition, Dijkstra’s evaluates the total weighted distance from s to a node as it considers which node to add to the cloud next, while Prim’s is only concerned with the individual weights of each edge (u,v) leading from a node u, and it considers whether or not adding node v will create a cycle.

o For each of the Prim’s and Kruskal’s minimum spanning tree algorithms, state the greedy strategy and justify its optimality.

Kruskal’s

Greedy Strategy:

Starting with the smallest weighted edge in a graph, continually add the next smallest weighted edge to T if it will not create a cycle.

Optimality: For each edge considered:

Case 1: If adding e to T creates a cycle, then e is discarded. This is justified by the cycle property because e has the largest weight among all edges in the cycle.

Case 2: Otherwise, add e = (u, v) to T. This is justified by the cut

property, where the cut S is the set of nodes in u's connected

component, because, since adding e to T does not create a cycle, e

has the smallest weight among all edges remaining to be added from

the cutset of S.

Prim’s

Greedy Strategy:

Start at any node s and add to cut S, continually consider the smallest weighted edge in the cutset of S, while adding the newly explored node to S.

Optimality: Justified by the cut property: Let S be any cut in a graph, and let e be the minimum weighted edge in the cutset D of S. Then the MST contains e.

o Describe briefly how the Kruskal’s minimum spanning tree algorithm can be implemented using the union-find data structure. (4.5)

You can implement Kruskal’s algorithm using a forest implementation of disjoint sets. Initialize all nodes in the graph as disjoint singleton sets. Each time a new edge (u,v) is considered, check to see if u and v are equivalent (have the same root node) by calling find(u) and find(v). If they return different values, this means adding this edge would not create a cycle, so union them. Now they are apart of the same tree and next time find is called on either one, the same root node will be returned. Continue this process until all

nodes belong to the same set; then you know you’ve reached every node and the MST is complete.

o Show the minimum spanning tree as it is constructed during the execution of the Prim’s or the Kruskal’s algorithm. (4.5)

Examples: Numbers in red indicate order the edge was added to MST

1

3 1

2

6

5 4

7

1

3

1

7

1 2 4

5

1

6

Chapter 5. Divide and Conquer. (Do not use Master theorem when solving a recurrence relation.)

o Describe the divide-and-conquer approach in algorithm design.

o Break up problem into several parts

o Solve each part recursively

o Combine solutions as parts in overall solution

o State the approach to deriving the running time complexity of a divide-and-conquer algorithm.

Building and solving a recurrence relation.

o Outline the mergesort algorithm using divide-and-conquer and derive the running time complexity. (5.1)

Algorithm

// Divide array into two halves

// Recursively sort each half

// Merge two sorted halves to make one sorted whole

Running Time Complexity: O(nLogn)

Runtime T(n)

Divide O(1)

Sort 2T(n/2)

Merge O(n)

(Using pre-sorted arrays and temporary array)

T(n) ≤ T (⎣n/2⎦)+ T (⎡n/2⎤)+ O(n) => T(n) = O(n log n)

o Outline the counting inversion algorithm using divide-and-conquer and derive the running time complexity. (5.3)

Algorithm

// Divide array into two halves

// Recursively count inversion in each half

// Count inversions between the two halves, while merging into whole and return sum of all three counts (Make sure two halves are pre-sorted, and use auxiliary array)

Running Time Complexity: O(nLogn)

Runtime T(n)

Divide O(1)

Sort 2T(n/2)

Merge O(n)

(Using pre-sorted arrays and auxiliary array)

T(n) ≤ T (⎣n/2⎦)+ T (⎡n/2⎤)+ O(n) => T(n) = O(n log n)

o Outline the Karatsuba’s integer multiplication algorithm using divide-and-conquer and derive the running time complexity. (5.5)

Multiplying 2 n-digit integers Algorithm

// Add two ½ n digit integers

// Multiple three ½ n digit integers

// Add, subtract, and shift ½ n digit integers to obtain result

Running Time Complexity: O(n1.585)

Recursive calls Add, subtract, shift