DATA STRUCTURES AND ALGORITHM ANALYSIS IN JAVA 1. Arrays vs Arraylist Methods -

Question

DATA STRUCTURES AND ALGORITHM ANALYSIS IN JAVA

1. Arrays vs Arraylist

Methods - search ()/sort (), add ()/remove ()

INCLUDE Sort/search algorithms

Analysis of Time for n= 100 n = 1000, n = 10000.

Use random numbers for input

2. #2.20 (Program) just code and analysis

#2.20

a. Write a program to determine if a positive integer, N, is prime.
b. In terms of N, what is the worst-case running time of your program? (You should be able to do this in O(?N).)
c. Let B equal the number of bits in the binary representation of N. What is the value of B?
d. In terms of B, what is the worst-case running time of your program?
e. Compare the running times to determine if a 20-bit number and a 40-bit number are prime.
f. Is it more reasonable to give the running time in terms of N or B? Why?

3. Tower of Hanoi

Use recursion for program and include Big O-Notation analysis for the code

And also discuss greedy algorithm analysis.

1. Arrays vs Arraylist Methods - search ()/sort (), add ()/remove () INCLUDE Sort/search algorithms Analysis of Time for n= 100 n = 1000, n = 10000 Use random numbers for input 2. #2.20 (Program) just code and analysis a. Write a program to determine if a positive integer, N, is prime. b. In terms of N, what is the worst-case running time of your program? (You should 2.20 be able to do this in O(VN).) c. Let B equal the number of bits in the binary representation of N. What is the value of B? d. In terms of B, what is the worst-case running time of your program? e. Compare the running times to determine if a 20-bit number and a 40-bit number are prime f. Is it more reasonable to give the running time in terms of N or B? Why 3. Tower of Hanoi Use recursion for program and include Big O-Notation analysis for the codee And also discuss greedy algorithm analysis.

Explanation / Answer

Question 2

a. Write a program to determine if a positive integer, N, is prime.

boolean is_prime(int N){
   int k = 2;
   while (k*k <= N){
       if (n % k == 0) return false;
       k += 1;
   }
   return true;
}

b) In terms of N, what is the worst-case running time of your program? (You should be able to do this in O(N).)
=> Since our while loop run till k < N, so time complexity of above program is N.

c) Let B equal the number of bits in the binary representation of N. What is the value of B?
=> B = ceil(log2 N) where ceil(x) gives smallest integer that is greater than or equal to x.


//Question 3
//Tower of Hanoi

void shift(scr, mid){
   System.out.println("Move the top disk from "+src+" to "+mid);
}

void hanoi(scr,dst,mid,n){
   if (n == 1)
       shift(scr,mid);
   else{
       hanoi(scr,mid,dst,n-1);
       shift(scr,mid);
       hanoi(dst,scr,mid,n-1);
   }
}

Time complexity
O(2^n) where n is number of disk

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.