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

Login to view and/or buy answers.. or post an answer
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

Similar orders to Algorithms and Data Structures Related Questions
18
Views
0
Answers
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
Answers
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
Answers
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
Answers
Simulating Networks
Here are the details of first assignment for Computer Networks class. This is a pretty basic assignment with very little work but you will have to do initial setup for virtual box on your machine. Here are the details on how to do the setup: Download virt...