Analyze the following algorithm s and provide its worst case

Assignment Help Computer Engineering

Reference no: EM132096064

Please help

Question 1

In computer science, a program is called ____ if it is impossible to solve it with a polynomial-time algorithm.

(A) intractable

(B) complex

(D) transposable

When searching an array with 1,048,576 elements, how many comparisons will there be (at most) using binary search?

A) 8

B) 11

C) 21

D) 33

Which of the following problems has been proven not to have a polynomial-time solution?

A) Halting problem

B) chained matrix multiplication problem

C) sorting problem

D) shortest paths problem

Algorithms with time complexities such as n and 100n are called ____ algorithms.

A) linear-time

B) simple

C) first-order

D) one-to-one

It takes about ____ bits to encode a positive integer x in binary.

A) [lg x]

B) [lg x] + 1

C) x

D) x2

Question 2

Analyze the following algorithm S and provide its worst case time complexity measures.

Data is a global array of n elements of type keytype. Initial call to S is made:
S(0, n)

public static void S (index i, index j) {

index p;

if (j > i) {

p = subAlgoS (i, j);

S (i, p - 1);

S (p + 1, j);

}

public static void subAlgoS (index i, index j) {

index x, y, p;

keytype z;

z = Data[i];

y = i;

for (x = i + 1; x <= j; x++)

if (Data[x] < z) {

y++;

exchange Data[x] and Data[y];

}

p = y;

exchange Data[i] and Data[p];

return p;

}

Try to estimate average case performance and comment on the space complexity of the algorithm.

Question 3: Find the Big-Theta Complexity measures of the following recurrence relations:

T(n) = T(n/2) + 3n2 and T(1) = 5

T(n) = 4 T(n-1) + n4 + 2100 and T(1) = 100

Question 4: (20 points) Complete the following statements. Wherever applicable, assume the problem refers to which is a proper binary tree.

A tree T with 8 internal nodes will have __ external nodes, and __ total nodes.

The maximum number of external nodes in a tree with height of 5 will be __ and the maximum number of total nodes will be ____.

If a tree has 65 nodes altogether (i.e. total of internal and external nodes), its minimum and maximum height will be between min =___and max = ___.

Total number of nodes in a proper binary tree is always an (____ / odd) number.

If an expression tree contains 4 operators, it will contain_____ operands.

If an expression tree contains 4 operands, the number of possible expression tree topologies will be ______.

The height of the root node in a binary tree is ______.

Reference no: EM132096064

Questions Cloud

Technological and Strategical planning in New Ventures : Prepare a Mini Research project on the given topic. Topic: Technological and Strategical planning in New Ventures for solving Business start-up issues

Create a random sample of size 1000 from the diamonds data : Create a random sample of size 1000 from the diamonds data. Draw the scatterplot of carat vs log(price), color coded by cut.

Write the following functions for a linked list program : Write the following functions in C++ for a linked list program. Use separate .cpp main file for calling the functions to show they work.

Suggest a subset selection method and a shrinkage : Suggest a subset selection method and a shrinkage method that could be used here.

Analyze the following algorithm s and provide its worst case : When searching an array with 1,048,576 elements, how many comparisons will there be (at most) using binary search?

How many units on average while holding x2 constant : Suppose a multiple regression model is given by y = 4.44X1 -9.29X2 + 39.67. How do I determine what an interpretation of the coefficient of X1 be if X1

What are your thoughts about the intervention employed : What health state/health status and population resonated with you from the video - what was the primary determinant influencing their health state/health status

Create a main method and use these input files to test : Create a main method and use these input files to test that you are able to input the Undergraduates, put them into an ArrayList, print out the list.

Create an iterator that will allow the program to return : Create unique key values (Do not use map class from STD library.) Create an iterator that will allow the program to return the key,value pairs.

User Account

All Pages