1. search a sorted vector of 255 elements using the binary search algorithm? (a)

Question

1. search a sorted vector of 255 elements using the binary search algorithm? (a) 10 (b) 8 (c) T (d) 9 2. A list implementation of a graph might use an array of linked lists, each list containing all thea vertex. (a)paths containing (b) edges adjacent to (b) vertices adjacent to (c) trees containing 3. The adjacency list of the undirected graph is on the form: 4. (T/F) The linear search has asymptotic running time of order n 5. How many ways do you have to parenthesize the matrices multiplication AiA2HaAA? Question 2 5 Marks) Apply the BFS algorithm on the following undirected graph with source B estion 3 5 Marks)

Explanation / Answer

1.In binary search the number of comparisons are log(n) to the base 2 where n is the
number of elements.In this case n = 255 so log(255) to the base 2 is close to 8.
So in this case answer is 8.

2. The answer is b) vertices adjacent to

   This is the way adjacency list of a graph is created, where we have array of vertices
   and each element is a list containg the vertice connected to that vertex.

3. Adjacency list will be as follws:

   Each vertex is stored in an array and every element of the array is pointint to a    linked list starting with a vertex and the list containing the vertices adjacent to    it.

   1->2->5
   2->1->3->4->5
   3->2->4
   4->3->2->5
   5->1->2->4

4 It is of O(n). In linear search we comapre each and every element of the set with the
number we are searching. If the set contains n elements we will have n comparisons so   its complexity is of O(n).

5. We need to do parenthesize as follows:

   We will multiply two matrices at a time.

   1.(A1*A2)*(A3*A4)
   2. ((A1 * (A2*A3)) * A4)

2 Applying BFS to the graph. In BFS we need to traverse all the child of the node and then move to the next level (i.e repeat the step for each child node at the same level)

                                 A
                               / |                              
                             B   |   C
                           / |  
                         D      E

So B as starting the BFS order will be , first we have to cover all the children of B.So
   we get B D E A

   Then we go to D (it is already visited and no children)
   Then we go to E (it is already visited and it has A as child, but that is visited)
   Then we go to A (it is already visited and it has C as child)

   So the total order will be B D E A C
      

      

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.