Identify the ‘Bottleneck Spanning Tree’ of an undirected graph

Given an undirected graph, identify the ‘Bottleneck Spanning Tree’ of an undirected graph, which is defined to be any spanning tree that minimizes the weight of the heaviest edge used in the tree. In the usual ‘Minimum Spanning Tree’ problem, the sum of weights is minimized.

Identify if a given graph is a scorpion or not.

A scorpion is an undirected graph with 3 special vertices: the sting, the tail, and the body. The sting has degree one and is connected to the tail. The tail has degree two and is connected to the sting and the body. The body has degree n – 2 and is connected to all vertices except the sting. The other vertices may be arbitrarily connected with each other. Identify if a given graph is a scorpion or not.

Gray Code for Fibonacci Sequences: identify the starting string and then enumerate these positions in time proportional to the number of strings.

The number of binary strings of length k such that two 1′s are never adjacent in any string equals the k-th Fibonacci number. Further, these strings can be ordered to form a Gray code, which means that successive strings differ in only one position. For example, a Gray code for 3-bit strings is 100 101 001 000 010. The goal is to identify the starting string and then enumerate these positions in time proportional to the number of strings.

Working Computer Problem :discover an undamaged computer in as few queries as possible.

A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible.

implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise.

Animal behavior researchers would like to get information on animal movements in a valley. They have placed N motion sensors along a straight line crossing the valley at various heights. For 0 <= i <= N-1, the i-th sensor's height is h_i (0 <= h_i <= 1 000 000 000). No two sensors are on the same height.
Since the line is on a valley, the heights of sensors satisfy these constraints:

• there is an integer k (0 <= k <= N-1), such that the k-th sensor has the minimum height,
• for all 0 <= i < k, h_i > h_i+1, and
• for all k <= i < N-1, h_i < h_i+1.

However, because the sensor installation team forgot to measure the sensors' heights, the value of k, and all the heights h_i's are not known.
You would like to find if there is a sensor at height X. This seems to be hopelessly impossible, but you recall that each sensor has a height meter and can report its height. To minimize the power usage, you would like to make only a small number of height queries.

Implement

You have to implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise. Your procedure can call a procedure query(i) to get h_i. However, you can make at most 50 calls, for each run of procedure find.
Note: In a single run, the sample grader, provided with the prototype, may perform many calls to find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to procedure find. Therefore, you should not assume that two different calls to procedure find share the same height information.

Example

Suppose that N=4 and the height of each sensor is:

sensor	height
0	10
1	7
2	9
3	15

Note that in this case, k=1. The following are the return values from procedure query:

calls	returns
query(0)	10
query(1)	7
query(2)	9
query(3)	15

The correct implementation of procedure find, when called by the grader, should return as in the following table.

calls	returns
find(4,10)	1
find(4,2)	0
find(4,9)	1
find(4,15)	1
find(4,100)	0

find the maximum sum of temperatures of K consecutive days

Thailand is a tropical country. Thai people usually say that Thailand has 3 seasons: Hot Summer, Hotter Summer, and Hottest Summer. It especially feels very hot when you have many consecutive days with high temperatures.
You are planning a K-day trip to Thailand. Since you would like to experience the real Thai Summer, you want your stay to be as hot as possible.
You are given a list of forecasted temperatures of N consecutive days. You would like to find the maximum sum of temperatures of K consecutive days. It is guaranteed that 1 <= K <= N.

Implement 

You are to implement procedure maxk(N,T,K) that returns the maximum sum of temperatures of any K consecutive days, where N is the number of days and T is an array of positive integers where T[i], for 0 <= i < N, is the temperature of day i.

Example

Suppose that N=6, K=3 and T = 10 50 30 20 5 1.

There are 4 possible 3-day trips, starting from day 0, day 1, day 2, and day 3; and their sum of temperatures are 90, 100, 55, and 26. Therefore, procedure maxk should return 100.

Subtasks

Subtask 1

• N <= 1 000, 0 < T[i] <= 1 000

Subtask 2

• N <= 1 000 000, 0 < T[i] <= 1 000

you have to encode the data into a sequence of alphabets, transmit the encoded data, and decode it to obtain the original integer data.

You would like to transmit integer data through a special channel, i.e., this channel only supports transmission of alphabets a - z. In order to do so, you have to encode the data into a sequence of alphabets, transmit the encoded data, and decode it to obtain the original integer data.
The overall process is shown in the following figure.

       You have to implement:

• Procedure encode(N,D) that encodes the data, where N denotes the length of data and D is an array of integers representing the data, where D[i] is the i-th integer in the data. (0 <= D[i] <= 255.) This procedure must call procedure send_data(c) for each character c in the sequence to transmit the encoded data. Each encoded character c must be lowercase English alphabets, i.e., alphabets a - z.
  
  Procedure decode(M) that decodes the data, where M denotes the length of the encoded data. To read the encoded data as a sequence of characters, this procedure must call procedure read_data() for each character in the sequence. It may call read_data for at most M times. To output the decoded data, it must call procedure output_data(y) for each integer y in the decoded data.
  
   Follow Up
  

  Subtask 1

• N <= 100 and 0 <= D[i] <= 25.
• The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

        Subtask 2

• N <= 100.
• The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

        Subtask 3 (40 points)

• N <= 100.
• The encoded message should not contain more than 2N characters, i.e., encode may not call send_data more than 2N times.

You need to write a program that calculates the advanced edit distance of two given words.

The edit distance of two strings S and T is the minimum number of edit operations that need to be done to transform S into T . The valid edit operations are:
• Insert a single character at any position.
• Modify an existing character.
• Remove an existing character.
For example, the edit distance of “pantera” and “aorta” is 5, because the following chain of
edits is valid (and there is no shorter chain):
“pantera” >>> “antera” >>> “aotera” >>> “aoera” >>> “aora” >>> “aorta”.
We define the advanced edit distance in a similar way, but adding the swap of two adjacent characters as an extra valid operation. With this setting, the advanced edit distance of “pantera” and “aorta” is 4:
“pantera” >>> “antera” >>> “antra” >>> “aotra” >>> “aorta”.

You need to write a program that calculates the advanced edit distance of two given words.

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.

Transpose Algorithm 

Basically, we are converting rows into columns. E.g. a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should be changed to a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4.

a1 b1 c1 (i=1)

a2 b2 c2 (i=2)

a3 b3 c3 (i=3)

a4 b4 c4 (i= 4)

So we should write the array as a1 a2 a3 a4 b1 b2 b3 b4........, only this time, we are writiing column wise.

The program is recursive. The variable i is the number of groups

#include

#define SIZE 12 //multiple of 3

void arrange(int arr[], int n, int i)

{

if(i == 1)

{

arr[1] = arr[n];

arr[2] = arr[n <<1]

return;

}

int a = arr[i - 1];

int b = arr[n + i - 1];

int c = arr[2*n + i - 1];

arrange(arr, n, i - 1);

int x = 3 * (i - 1);

arr[x] = a;

arr[x + 1] = b;

arr[x + 2] = c;

}

int main()

{

int n = SIZE;

int a[SIZE], i;

printf("\nEnter %d numbers", SIZE);

for(i = 0; i <>

scanf("%d", a + i);

if(n != 0 && n % 3 == 0)arrange(a, n/3, n/3);

for(i = 0; i <n;i++)
printf(a[i]);

printf("\n");

}

Given a root and a node of a BST tree, write a function which print all the nodes which are a 'k' distance from the given nodes in sorted order. (distance can be upwards and downwards)