CS 61B More Asymptotics and ADTs
Spring 2021
1 Asymptotics is Fun!
Exam Prep Discussion 7: March 1, 2021
(a) Using the function g defined below, what is the runtime of the following func- tion calls? Write each answer in terms of N.
6 7} 8}
(b)
void g(int N, int x) { if (N == 0) {
1
2
3
4}
5 for (int i = 1; i <= x; i++) {
return;
g(N - 1, i);
g(N, 1): ¦¨( ) g(N, 2): ¦¨( )
Solution:
g(N, 1): ¦¨(N) g(N, 2): ¦¨(N2)
Suppose we change line 6 to g(N - 1, x) and change the stopping condition in the for loop to i <= f(x) where f(x) returns a random number between 1 and x, inclusive. For the following function calls, find the tightest ¦¸ and big O bounds.
6 7} 8}
void g(int N, int x) { if (N == 0) {
1
2
3
4}
5 for (int i = 1; i <= f(x); i++) {
return;
g(N - 1, x);
g(N, 2): ¦¸( ), O( ) g(N, N): ¦¸( ), O( )
Solution:
g(N, 2): ¦¸(N), O(2N) g(N, N): ¦¸(N), O(NN)
5 6 7 8 9
10 11 12
if (i == stop) { flop(i, N);
return; }
2 More Asymptotics and ADTs 2 Flip Flop
Suppose we have the flip function as defined below. Assume the method unknown returns a random integer between 1 and N, exclusive, and runs in constant time. For each definition of the flop method below, give the best and worst case runtime of flip in ¦¨(.) notation as a function of N.
public static void flip(int N) { if (N <= 100) {
return;
int stop = unknown(N);
for (int i = 1; i < N; i++) {
1
2
3 4}
} }
(a) public static void flop(int i, int N) { flip(N - i);
}
Best Case: ¦¨( ), Worst Case: ¦¨( )
Solution:
Best Case: ¦¨(N), Worst Case: ¦¨(N)
(b) public static void flop(int i, int N) { int minimum = Math.min(i, N - i); flip(minimum);
flip(minimum);
}
Best Case: ¦¨( ), Worst Case: ¦¨( )
Solution:
Best Case: ¦¨(1), Worst Case: ¦¨(Nlog(N))
(c) public static void flop(int i, int N) { flip(i);
flip(N - i); }
Best Case: ¦¨( ), Worst Case: ¦¨( )
Solution:
Best Case: ¦¨(N), Worst Case: ¦¨(N2)
10 11 12 13
factor += 1; }
return count; }
Best Case: ¦¨( ), Worst Case: ¦¨( )
3 Prime Factors
Determine the best and worst case runtime of prime_factors in ¦¨(.) notation as a function of N.
int prime_factors(int N) { int factor = 2;
int count = 0;
while (factor * factor <= N) {
while (N % factor == 0) { System.out.println(factor); count += 1;
N = N / factor;
1
2
3
4
5
6
7
8 9}
Solution:
¡Ì
Best Case: ¦¨(log(N)), Worst Case: ¦¨( N)
More Asymptotics and ADTs 3
4 More Asymptotics and ADTs 4 ADT Selection
Suppose we have a TA Shreyas who teaches multiple discussion sections! A student may frequent more than one discussion section. For each situation below, choose the best ADT(s) out of the following ¡ª Map, Set, List ¡ª and explain how you can use the ADT(s) to solve the problem. Each subpart is independent of the previous. One answer may involve multiple ADTs. There may be mutliple efficient answers for each problem.
1. Storing all the Students in Shreyas¡¯s first section in alphabetical order.
2. Storing all the Students by their section, where Students within a section are sorted alphabetically.
3. Storing the Students in all of Shreyas¡¯s sections. There shouldn¡¯t be dupli- cates.
4. Determining all the Students that attend more than one of Shreyas¡¯s sections.
5. Quickly getting a Student by sid.
6. Quickly getting a Student by name or sid. Names aren¡¯t necessarily unique.
7. Cycling through the Students in one discussion section.
Solution:
1. Put the Students in a List in alphabetical order.
2. Use a Map, where each Section maps to an alphabetically ordered List of
Students in that section.
3. Use a Set. Add all the Students to the Set.
4. Use two Sets. The first Set will store all the students seen so far, and the second Set will be our answer. Iterate through the Students in each Section and, if the first set contains the Student, add it to the second set. Otherwise, add the Student to the first set.
More Asymptotics and ADTs 5
5. Use a Map, where each sid maps to one Student.
6. Use two Maps, where the first map works as described in the previous part and the second map maps names to a Set of Students of the given name.
7. Put the Students in a List, a LinkedList recommended. Repeat removing from the front and reinserting at the back.