# Algorithms Final Exam Study Guide

53 Questions | Total Attempts: 140  Settings  Exam 1-3, True/False questions & multiple choice questions.

Related Topics
• 1.
N^2 = o(n^2)
• A.

True

• B.

False

• 2.
N = O(n^2)
• A.

True

• B.

False

• 3.
The reflexive property hold for o (little-oh) and w.
• A.

True

• B.

False

• 4.
For two functions f(n) and g(n), if f(n) = w(g(n)), we know that f(n) is asymptotically larger than g(n).
• A.

True

• B.

False

• 5.
For two algorithms A and B, if O(A) = n^100 and O(B) = 10^n, then algorithm A is the better choice.
• A.

True

• B.

False

• 6.
The recurrence could be written equivalently as T(n) = T(n/2) + θ(n)
• A.

True

• B.

False

• 7.
There is a significant difference in the running time f(n) = n and the running time g(n) = lg n.
• A.

True

• B.

False

• 8.
F(n) = o(g(n)) means that f(n) is asymptotically smaller than g(n).
• A.

True

• B.

False

• 9.
All functions can be compared asymptotically.
• A.

True

• B.

False

• 10.
F(n) = Ω(g(n)) is like saying f(n) ≥ g(n)
• A.

True

• B.

False

• 11.
The min-heap property states that for every node i other than the root, A[PAERENT(i)] ≤ A[i].
• A.

True

• B.

False

• 12.
An array constructed with the values [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] is a max heap.
• A.

True

• B.

False

• 13.
For a node A at index i in a heap, the right child of A can be computed as 2*i.
• A.

True

• B.

False

• 14.
The master method can be used to solve all recurrence equations that have the form T(n) = aT(n/b) + f(n).
• A.

True

• B.

False

• 15.
Quicksort has a worst-case running time of θ(n^2).
• A.

True

• B.

False

• 16.
One good reason for using a hash table would be to reduce storage requirements.
• A.

True

• B.

False

• 17.
If we are using the division method for our hashing function, a table size of 64 would be a good choice.
• A.

True

• B.

False

• 18.
Printing every node in a binary tree takes θ(lg n) time.
• A.

True

• B.

False

• 19.
We do not have to make any key comparisons to find the min or max nodes of a binary search tree.
• A.

True

• B.

False

• 20.
Open addressing is usually preferred over chaining for solving hash function collisions.
• A.

True

• B.

False

• 21.
Red-black trees are an attempt to minimize the time of dynamic set operations by creating a balanced tree.
• A.

True

• B.

False

• 22.
In a red-black tree, a black node must have only red children.
• A.

True

• B.

False

• 23.
A problem that generates completely new subproblems at each step is a good candidate for a dynamic programming solution.
• A.

True

• B.

False

• 24.
Dynamic programming has the potential to transform exponential-time algorithms to polynomial time.
• A.

True

• B.

False

• 25.
A topological sort for a directed acyclic graph (DAG) can be created by performing a breadth-first search on the DAG.
• A.

True

• B.

False

• 26.
A minimum spanning tree for a graph with N vertices will have N-2 edges.
• A.

True

• B.

False

• 27.
A matrix is a good choice for representing a dense graph.
• A.

True

• B.

False

• 28.
Both matrix and lists can be used to represent weighted graphs.
• A.

True

• B.

False

• 29.
In Kruskal's algrorithm for building a minimum spanning tree, we proceed node by node, adding the connecting edges to the tree.
• A.

True

• B.

False

• 30.
Huffman encoding uses a dynamic programming strategy to compress data.
• A.

True

• B.

False

• 31.
If the following functions were sorted in increasing order of complexity (big-Oh), which one would be in the 3rd place? f1(n) = n^(0.999999)logn f2(n) = 10000000n f3(n) = 1.000001^n f4(n) = n^2
• A.

F1

• B.

F2

• C.

F3

• D.

F4

• 32.
Select the correct asymptotic notation for the function f(n) n^3 + 1000 - 100n^2 - 100n.
• A.

θ(n^3)

• B.

O(n^3)

• C.

O(n lg n)

• D.

Ω(2^n)

• 33.
What is the smallest value of n such that an algorithm whose running time is n^2 runs slower than an algorithm whose running time is 3n + 1?
• A.

2

• B.

25

• C.

4

• D.

15

• 34.
Given the algorithm for Bubblesort below, what is an accurate description of it's running time? BUBBLESORT(A)    for I = 1 to A.length -1       for j = A.length downto I + 1          If A[j] < A[j-1]             exchange A[j] with A[j-1]
• A.

