Please copy and paste this embed script to where you want to embed

Feedback — Problem Set-5 You submitted this quiz on Thu 28 Feb 2013 10:59 AM CET. You got a score of 5.00 out of 5.00.

Question 1 Consider a directed graph with distinct and nonnegative edge lengths and a source vertex s. Fix a destination vertex t, and assume that the graph contains at least one s-t path. Which of the following statements are true? [Check all that apply.] Your Answer

Score

There is a shortest s-t path with no repeated vertices (i.e., a "simple" or "loopless" such path).

✔

0.25

The shortest (i.e., minimum-length) s-t path might have as many as n − 1 edges, where n is the number of vertices.

✔

0.25

The shortest s-t path must include the minimum-length edge of G.

✔

0.25

The shortest s-t path must exclude the maximum-length edge of G.

✔

0.25

Total

Explanation

1.00 / 1.00

Question 2 Consider a directed graph

G = (V , E)

and a source vertex s with the following properties:

edges that leave the source vertex 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. Does Dijkstra's shortest-path algorithm correctly compute shortest-path distances (from s) in this graph?

Your

Score

Explanation

1.00

One approach is to see that the proof of correctness from the videos still works. A slicker solution is to notice that adding a

Answer ✔ Always

positive constant M to all edges incident to s increases the length of every s-v path by exactly M , and thus preserves the shortest path. Total

1.00 / 1.00

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.) Your Answer Θ(n)

and

Θ(1)

Score ✔

Total

Explanation

1.00 1.00 / 1.00

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.) Your Answer Θ(1)

Total

and

Θ(n)

Score ✔

1.00 1.00 / 1.00

Explanation

Question 5 You are given a heap with

n

elements that supports Insert and Extract-Min. Which of the

following tasks can you achieve in

O(log n)

time?

Your Answer Find the fifth-smallest element stored in the heap. Total

Score ✔

1.00 1.00 / 1.00

Explanation

View more...
Question 1 Consider a directed graph with distinct and nonnegative edge lengths and a source vertex s. Fix a destination vertex t, and assume that the graph contains at least one s-t path. Which of the following statements are true? [Check all that apply.] Your Answer

Score

There is a shortest s-t path with no repeated vertices (i.e., a "simple" or "loopless" such path).

✔

0.25

The shortest (i.e., minimum-length) s-t path might have as many as n − 1 edges, where n is the number of vertices.

✔

0.25

The shortest s-t path must include the minimum-length edge of G.

✔

0.25

The shortest s-t path must exclude the maximum-length edge of G.

✔

0.25

Total

Explanation

1.00 / 1.00

Question 2 Consider a directed graph

G = (V , E)

and a source vertex s with the following properties:

edges that leave the source vertex 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. Does Dijkstra's shortest-path algorithm correctly compute shortest-path distances (from s) in this graph?

Your

Score

Explanation

1.00

One approach is to see that the proof of correctness from the videos still works. A slicker solution is to notice that adding a

Answer ✔ Always

positive constant M to all edges incident to s increases the length of every s-v path by exactly M , and thus preserves the shortest path. Total

1.00 / 1.00

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.) Your Answer Θ(n)

and

Θ(1)

Score ✔

Total

Explanation

1.00 1.00 / 1.00

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.) Your Answer Θ(1)

Total

and

Θ(n)

Score ✔

1.00 1.00 / 1.00

Explanation

Question 5 You are given a heap with

n

elements that supports Insert and Extract-Min. Which of the

following tasks can you achieve in

O(log n)

time?

Your Answer Find the fifth-smallest element stored in the heap. Total

Score ✔

1.00 1.00 / 1.00

Explanation

Thank you for interesting in our services. We are a non-profit group that run this website to share documents. We need your help to maintenance this website.

To keep our site running, we need your help to cover our server cost (about $400/m), a small donation will help us a lot.