Algorithms Design & Analysis Final Exam

false

(T/F) In the dynamic programming technique, we solve the subproblems top-down just like the dive and conquer technique.

true

(T/F) The dynamic programming technique will only solve a subproblem once, but it must solve every subproblem once

true

(T/F) The binomial coefficient, "n choose k", is given by the formula (depicted in the picture) need n >= k and need k >= 0

a) 64

Suppose we have three matrices A1 (2x3), A2 (3x4), and A3 (4x5). How many multiplications require for A1 x A2 x A3?
a) 64
b) 60
c) 40
d) 90

d) 90

Suppose we have three matrices A1 (2x3), A2 (3x4), and A3 (4x5). How many multiplications require for A1 x (A2 x A3)?
a) 64
b) 60
c) 40
d) 90

true

(T/F) Suppose we have three matrices A1 (2x3), A2 (3x4), and A3 (4x5). If we want to find A1 x A2 x A3, the possible split value of k is 1 and 2.

true

(T/F) The complexity of chained matrix multiplication is Θ(n^3).

true

The recursive formula to build table for 0-1 Knapsack Problem is:
If i > 0 and k > 0, P[i][k] = if wi

false

(T/F) In a graph G(V, E), en edge e in E with ends u and v can be denoted by uv. Two nodes u and v are said to be incident if uv is in E and e is said to be adjacent with u and v.

true

(T/F) In graph G(V, E), the degree of node v is the number of neighbors of v.

false

(T/F) If the subgraph of a graph G = (V, E) is a graph G' = (V', E') such that V' is a subset of V, and E' is a subset of E then a subgraph is called spanning if V' =/= V.

false

(T/F) In a complete graph of n nodes, the total # of edges = (n(n+1))/2 .

false

(T/F) A forest is a cyclic graph.

true

(T/F) In a directed graph G, the indegree of a node v is the number of edges directed into v, and the outdegree of v is the number of edges directed out of v.

true

(T/F) The size of the directed graph can be measured by either sum of indegrees or the sum of outdegrees.

true

(T/F) The Traveling Salesperson Problem is an NP-complete problem.

connected; acyclic, with non-negative weights, must have all nodes in it

The minimum spanning tree fulfill one or more than one of the following options: (select multiple)
- connected
- acyclic, with non-negative weights
- must have all nodes in it
- none of the above

true

(T/F) The Stable Marriage Problem is an example of the Greedy technique.

4, 5, 6; 4, 5, 6, 3; 3, 5, 6

In the following graph, which set of nodes are a clique? Choose all possible answers.
- 4, 5, 6
- 4, 5, 6, 3
- 1, 6, 4
- 3, 5, 6

false

(T/F) A set of marriages is called stable if two people who are not married both prefer each other to their spouses.

false

(T/F) Given a problem P, we say that an algorithm A is optimal (in the worst case) for P if it is the best-known algorithm for P.

true

(T/F) In the decision tree, comparisons from longest root to leaf path would be the worst-case scenario.

true

(T/F) For the general binary tree, 2^k >= k where d is the depth of the tree, and k is the number of leaves.

true

(T/F) Matrix multiplication (ordinary alg Θ(n^3)) is a polynomial type of problem.

false

(T/F) If there is any algorithm A has complexity Θ(2^n). This algorithm is a polynomial type problem.

false

(T/F) The theory of NP-Completeness deals with the optimization version of a problem.

false

(T/F) In the CNF Satisfiability problem, a clause is a sequence of literals separated by the logical AND operator.

a) the number of possible combinations of n objects taken k at a time

The binomial coefficient represents
a) the number of possible combinations of n objects taken k at a time
b) the number of possible combinations of k objects taken n at a time
c) the number of k objects that can go into n at a time
d) the number of n objects that can go into k at a time

false

(T/F) The divide and conquer algorithm for finding the binomial coefficient is more efficient than the dynamic programming approach.

"1 choose k" = 1; k = n; k = 0; "n choose k" = 1

The base cases for the recursive formula of the binomial coefficient are
- "1 choose k" = 1
- k = n
- n = 1
- k = 0
- "n choose k" = 1
- k >= 1

c) rows by rows, left to right

What order should we calculate the values for the binomial coefficient table?
a) column by column, left to right
b) rows by rows, right to left
c) rows by rows, left to right
d) none of the above

true

(T/F) The complexity for the dynamic programming algorithm of the binomial coefficient is Θ(n, k).

b) Θ(n, k)

The complexity for the dynamic programming algorithm of the binomial coefficient is
a) Θ(k)
b) Θ(n, k)
c) Θ(n + 1, k)
d) Θ(n)

true

(T/F) If matrix A is m * k and matrix B is k * n, then A * B requires m * k * n multiplications.

false

(T/F) Because matrix multiplication is associative, the parentheses of the multiplication cannot be changed.

true

(T/F) Base case for chained matrix multiplication:
Ai just one matrix in chain, i = j --> M[i][j] = 0 P[i][j] = no entry

a) min(M[i][k] + M[k+1][j] + di-1*dk*dj)

