True/False Midterm

To delete the ith node in a binary min heap, you can exchange the last node with the ith

node, then check the nodes below the ith node to see if the ith node should move down

the heap to “re-heapify” it.

If G is a directed acyclic graph, then G must have a node with no incoming edges.

Inserting into a binomial heap of n elements has O(1) amortized cost.

In an undirected, connected, weighted graph with at least three vertices and unique edge weights, the

heaviest edge in the graph cannot be in any minimum spanning tree.

If f=O(g)and g=O(h), then f=O(h).

The array [100, 93, 83, 90, 79, 84, 81] corresponds to a binary max-heap.

Given a graph, suppose we have calculated the shortest path from a source to all other vertices. If we

modify the graph such that weights of all edges are doubled, then the shortest path remains the same,

only the total weight of the path changes.

Let d(u, v) denote the minimum distance from node u to node v in a weighted graph G. If d(s, u) + d(u,

t) = d(s, t), then u is on at least one shortest path from

s to t. (All edge weights in G are positive.)

Height of a binary heap is O(n)

The divide and conquer algorithm to solve the closest pair of points in 2D runs in

O(n log n). But if the two lists of points, one sorted by X-coordinate and the other sorted by Y-

coordinate are given to us as input, the rest of the algorithm (skipping the sorting steps) runs in O(n)

time.

The solution of the recurrence T(n) = 18T(n/3) + O(n3) is T(n) = O(n3).

Any depth-first search in a directed graph will produce the same number of tree edges in the DFS tree.

For any connected graph with n vertices and m edges we can say that m+n = O(m).

In a binomial heap, for a given set of input values, the number of binomial trees in the heap will

depend on the order of insertions

The amortized cost of an operation can be as high as the worst-case cost of an operation in a data

structure.

A recurrence equation of the type T(n) = a * T(n/b) + f(n) where a * f(n/b) = 2 * f(n) cannot be solved

using the Master Theorem.

The shortest path between two nodes in a weighted directed graph can be found using BFS if all edges except for those leaving the starting point have the same weight.

Kruskal's algorithm for minimum weight spanning trees is an example of a greedy algorithm.

If all the edge weights of a given graph are the same, then every spanning tree of that

graph is minimum.

An in-order traversal of a min-heap outputs the values in sorted order.

If all edges in a connected undirected graph have distinct positive weights, the shortest path between any two vertices is unique.

If a connected undirected graph G(V, E) has n = |V| vertices and n +10 edges, we can find the minimum spanning tree of G in O(n) runtime.

An amortized cost of insertion into a binomial heap is constant.

Gale-Shapley algorithm is a greedy algorithm.

For all positive functions f(n), g(n) and h(n), if f(n) = O(g(n)) and f(n) = Ω(h(n)), then g(n) + h(n) = Ω(f(n)).

Any function which is Ω(log log n) is also Ω(log n).

The depths of any two leaves in a binomial heap differ by at most 1.

For some graphs BFS and DFS trees can be the same.

The number of cycles in a bipartite graph may be odd.

Stable matching algorithm presented in class is based on the greedy technique.

To delete the ith node in a binary min heap, you can exchange the last node with the ith

node, then check the nodes below the ith node to see if the ith node should move down

the heap to “re-heapify” it.

Kruskal’s algorithm can fail in the presence of negative cost edges.

Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first by w, and w is ranked first by m. Then (m, w) must appear in every stable matching.

If a connected undirected graph G has the same weights for every edge, then a minimum spanning tree can be found in linear time.

Given n numbers, one could construct a binary heap using the n numbers, then using

the binary heap produce a sorted list of the numbers in O(n) time.

In a Fibonacci heap, the insert operation has an amortized cost of O(1) time, but the worst case cost is higher.

In a connected undirected graph, and using the same starting point, the depth of any

DFS tree is at least as much as the depth of any BFS tree.

Let T be a complete binary tree with n nodes. Finding a path from the root of T to a

given vertex v ∈ T using breadth-first search takes O(log n) time.

Amortized cost of operations in a Fibonacci heap is at least as good as the worst case cost of those same operations in a binomial heap.

Master’s Theorem can be used to calculate the running time of any recursive function.

Dijkstra’s shortest path algorithm can be used to find shortest path in graphs with any

edge weights.

Stable Matching: Suppose Jack prefers Rose to others, and Rose prefers Jack to others. The pair (Jack, Rose) exists in every stable matching.

A DFS tree is a spanning tree.

A binary max-heap can be built using an unsorted list of elements in O(n) time

Let T be a complete binary tree with n nodes. Finding a path from the root of T to a

given vertex v ∈ T using breadth-first search takes O(logn).

Dijkstra’s algorithm works correctly on a directed acyclic graph even when there are

negative-weight edges.

If the edge e is not part of any MST of G, then it must be the maximum weight edge on some cycle in G.

If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n).

The following array is a max heap: [10; 3; 5; 1; 4; 2].

There are at least 2 distinct solutions to the stable matching problem: one that is preferred by men and one that is preferred by women.

In a binary max-heap with n elements, the time complexity of finding the second

largest element is O(1).

Given a binary max-heap with n elements, the time complexity of finding the smallest

element is O(lg n).

If a weighted undirected graph has two MSTs, then its vertex set can be partitioned

into two, such that the minimum weight edge crossing the partition is not unique.

Height of any complete binary tree with n nodes is O(n)

Given a binary max heap with k levels (with root at level 1), the smallest element of the heap

will be on level k.

Given a binary min heap of size n, we can construct a sorted list of the n elements in O(n)

time.

Given a directed graph G with n vertices, any BFS tree corresponding to graph G will have

n-1 edges

In the Gale-Shapley algorithm we will always have to do the same number of iterations

whether men are proposing, or women are proposing

Amortized cost of an operation in a data structure is always lower than its worst-case cost

In a binary max-heap, the kth largest element cannot appear anywhere below the kth level.

(root is at level 1)

The depths of any two leaves in a binomial heap differ by at most 1.

Any function which is Ω(log log n) is also Ω(log n).

An in-order traversal of a min-heap outputs the values in sorted order.

To delete the ith node in a binary min heap, you can exchange the last node with the ith

node, then check the nodes below the ith node to see if the ith node should move down

the heap to “re-heapify” it.

If f(n) is O(g(n)), if n is large enough, we always have f(n)<=g(n)