Coursera Answers

Graph Search, Shortest Paths, and Data Structures Week 3 | Problem Set #3 Quiz Answer

Graph Search, Shortest Paths, and Data Structures Week 3  Problem Set #3 Quiz Answer

Graph Search, Shortest Paths, and Data Structures Week 3 | Problem Set #3 Quiz Answer


In this article i am gone to share Coursera Course Graph Search, Shortest Paths, and Data Structures Week 3 | Problem Set #3 Quiz Answer with you..

Problem Set #3

Question 1)

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) and Ө(n)
  • Ө(n) and Ө(1)
  • Ө(log n) and Ө(1)
  • Ө(1) and Ө(n)

Question 2)

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

  • Ө(1) and Ө(log n)
  • Ө(n) and Ө(n)
  • Ө(n) and Ө(1)
  • Ө(1) and Ө(n)

Question 3)

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? 

  • Find the fifth-smallest element stored in the heap. 
  • Find the largest element stored in the heap. 
  • Find the median of the elements stored in the heap. 
  • None of these.

Question 4)

You are given a binary tree (via a pointer to its root) with n nodes. As in lecture, let size(x) denote the number of nodes in the subtree rooted at the node x. How much time is necessary and sufficient to compute size(x) for every node x of the tree?

  • Ө(n)
  • Ө(n2)
  • Ө(height) 
  • Ө(n log n)

Question 5)

Suppose we relax the third invariant of red-black trees to the property that there are no three reds in a row. That is, if a node and its parent are both red, then both of its children must be black. Call these relaxed red-black trees. Which of the following statements is not true? 

  • Every red-black tree is also a relaxed red-black tree. 
  • There is a relaxed red-black tree that is not also a red-black tree. 
  • The height of every relaxed red-black tree with n nodes is O(log n). 
  • Every binary search tree can be turned into a relaxed red-black tree (via some coloring of the nodes as black or red).