The general formula to solve the chained matrix multiplication problem is M[i][j] =
a) min(M[i][k] + M[k+1][j] + di-1*dk*dj)
b) min(M[k][i] + M[k+1][i] + dj-1*di*dk)
c) min(M[j][k] + M[i+1][j] + di-1*dj*dk)
d) none of the above

c) Θ(2^n)

How many recursive calls are required for M[1][n]? (if we used a recursive algorithm)
a) Θ(n)
b) Θ(n^2)
c) Θ(2^n)
d) none of the above

b) Θ(n^2)

How many possible M[i][j] sub problems are there? (# of table entries for dynamic programming)
a) Θ(n)
b) Θ(n^2)
c) Θ(2^n)
d) none of the above

false

(T/F) We need to calculate the base case first and work on the entries in a straight line when calculating the M[i][j]s for a chained matrix multiplication table.

true

(T/F) The # of split points for each entry in chained matrix multiplication using dynamic programming is O(n) (upper bound).

b) O(n^3)

The W(n) complexity for the dynamic programming approach of chained matrix multiplication is
a) O(n)
b) O(n^3)
c) O(n^2)
d) O(2^n)

true

(T/F) The 0-1 Knapsack problem is to determine a subset A of S which will fit in the knapsack and has maximum total profit.

false

(T/F) When solving the 0-1 Knapsack problem by brute force, the # of possibilities is n^2.

b) p[n][w] = consider all n items knapsack size w

What is it that we want to find when using the dynamic programming algorithm for the 0-1 Knapsack problem?
a) p[i][j] = consider all i items knapsack size j
b) p[n][w] = consider all n items knapsack size w
c) p[w][n] = consider all w items knapsack size n
d) none of the above

true

(T/F) The recursive formula used to build the 0-1 Knapsack table is
if wi

a) if the maximum is pi + p[i-1][k-wi]

The recursive formula for the 0-1 Knapsack problem is:
if wi

b) if the maximum is p[i-1][k]

The recursive formula for the 0-1 Knapsack problem is:
if wi

c) row by row, left to right

In what order should we calculate the entries of p for the 0-1 Knapsack problem table?
a) row by row, right to left
b) column by column, left to right
c) row by row, left to right
d) none of the above

a) (n+1)(w+1)

The worst case analysis W(n) of the 0-1 Knapsack algorithm is
a) (n+1)(w+1)
b) (n)(w+1)
c) (n+1)(w)
d) n*w

a) Θ(n, w)

The complexity of the 0-1 Knapsack algorithm is
a) Θ(n, w)
b) Θ(w)
c) Θ(n)
d) Θ(n^2, w)

true

(T/F) A graph G = (V, E) is defined as a finite set of nodes V which are interconnected by a finite set of edges E.

b) adjacent

Each edge e in E corresponds to two nodes in V, called the ends of e. An edge e in E with ends u and v can be denoted by uv.
Two nodes u and v are said to be __________ if uv is in E.
a) incident
b) adjacent
c) decadent
d) none of the above

a) incident

Each edge e in E corresponds to two nodes in V, called the ends of e. An edge e in E with ends u and v can be denoted by uv.
Edge e is said to be __________ with nodes u and v.
a) incident
b) adjacent
c) decadent
d) none of the above

c) neighbors

Each edge e in E corresponds to two nodes in V, called the ends of e. An edge e in E with ends u and v can be denoted by uv.
The ____________ of a node v are all the nodes in V which are adjacent to v in graph G.
a) connections
b) degree
c) neighbors
d) none of the above

b) degree

Each edge e in E corresponds to two nodes in V, called the ends of e. An edge e in E with ends u and v can be denoted by uv.
The ____________ of node v is the number of neighbors v has.
a) connections
b) degree
c) neighbors
d) none of the above

true

(T/F) In graph G, depicted below, node A has neighbors B, D, and C.

false

(T/F) In graph G, depicted below, C and B are adjacent.

true

(T/F) In graph G, depicted below, the degree of node A is 3 or d(A) = 3.

true

(T/F) In graph G, depicted below, the weight of AB is 1.

a) subgraph

A _____________ of a graph G = (V, E) is a graph G’ = (V’, E’) such that V’ is a subset of V, and E’ is a subset of E.
a) subgraph
b) subdrawing
c) topgraph
d) none of the above

a) there is an edge between every pair of nodes

A graph is complete if
a) there is an edge between every pair of nodes
b) every node has a degree of 2
c) there is an odd number of edges
d) none of the above

true

(T/F) The following graph is a complete graph.

b) n(n-1)/2

The number of edges in a complete graph on n nodes, kn, is kn =
a) n(n+1)/2
b) n(n-1)/2
c) (n-1)/2
d) (n+1)/2

true

(T/F) A path from node vo to node vk in a graph is a sequence of edges vo, v1, v1 v2 , ... , vk-1, vk , where vo ,v1 , ... , vk are all distinct.

a) cycle

A _________ in a graph is like a path except node vo = node vk.
a) cycle
b) forest
c) roundabout
d) none of the above

false

(T/F) DAB is a path with a length of 3.

true

(T/F) CAD is a cycle with a length of 3.

