Coursera

Warning: You have already made the maximum number of submissions. Additional submissions will not count for credit. You are welcome to try it as a learning exercise.

In accordance with the Coursera Honor Code, I (Anonymous Student) certify that the answers here are my own work.

Question 1

Consider a directed graph with distinct and nonnegative edge lengths and a source vertex

s $s$ . Fix a destination vertex

t $t$ , and assume that the graph contains at least one

s $s$ -

t $t$ path. Which of the following statements are true? [Check all that apply.]

There is a shortest

s $s$ -

t $t$ path with no repeated vertices (i.e., a "simple" or "loopless" such path).

The shortest (i.e., minimum-length)

s $s$ -

t $t$ path might have as many as

n−1 $n-1$ edges, where

n $n$ is the number of vertices.

The shortest

s $s$ -

t $t$ path must include the minimum-length edge of

G $G$ .

The shortest

s $s$ -

t $t$ path must exclude the maximum-length edge of

G $G$ .

Question 2

Consider a directed graph

G=(V,E) $G = (V,E)$ and a source vertex

s $s$ with the following properties: edges that leave the source vertex

s $s$ have arbitrary (possibly negative) lengths; all other edge lengths are nonnegative; and there are no edges from any other vertex to the source

s $s$ . Does Dijkstra's shortest-path algorithm correctly compute shortest-path distances (from

s $s$ ) in this graph?

Never

Only if we add the assumption that

G $G$ contains no directed cycles with negative total weight.

Maybe, maybe not (depends on the graph)

Always

Question 3

Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

Θ(n) $\Theta(n)$ and

Θ(n) $\Theta(n)$

Θ(n) $\Theta(n)$ and

Θ(1) $\Theta(1)$

Θ(logn) $\Theta(\log n)$ and

Θ(1) $\Theta(1)$

Θ(1) $\Theta(1)$ and

Θ(n) $\Theta(n)$

Question 4

Suppose you implement the functionality of a priority queue using an unsorted array. What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

Θ(n) $\Theta(n)$ and

Θ(1) $\Theta(1)$

Θ(n) $\Theta(n)$ and

Θ(n) $\Theta(n)$

Θ(1) $\Theta(1)$ and

Θ(n) $\Theta(n)$

Θ(1) $\Theta(1)$ and

Θ(logn) $\Theta(\log n)$

Question 5

You are given a heap with

n $n$ elements that supports Insert and Extract-Min. Which of the following tasks can you achieve in

O(logn) $O(\log n)$ time?

Find the largest element stored in the heap.

Find the median of the elements stored in the heap.

None of these.

Find the fifth-smallest element stored in the heap.

In accordance with the Coursera Honor Code, I (Anonymous Student) certify that the answers here are my own work.

You cannot submit your work until you agree to the Honor Code. Thanks!

Algorithms: Design and Analysis, Part 1

Top Navigation Bar

Algorithms: Design and Analysis, Part 1
by Tim Roughgarden

Side Navigation Bar

Problem Set-5 Help Center

Question 1

Question 2

Question 3

Question 4

Question 5

Algorithms: Design and Analysis, Part 1

Algorithms: Design and Analysis, Part 1by Tim Roughgarden

Problem Set-5 Help Center

Question 1

Question 2

Question 3

Question 4

Question 5

Confirm Navigation

Algorithms: Design and Analysis, Part 1
by Tim Roughgarden