Theoretical Part:
1. What is the largest size n of problem which can be solved in one second by an algorithm with the following running time functions, in microseconds (1 second = 1,000,000
log n microseconds): a) log2n b) √n c) n d) n2 e) (log2n) 2
2. Justify the following statements using the “big-Oh” definition:
a) (n+25)2 is O(n2) , and n2 is O((n+25)2)
b) n3 is NOT O(n2);
c) Given f1(n) is (n+25)2 , and f2(n) is n3 what is the big-Oh for f1(n) x f2(n)?
3. Give the asymptotic (“big-Oh”) running time complexity of the following algorithm, show all the work you have done.
Algorithm: ArrayMangle(A[ ], int n) Input: an array A, an integer n x = 0;
for (i=0; i<=n-1; i++) {
for (j=i; j<=n-1; j++) { x = x + A[j];
}
for (k=0; k<= n-1; k++) {
for (j=0; j< =n-1; j++) { x = x + A[j]*A[k];
} }
}
Programming Part (preferably using Java):
4. Implement the stack ADT with singly linked list (without using classes from any Library). Use the data given, ds20s-a1.txt, in the following file(see the Lab section) to stack (INPUT/PUSH) the operand(s) (data) and the data in each subsequent line(s) until another POP command is encountered. If the command is POP, un-stack (pop) the top of the stack. For the command PRINT, output the contents of the stack from the ‘top’ to the ‘bottom’. If the stack is empty, a POP or PRINT operation should produce an error message.(The marker may change the data to see if your program works for any similar data set with different order)
What is the top element of the stack once the above file is completely processed?
