(for example, 1 and 3 are adjacent in G 2 , because the distance between them in
ID: 3571386 • Letter: #
Question
(for example, 1 and 3 are adjacent in G2, because the distance between them in G is 2. 1 and 4 are not adjacent in G2, because the distance between them in G is 3)
Design an efficient algorithm to calculate an adjacency matrix of G2. What is its running time?
4. You are given a set of ABC cubes for kids (like the one shown below) and a word. On each side of each cube a letter is written.
You need to find out, is it possible to form a given word by the cubes?
For example, suppose that you have 5 cubes:
B1: M X T U A S
B2: O Q A T G E
B3: R E W M N A
B4: M B D F A C
B5: I J K G D E
(here for each cube the list of letters written on its sides is given)
You can write the word “MAMA” using cubes B3, B2, B4, B1:
please help, these questions will help me prep for final exam. Thank you
1. Consider two algorithms with running times 8n2 and 64nlog(n), respectively. Starting from what value of n second algorithm becomes better than the first algorithm? 2. You are given a binary search tree. Howto find its third largest element? 3. You are given an unweighted graph G, which is represented by an adjacency matrix. Square of G is a graph G2 with the same set of vertices as G, and two vertices being adjacent if and only if the distance between them in G is 1 or 2. ExampleExplanation / Answer
2) Here we are talking about finding the third largest element , we can generalise this to finding nth largest element(in this way you can find largest value at index of your choice).
The basic logic behing finding it is to traverse the tree in decreasing order and once you reach the nth node print that value.
Algo/Pseudocode looks like
findLargest(Node* root, int N)
1) if root is NULL then return
2) for every node go to the right of it and follow the steps from 1 to 2(a recursive call to findLargest function witn root as right)
Now we are at right most and current node is greatest
3) if ++index is equal to N then print the value of root and return
4) Go to left of node and follow the recurisve call to function findLargest with root as left.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.