# Algorithms and Data Structures Related Questions

CHECK UPLOADED FILE FOR 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 )

Justify your answer.

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;

nodeType *llink;

nodeType *rlink;

};

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

relation to find the complexity of your code. Show your work.

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.

## Get Help With a similar task to - Algorithms and Data Structures Related Questions

##### Additional Instructions:

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 ) Justify your answer. 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; nodeType *llink; nodeType *rlink; }; 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 relation to find the complexity of your code. Show your work. 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. https://www.raywenderlich.com/4946/introduction-to-a-pathfinding

## Related Questions

Tutlance Experts offer help in a wide range of topics. Here are some of our top services:

- Math homework help
- Nursing homework help
- Statistics homework help
- Nursing coursework help
- Capstone project writing services
- Essay writers for hire
- Case study writing help
- Buy college papers online
- Buy college research papers
- College homework help
- Professional resume writing services
- Programming homework help
- Coursework writing help
- Term paper writing help
- Biology homework help
- Do my physics homework
- Dissertation data analysis help
- PhD Dissertation writing services
- Chemistry homework help

Post your project now for free and watch professional experts outbid each other in just a few minutes.