1 . Assume that you have an array A of length 1000000 (1e6). In a test you find
ID: 3871600 • Letter: 1
Question
1. Assume that you have an array A of length 1000000 (1e6). In a test you find out that reading the element A[999] takes 1ms (you obviously have a slow computer). How long will it take to read the element A[999999]?
A. 1/10ms
B. 1ms
C. 10ms
D. 1000ms
2. Assume you have a Single Linked List L with head reference and without tail reference, L is of length 1000000 (1e6). In a test you find out that reading the element at index 999 takes 1ms. How long will it take to read the element at index 999999?
A. 1/10ms
B. 1ms
C. 10ms
D. 1000ms
II. Essay question (30 pts)
1. What is the order of magnitude of the following code-part (assume that "n" denotes the number of input data elements)?
for (int j = 0; j<n; j++){
for (int i = 0; i<20; i++){
System.out.println( i );
}
}
2. What is the order of magnitude of the following code-part (assume that "n" denotes the number of input data elements)?
for (int j = 0; j<20; j++){
for (int i = 0; i<20; i++){
System.out.println( n );
}
}
III. Coding (60 pts = 2 x 30 points)
1. For the class SimpleLinkedList2 given to you in Lec#7 (folder: Lec7-Code/linkedlist_demo), write a method:
public int getTotal()
The method sums up all integer values in the calling object of SimpleLinkedList2 and returns the sum. Your code CANNOT call any other methods in this class or any other class. It means that you have to implement it from scratch and walk down the list of Nodes “in-person”.
Hint: Your code is inside the class SimpleLinkedList2 and has direct access to the data fields in the calling object of SimpleLinkedList2.
2. Assume that you have a main(…) method in the client class of the SingleLinkedList<E> class. In this main(…) method, there is a variable numberList of type SingleLinkedList<Integer>. numberList references a single linked list of Integer objects. The number of items in this list varies (0, 1, 2, …). Write a code fragment in this main(…). Your code fragment sums up all integer values in this single linked list.
Hints: Your code is outside the class SingleLinkedList<E> and DOES NOT have direct access to the data fields in this SingleLinkedList<Integer>.
Explanation / Answer
1. it takes just 1 ms even for A[999999], because internally all it does is takes pointer address of A and does A+(sizeof(type_of_A)*index) to get a value of A[index].
2. it takes 1000ms since linked list has to go through every single element in it.
3. n iterations * 20 iterations for every iteration == 20N
Magnitude = O(N)
4. 20 iterations * 20 iterations for every outer iteration == 400 iterations (constant)
Magnitude = O(1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.