# Algorithms and Data Structures Related Questions

1

I.

a. Write a recursive function Int2Bin (int x) that takes as input an integer and prints out the corresponding binary number. For example calling Int2Bin(19) should print 10011. You function cannot use bitwise operations such as XOR, NOT, AND,â¦ You are NOT allowed to use any additional data structure (array, stack, queue,â¦). You can use any programming language.

Int2Bin(int x) {

}

b. Choose carefully a basic operation and find the recurrence relationship for the number of basic operations done by Int2Bin().

c. Solve the recurrence relationship in order to find the complexity of the function Int2Bin().

II. Many operations can be performed faster on sorted than on unsorted data. For which of the following operations is this the case? Justify your answer. Only answer with the right justification will get points.

â¢ Finding the item with a minimum value

â¢ Computer an average of values

â¢ Finding the middle value (the median)

â¢ Finding the value that appear most frequently in the data

III. After two iterations (passes) of a sorting algorithm, the following array:

has been rearranged as shown below

Which sorting algorithm has been use (selection, insertion, or bubble)? Defend your answer. Only answer with the right justification will get points.

Arr =

47

3

66

32

56

92

Arr =

3

47

66

32

56

92

2

IV. Given the original bubblesort algorithm

template <class T>

void bublesort(T data[], int n){

for (int i=0;i<n-1;i++)

for (int j=n-1;j>i;--j)

if (data[j]<data[j-1])

swap(data[j],data[j-1]);

a. Will the algorithm work properly if the inner for loop

for (int j = n-1 ; j > i; --j )

is replaced by

for (int j = n-1 ; j > 0; --j )

b. What would be the complexity of the resulting algorithm?

V.

a. Given a stack S1 of positive integer values, write the code for an algorithm,

SortStack(), that sorts all elements in S1 in increasing order, with the largest value at

the bottom of the stack. You can only use the following basic operation on stacks:

size(), push(), top(), and pop(). You can only use only ONE extra stack, S2, if

needed.

b. If each of the basic operation on the stack (size(), push(), top(), and pop() ) has a

complexity of O(1), what is the complexity of your code, assuming you have n

elements in the stack?

VI. Given the following array of integers Arr. If the array Arr is to be sorted in increasing

order, show how the array would look like after the FIRST iteration using the Quick

sorting algorithm. One iteration for the Quick sort means selecting one pivot and sorting

all the elements around the pivot, and putting the pivot in the right place. Base your

output on the quick sorting algorithms that was presented in the slides. No other approach

for sorting will be accepted. Show all intermediate steps.

Arr = 7 5 19 14 2 12 9 11 17 4 27 21 10 8 6

3

VII. Given the following definition of node for a binary tree:

//Definition of the node

struct nodeType

{

int info;

};

Using the following definition for the function visit(), show how the following binary

tree will look like after applying the inorder() traversal on the following tree. What is

the output of the in-order traversal?

visit(nodeType *p)

{

if ((p->llink!= NULL) && (p->info < 10))

{

p->info + = 2;

cout(p->info); // print the info the node

}

}

4

VIII.

a. Write the recursive version of the following function:

int sumCube (int n){

int Sum = 0;

for ( int i = 1 ; i <= n ; i++)

Sum = Sum + i*i*i;

return Sum;

}

b. Using multiplication â*â as basic operation, derive and solve the recurrence

IX. For this exercise, use the following modular arithmetic hashing function to find the index

of the element in the hash table: Hash(x) = x mod 13.

a. Using Open Addressing with Quadratic Probing, show how the following table HT

would look like after inserting the following elements in this order into the table: 25, 27,

12,13, 22, 38, 51,64,77, 26, 1, 23, 24

0 1 2 3 4 5 6 7 8 9 10 11 12

HT

b. If you are using a marker of â-1â to mark a deleted entry in the hashing table, and using

Open Addressing with Quadratic Probing, show how the table from part a would look

like after deleting 23, 24, 25 and then adding 36 and 49 to the table.

0 1 2 3 4 5 6 7 8 9 10 11 12

HT

5

X. Use the same approach from the following website

(https://www.raywenderlich.com/4946/introduction-to-a-pathfinding) and as illustrated in

the class to show how the cat Moody can use the A* algorithm to get to the bone. Use the

same approach to show the results of each step, including the open and closed list (you can

use different colors of lists and pictures to show intermediate steps). Use also the same

movement cost and heuristic computation approach.

## Related Questions

Similar orders to Algorithms and Data Structures Related Questions
18
Views
0
Nested imbalanced design of expriment using Box-Adjusted wald-type test
I need to provide statistical analysis of a nested design non-balanced design of experiment. I am hoping to have the implementation in either R, SPSS, or both. I will need the answers to be provided as shown in the attached file (Project.docx), and also wo...
32
Views
0
CMPT 200 Coding Homework
Write a class called Fraction that can store a rational number (reminder: those numbers that can be expressed in the form a/b, where a and b are integers are rational numbers). For example, a variable with a value of Â½ would be created using oneHalf ...
15
Views
0
Artificial Inteligence System Technique
This is a Master Degree course and I have attached example questions, there are 5 questions and only 3 need to be answered. We will get the actual questions on the day of the exam and they need to be completed within 2 hours, which means the expert has to ...
18
Views
0