T(n-1) + θ(n)

• B.

θ(n^2)

• C.

2T(n/2) + θ(1)

• D.

O(n)

• 35.
The most precise form of asymptotic notation is
• A.

O

• B.

Ω

• C.

O

• D.

θ

• 36.
In analyzing a divide-and-conquer algorithm, any subproblem that is not part of the original problem is incorporated into which part of the recurrence?
• A.

Recursion

• B.

Divide

• C.

Combine

• D.

Base case

• 37.
An algorithm that takes constant time is represented by
• A.

Ω(o)

• B.

W(g(n))

• C.

θ(n)

• D.

θ(1)

• 38.
Before running MAX-HEAPIFY on node i of a heap, what must be true?
• A.

The heap must be totally sorted in decreasing order.

• B.

The heap must be totally sorted in increasing order.

• C.

The parent of node i must be the root of a max heap.

• D.

Both children of node i must be the roots of max heaps.

• 39.
In which approach do we randomly select a hash function to avoid bad hashing behavior caused by a selected set of keys?
• A.

Double hashing

• B.

Division method

• C.

Multiplication method

• D.

Universal hashing

• 40.
The recurrence equation T(n) = T(n-1) + θ(n) represents the
• A.

Best case running time for Quicksort

• B.

Worst-case running time for Quicksort

• C.

Best-case running time for Heapsort

• D.

Worst-case running time for Heapsort

• 41.
Primary clustering is a problem in what hashing technique?
• A.

Universal hashing

• B.

Double hashing

• C.

• D.

Linear probing

• 42.
In hashing with chaining, the load factor α represents
• A.

The worst case search time

• B.

The space remaining in the hash table

• C.

The number of expected elements at any slot

• D.

The number of probes for insertion

• 43.
The worst-case search time for hashing with chaining is
• A.

θ(n)

• B.

O(1)

• C.

O(α)

• D.

θ(n^2)

• 44.
Which one of the following is a true for a red-black tree?
• A.

The root is red.

• B.

The root and leaves are black.

• C.

All simple paths from a node to the leaves contain the same number of red and black nodes.

• D.

A red node can have only one black child.

• 45.
What distinguishing feature should cause us to choose dynamic programming rather than a divide-and-conquer approach to a problem?
• A.

It is an optimization problem.

• B.

The problem can be solved recursively.

• C.

The problem does not have a brute force solution.

• D.

The subproblems for the solution overlap.

• 46.
Which of the following is true regarding Prim's algorithm for finding a minimum spanning tree?
• A.

The starting node must be connected to the edge with the least weight.

• B.

The algorithm grows only a single tree from start to finish.

• C.

"Marked" nodes indicate nodes that will not be in the final tree.

• D.

When selecting the next edge, we consider only edges that connect unmarked nodes to the other unmarked nodes.

• 47.
Which of the following is NOT a property of a minimum spanning tree?
• A.

It may have one or more cycles.

• B.

It has |V| -1 edges.

• C.

It is not necessarily unique.

• D.

The sum of weights of the edges is minimal.

• 48.
What is the name of the technique that stores computed values for future lookup, rather than recomputing them?
• A.

Overlapping subproblems

• B.

Topological sort

• C.

Memoization

• D.

Dynamic recursion

• 49.
Bottom-up dynamic programming works by
• A.

Doubling the recursive calls

• B.

Transforming recursive calls to a loop

• C.

Solving the same subproblem multiple times

• D.

Solving larger subproblems first, followed by smaller subproblems

• 50.
The basic restructuring operation for red-black trees is
• A.

Dynamic programming

• B.

Binary sort

• C.

Depth-first search

• D.

Rotation

• 51.
Which of the following is true for optimal binary search trees?
• A.

An optimal binary search tree will always be balanced.

• B.

Putting the highest-probability node at the root will always give us an optimal tree.

• C.

Optimal binary search trees are constructed through the principal of optimal substructure.

• D.

An optimal binary search tree for a set of nodes will always be unique.

• 52.
The general comparison used to determine if a graph is sparse or dense is between
• A.

|V| and |E^2|

• B.

In E and |V|

• C.

|E| and |V^2|

• D.

|V| and |E| + |V|

• 53.
Greedy algorithms make _______________optimal choices leading to _______________ optimal solutions.
• A.

Globally, locally

• B.

Top-down, bottom-up

• C.

Locally, globally

• D.

Bottom-up, top-down