b) connected

A graph is _________ if there is a path between every pair of nodes.
a) conjunct
b) connected
d) conjoined
d) none of the above

true

(T/F) A graph is called acyclic if it contains no cycle.

b) forest; tree

A ________ is an acyclic graph and a _________ is a connected forest.
a) tree; forest
b) forest; tree
c) jungle; tree
d) forest; camp

true

(T/F) If G is a tree and G has n nodes, then G has n-1 edges.

false

(T/F) If G is a tree and G has n nodes, then G has n edges.

c) directed graph; digraph

A __________________, or __________ is a graph in which all of the edges have been given a direction.
a) undirected graph; unigraph
b) digested graph; digraph
c) directed graph; digraph
d) none of the above

c) indegree; outdegree

The __________ of a node v is the number of edges directed into v and the ___________ of v is the number of edges directed out of v.
a) half-degree; full-degree
b) outdegree; indegree
c) indegree; outdegree
d) full-degree; half-degree

b) 2

In the graph depicted, the indegree of A is
a) 1
b) 2
c) 3
d) 4

b) 2

In the graph depicted, the outdegree of D is
a) 1
b) 2
c) 3
d) 4

true

(T/F) sum of indegrees = sum of outdegrees = |E| = size

edge list; adjacency matrix; adjacency list

Different ways to represent graphs and diagraphs include (select multiple)
- edge list
- incidence list
- adjacency matrix
- adjacency list
- incident matrix

a) edge list

What representation of a graph is being used in the picture?
a) edge list
b) adjacency matrix
c) adjacency list
d) none of the above

b) adjacency matrix

What representation of a graph is being used in the picture?
a) edge list
b) adjacency matrix
c) adjacency list
d) none of the above

c) adjacency list

What representation of a graph is being used in the picture?
a) edge list
b) adjacency matrix
c) adjacency list
d) none of the above

false

(T/F) The greedy technique always results in a correct algorithm for a problem.

b) Θ(n^2)

The complexity for Prim's algorithm is
a) Θ(n)
b) Θ(n^2)
c) Θ(n+1)
d) none of the above

true

(T/F) The greedy technique in Prim's algorithm doesn't work for directed graphs.

a) Θ(n^2)

What is the complexity of the Stable Marriage problem?
a) Θ(n^2)
b) Θ(n^3)
c) Θ(n)
d) none of the above

d) both a and b

Women Men
A X
B Y
A couple in the Stable Marriage problem is unstable if
a) woman A prefers man X to man Y
b) man X prefers woman A to woman B
c) woman B prefers man Y
d) both a and b

false

(T/F) The Stable Marriage algorithm is "optimal" for women but not for the men, therefore the algorithm isn't biased.

a) Θ(n^2)

The complexity of using the greedy technique with scheduling deadlines is
a) Θ(n^2)
b) Θ(n^3)
c) Θ(n)
d) none of the above

c) we establish a lower bound k on the # of operations needed to solve a problem P (in worst case)

How do we show an algorithm is optimal for a problem?
a) we establish a lower bound k on the # of operations needed to solve a problem P (in best case)
b) we establish a upper bound k on the # of operations needed to solve a problem P (in worst case)
c) we establish a lower bound k on the # of operations needed to solve a problem P (in worst case)
d) none of the above

merge sort, quick sort, exchange sort, bubble sort, shell sort

Examples of the fastest worst case algorithms Θ(nlgn) include (select multiple)
- bucket sort
- merge sort
- quick sort
- radix sort
- exchange sort
- bubble sort
- shell sort

b) decision tree

In a ________________ the non-leaf nodes represent a comparison of two of the keys, i.e., a < b
a) choice tree
b) decision tree
c) sort tree
d) none of the above

true

(T/F) The depth of a tree is the number of edges in a longest root to leaf path.

true

(T/F) Concerning general binary trees, 2^d >= k where d is the depth of the tree and k is the number of leaves.

true

(T/F) Concerning general binary trees, d = ⌈lg k⌉ where d is the depth of the tree and k is the number of leaves.

true

(T/F) An algorithm is said to be polynomial (or is said to run in polynomial time) if it has complexity(worst case) < Θ(p(n)), where p(n) is some polynomial in the size of the input n.

Θ(n^2), Θ(nlgn)

Select the W(n) that are considered polynomial time:
- Θ(n^2)
- Θ(2^n)
- Θ(nlgn)
- Θ(n!)

a) tractable

A problem for which we know a polynomial algorithm is called _____________.
a) tractable
b) malleable
c) tactile
d) tractate

b) Graph-Coloring Optimization

The _______________ problem is to determine the minimum number of colors needed to color a graph so that no two adjacent vertices are colored the same color.
a) Graph-Drawing Optimization
b) Graph-Coloring Optimization
c) Graph-Rainbow Optimization
d) Color-Adjacency Optimization

c) logical (Boolean) variable

A ________________ is a variable that can have one of two values: true or false. If x is a logical variable, x̄ is the negation of x.
a) natural (Boolean) variable
b) rational (Boolean) variable
c) logical (Boolean) variable
d) none of the above