Part A A1.1. f1 --> C:Theta(n) f2 --> E:Theta(n^2) f3 --> E:Theta(n^2) f4 --> B:Theta(log(n)) f5 --> D:Theta(n log(n)) A1.2. f1 --> A:Theta(1) f2 --> E:Theta(n^2) f3 --> C:Theta(n) f4 --> A:Theta(1) f5 --> A:Theta(1) A2.3. Table content after inserting C G F E D A B: 0:B 1:D 2:A 3:E 4:C 5:G 6:F A2.4. No sequence can result in 0:(E:3) 1:(F:5) 2:(G:4) 3:(A:2) 4:(B:3) 5:(C:4) 6:(D:1) A2.5. 0:(B:3) 1:(D:1) 2:(A:2) 3:(E:3) 4:(C:4) 5:(G:5) 6:(F:5) Yes, the sequence from question 3 gives the table. A2.6. No sequence results in 0:(G:4) 1:(C:4) 2:(A:2) 3:(D:1) 4:(B:3) 5:(E:3) 6:(F:5) A3.7. 375 33 12 / / 73 / 213 / / 619 378 / 596 469 / 574 550 534 / / / 589 / / / 787 635 / / / A3.8. One possible solution is: 534 213 596 33 378 574 635 12 73 375 469 550 589 619 787 A3.9. 12 213 73 33 534 550 589 574 469 596 378 635 787 619 A3.10. replacing by predecessor: 213 33 12 / / 73 / / 619 378 / 596 469 / 574 550 534 / / / 589 / / / 787 635 / / / replacing by successor: 378 33 12 / / 73 / 213 / / 619 596 469 / 574 550 534 / / / 589 / / / 787 635 / / / A4.11 call --> pivot 1 --> 12 2 --> 787 3 --> 33 4 --> 635 5 --> 73 6 --> 213 7 --> 375 8 --> 378 9 --> 469 10--> 534 11--> 619 12--> 596 13--> 550 14--> 574 remaining list of length 1 and no call is made. A4.12 call --> pivot 1 --> 534 2 --> 213 3 --> 33 two remaining lists of length 1 4 --> 378 two remaining lists of length 1 5 --> 596 6 --> 574 two remaining lists of length 1 7 --> 635 two remaining lists of length 1 A5.13. G A B F H E C with D before G, A, B, F or H A5.14. All nodes except for G, i.e., {A,B,C,D,E,F,H} Part B B1.15: no. The claim puts an upper bound, not a lower bound. B1.16: no. The claim puts an upper bound, not a lower bound. B1.17: no. Omega(n) still intersects Theta(n^2). B1.18: yes. All functions in Omega(n^2 log(n)) are "strictly worst" than those in Theta(n^2) and the claim is about worst case.. B1.19: yes. The claim is about best case and the family in question has strictly cheaper complexity (here 5n+3) then those captured by Theta(n^2). B1.20: yes. The claim is about best case and the family in question has strictly cheaper complexity (here O(n)) then those captured by Theta(n^2). B1.21: yes. The claim is about best case and all inputs have strictly cheaper complexity (here O(n)) then those captured by Theta(n^2). B1.22: no. t(n) can still be in Omega(n^2) since it is in Omega(n). B2.23: We argue g(n1, n2) = n1 + n2 is a tight bound for the worst-case time complexity of the method bar(lst1,lst2). This is because, given two lists lst1 and lst2 of sizes n1 and n2 respectively, a) bar starts by creating an empty list and by declaring two iterator variables it initializes to the beginning of lists lst1 and lst2. This corresponds to a finite number of instructions that does not depend on n1 or n2. b) It then repeatedly consumes, and inserts to the rslt list, the head of lst1 or of lst2 until at least one of them is empty. This involves, in each iteration, a finite number of instructions that again does not depend on n1 or n2. It then consumes the remaining elements and insert them to rslt (also a finite number of steps in each iteration). In total, bar only does a finite number of instructions for each element in lst1 and lst2, plus some initial and final fixed amount of instructions, hence, it is in Theta(n1 + n2). B2.24: We argue foo is in Theta(f(n)) with f(n) = n log(n) and where n is the length of input. To simplify, we assume n is a power of 2. * foo starts by dividing the input into two lists of size n/2 each (since n is a power of 2). This part of foo requires a number of instructions that is linear in n since a finite number of instructions is involved for each element of input. * foo then calls itself recursively on the two halves. * Observing the recursive calls to the two halves do not change the content of the halves and only rearranges them with the help of bar, we note that rslt1 and rslt2 are of size n/2 each. * then bar is called on the two halves returned by the two recursive calls to foo. This part is linear in n/2+n/2=n as described earlier. * the result of bar is returned as the result of foo. Hence, if foo_steps(n) is the number of steps needed for foo(lst) when lst has length n, then: foo_steps(n) = 2 foo_steps(n/2) + c n + d for n >= 2 and foo_steps(1) = e By unrolling, we get foo_steps(n) = 2 (2 foo_steps(n/2^2) + c n/2) + c n = ... = 2^(log2(n)) (foo_steps(1) + c n log2(n)) so foo_steps(n) in Theta(f(n)) for f(n)=n log(n) B2.25: Basically, the method needs to return true iff there is a triplet (a,b,c) of elements in lst for which a+b+c==0. We propose to write check as three simple nested loops: bool check(const list& lst) { for(list::const_iterator it1=lst.begin(); it1!=lst.end(); lst1++) { for(list::const_iterator it2=lst.begin(); it2!=lst.end(); lst2++) { for(list::const_iterator it3=lst.begin(); it3!=lst.end(); lst3++) { if(*it1 + *it2 + *it3 == 0) { return true; } } } } return false; } The method iterates through all possible triplets (*it1, *it2, *it3) in lst and checks if their sum is 0. It uses three simple for loops that each iterate through each element of lst. The if statement (which requires a finite amount of work) is therefore evaluated n^3 times in the worst case. The worst case complexity of check is therefore in Theta(n^3). B2.26: bool fasterCheck(const list& lst) { list sorted = foo(lst); for(list::const_iterator it1=lst.begin(); it1!=lst.end(); lst1++) { list::const_iterator it2= it1; list::const_iterator it3= lst.end(); it3--; while(it2 != it3) { if(*it1 + *it2 + *it3 > 0){ it3 --; }else if(*it1 + *it2 + *it3 < 0){ it2 ++; }else{ return true; } } if(*it1 + *it2 + *it3 == 0) { return true; } return false; } This code is strictly more efficient than check as argued in B2.27. It solves the same problem as check because, given the list lst, it starts by sorting it. So the content of sorted is the same as the content of lst, just sorted in increasing order. It will then iterate through some triplets (a,b,c) in lst and will return true if a+b+c==0. Clearly, if it returns true then it found a triple and it is a valid triplet for check who should also return true. It will also discard some triplets. Observe fastcheck only considers triplets (a,b,c) where a <= b <= c. This is enough since addition is commutative and checking all permutations of (a,b,c) is redundant. To only consider increasing triplets, it iterates through all possible smallest elements "a" (using it1 in the loop) and chooses candidate "b" to be the smallest element larger than "a" and "c" to be the largest element in the list. In addition, given an "a" : * if the sum is too large, then there is no need to consider larger b elements and the c has to be decreased. Indeed, larger b elements will only increase the sum which is already strictly positive. * if the sum is too small, then there is no need to consider smaller c elements and the b element has to be increased. Indeed, smaller c elements will only further decrease a sum that is already negative. * if the sum is 0 with the different b and c (in the while loop) or with different b and c (after the while loop for the same a), then true is returned. This way, only discards unsorted triplets or "hopeless" triplets (i.e., too large third term or too small second term). So if it returns false then check will also return false. B2.27: Sorting is in Theta(n log(n)) if foo is chosen (or in Theta(n^2) if insertion or selection sort is chosen). The for loop will repeat n times choosing larger and larger elements with it1. It involves a while loop in addition to a constant number of instructions in the if statement. In iteration i (for i in 1 to n) of the while loop, the loop will go through all remaining elements from it1, so n-i elements in the worst case. Each iteration of the while loop is in Theta(1). In the first iteration of the for loop, the while loop will make at most n-1 iterations. In the second iteration of the for loop, the while loop will make at most n-2 iterations. In the nth iteration of the for loop, the while loop will make 0 iteration. Hence, fastcheck will use, in the worst case, 1 + 2 + ... + (n-1) iterations of the while loop. Each iteration involves a finite number of instructions. Hence, fastechek is in Theta(n^2).