CS61B Textbook
  • Contributors
  • DISCLAIMER
  • 1. Introduction
    • 1.1 Your First Java Program
    • 1.2 Java Workflow
    • 1.3 Basic Java Features
    • 1.4 Exercises
  • 2. Defining and Using Classes
  • 3. References, Recursion, and Lists
  • 4. SLLists
  • 5. DLLists
  • 6. Arrays
  • 7. Testing
  • 8. ArrayList
  • 9. Inheritance I: Interface and Implementation Inheritance
  • 10. Inheritance II: Extends, Casting, Higher Order Functions
    • 10.1 Implementation Inheritance: Extends
    • 10.2 Encapsulation
    • 10.3 Casting
    • 10.4 Higher Order Functions in Java
    • 10.5 Exercises
  • 11. Inheritance III: Subtype Polymorphism, Comparators, Comparable
    • 11.1 A Review of Dynamic Method Selection
    • 11.2 Subtype Polymorphism vs Explicit Higher Order Functions
    • 11.3 Comparables
    • 11.4 Comparators
    • 11.5 Chapter Summary
    • 11.6 Exercises
  • 12. Inheritance IV: Iterators, Object Methods
    • 12.1 Lists and Sets in Java
    • 12.2 Exceptions
    • 12.3 Iteration
    • 12.4 Object Methods
    • 12.5 Chapter Summary
    • 12.6 Exercises
  • 13. Asymptotics I
    • 13.1 An Introduction to Asymptotic Analysis
    • 13.2 Runtime Characterization
    • 13.3 Checkpoint: An Exercise
    • 13.4 Asymptotic Behavior
    • 13.6 Simplified Analysis Process
    • 13.7 Big-Theta
    • 13.8 Big-O
    • 13.9 Summary
    • 13.10 Exercises
  • 14. Disjoint Sets
    • 14.1 Introduction
    • 14.2 Quick Find
    • 14.3 Quick Union
    • 14.4 Weighted Quick Union (WQU)
    • 14.5 Weighted Quick Union with Path Compression
    • 14.6 Exercises
  • 15. Asymptotics II
    • 15.1 For Loops
    • 15.2 Recursion
    • 15.3 Binary Search
    • 15.4 Mergesort
    • 15.5 Summary
    • 15.6 Exercises
  • 16. ADTs and BSTs
    • 16.1 Abstract Data Types
    • 16.2 Binary Search Trees
    • 16.3 BST Definitions
    • 16.4 BST Operations
    • 16.5 BSTs as Sets and Maps
    • 16.6 Summary
    • 16.7 Exercises
  • 17. B-Trees
    • 17.1 BST Performance
    • 17.2 Big O vs. Worst Case
    • 17.3 B-Tree Operations
    • 17.4 B-Tree Invariants
    • 17.5 B-Tree Performance
    • 17.6 Summary
    • 17.7 Exercises
  • 18. Red Black Trees
    • 18.1 Rotating Trees
    • 18.2 Creating LLRB Trees
    • 18.3 Inserting LLRB Trees
    • 18.4 Runtime Analysis
    • 18.5 Summary
    • 18.6 Exercises
  • 19. Hashing I
    • 19.1 Introduction to Hashing: Data Indexed Arrays
      • 19.1.1 A first attempt: DataIndexedIntegerSet
      • 19.1.2 A second attempt: DataIndexedWordSet
      • 19.1.3 A third attempt: DataIndexedStringSet
    • 19.2 Hash Code
    • 19.3 "Valid" & "Good" Hashcodes
    • 19.4 Handling Collisions: Linear Probing and External Chaining
    • 19.5 Resizing & Hash Table Performance
    • 19.6 Summary
    • 19.7 Exercises
  • 20. Hashing II
    • 20.1 Hash Table Recap, Default Hash Function
    • 20.2 Distribution By Other Hash Functions
    • 20.3 Contains & Duplicate Items
    • 20.4 Mutable vs. Immutable Types
  • 21. Heaps and Priority Queues
    • 21.1 Priority Queues
    • 21.2 Heaps
    • 21.3 PQ Implementation
    • 21.4 Summary
    • 21.5 Exercises
  • 22. Tree Traversals and Graphs
    • 22.1 Tree Recap
    • 22.2 Tree Traversals
    • 22.3 Graphs
    • 22.4 Graph Problems
  • 23. Graph Traversals and Implementations
    • 23.1 BFS & DFS
    • 23.2 Representing Graphs
    • 23.3 Summary
    • 23.4 Exercises
  • 24. Shortest Paths
    • 24.1 Introduction
    • 24.2 Dijkstra's Algorithm
    • 24.3 A* Algorithm
    • 24.4 Summary
    • 24.5 Exercises
  • 25. Minimum Spanning Trees
    • 25.1 MSTs and Cut Property
    • 25.2 Prim's Algorithm
    • 25.3 Kruskal's Algorithm
    • 25.4 Chapter Summary
    • 25.5 MST Exercises
  • 26. Prefix Operations and Tries
    • 26.1 Introduction to Tries
    • 26.2 Trie Implementation
    • 26.3 Trie String Operations
    • 26.4 Summary
    • 26.5 Exercises
  • 27. Software Engineering I
    • 27.1 Introduction to Software Engineering
    • 27.2 Complexity
    • 27.3 Strategic vs Tactical Programming
    • 27.4 Real World Examples
    • 27.5 Summary, Exercises
  • 28. Reductions and Decomposition
    • 28.1 Topological Sorts and DAGs
    • 28.2 Shortest Paths on DAGs
    • 28.3 Longest Path
    • 28.4 Reductions and Decomposition
    • 28.5 Exercises
  • 29. Basic Sorts
    • 29.1 The Sorting Problem
    • 29.2 Selection Sort & Heapsort
    • 29.3 Mergesort
    • 29.4 Insertion Sort
    • 29.5 Summary
    • 29.6 Exercises
  • 30. Quicksort
    • 30.1 Partitioning
    • 30.2 Quicksort Algorithm
    • 30.3 Quicksort Performance Caveats
    • 30.4 Summary
    • 30.5 Exercises
  • 31. Software Engineering II
    • 31.1 Complexity II
    • 31.2 Sources of Complexity
    • 31.3 Modular Design
    • 31.4 Teamwork
    • 31.5 Exerises
  • 32. More Quick Sort, Sorting Summary
    • 32.1 Quicksort Flavors vs. MergeSort
    • 32.2 Quick Select
    • 32.3 Stability, Adaptiveness, and Optimization
    • 32.4 Summary
    • 32.5 Exercises
  • 33. Software Engineering III
    • 33.1 Candy Crush, SnapChat, and Friends
    • 33.2 The Ledger of Harms
    • 33.3 Your Life
    • 33.4 Summary
    • 33.5 Exercises
  • 34. Sorting and Algorithmic Bounds
    • 34.1 Sorting Summary
    • 34.2 Math Problems Out of Nowhere
    • 34.3 Theoretical Bounds on Sorting
    • 34.4 Summary
    • 34.5 Exercises
  • 35. Radix Sorts
    • 35.1 Counting Sort
    • 35.2 LSD Radix Sort
    • 35.3 MSD Radix Sort
    • 35.4 Summary
    • 35.5 Exercises
  • 36. Sorting and Data Structures Conclusion
    • 36.1 Radix vs. Comparison Sorting
    • 36.2 The Just-In-Time Compiler
    • 36.3 Radix Sorting Integers
    • 36.4 Summary
    • 36.5 Exercises
  • 37. Software Engineering IV
    • 37.1 The end is near
  • 38. Compression and Complexity
    • 38.1 Introduction to Compression
    • 38.2 Prefix-free Codes
    • 38.3 Shannon-Fano Codes
    • 38.4 Huffman Coding Conceptuals
    • 38.5 Compression Theory
    • 38.6 LZW Compression
    • 38.7 Summary
    • 38.8 Exercises
  • 39. Compression, Complexity, P = NP
    • 39.1 Models of Compression
    • 39.2 Optimal Compression, Kolmogorov Complexity
    • 39.3 Space/Time-Bounded Compression
    • 39.4 P = NP
    • 39.5 Exercises
Powered by GitBook
On this page
  • Factual
  • Procedural
  • Metacognitive
  1. 15. Asymptotics II

15.6 Exercises

Doing more practices is the best way to gain intuition when it comes to asymptotics!

Factual

  1. Prove that Θ(log⁡2n)=Θ(log⁡3n)\Theta(\log _{2} n) = \Theta(\log _{3} n)Θ(log2​n)=Θ(log3​n).

  2. What is the runtime of the following function?

public static int f(int n) {
    if (n <= 1) {
        return 0;
    }
    return f(n - 1) + f(n - 1) + f(n - 1);
}
Problem 1

Using the properties of logs, we see that log⁡2n=log⁡nlog⁡2=Θ(log⁡n)\log_2 n = \frac{\log n}{\log 2} = \Theta(\log n)log2​n=log2logn​=Θ(logn). Similarly, log⁡3n=log⁡nlog⁡3=Θ(log⁡n)\log_3 n = \frac{\log n}{\log 3} = \Theta(\log n)log3​n=log3logn​=Θ(logn). So when consiering asymptotics relating to logarithms, the base does not matter (as long as it is some constant).

Problem 2

This is essentially fib with 3 recursive calls instead of 2. The runtime is Θ(3n)\Theta(3^n)Θ(3n).

Procedural

  1. Find the runtime of running print_fib with for arbitrarily large n.

public void print_fib(int n) {
   for (int i = 0; i < n; i++) {
       System.out.println(fib(i));
   }
}

public int fib(int n){
   if (n <= 0) {
     return 0;
   } else if (n == 1) {
     return 1;
   } else {
     return fib(n-1) + fib(n-2);
   }
}
  1. Do the above problem again, but change the body of the for loop in print_fib to be:

 System.out.println(fib(n));
  1. Find the runtime of the function f on an input of size n, given the createArray function as described below:

public static void f(int n) {
    if (n == 1) {
        return;
    }
    f(n / 2);
    f(n / 2);
    createArray(n);
}

public int[] createArray(int Q) {
    int[] x = new int[Q];
    for (int i = 0; i < x.length; i++) {
        x[i] = i;
    }
    return x;
}
Problem 1

From lecture, we know that fib(i) runs in roughly 2i2^i2i time. If we run fib for each i from 1 to n, we get a total work of 20+21+...2n2^0 + 2^1 + ... 2^n20+21+...2n. Note that this is a geometric sum with last term 2n2^n2n, so the overall runtime is actually still Θ(2n)\Theta(2^n)Θ(2n).

Problem 2

Again, we know that fib(i) takes about 2i2^i2i time. However, this time we call fib(n) each time in the loop n total times. This gives a runtime of Θ(n2n)\Theta(n2^n)Θ(n2n).

Problem 3

This function creates two recursive branches of half the size per call, with each node taking linear work. As such, each level has nnn total work, and since we halve the input each time, there are log⁡n\log nlogn total levels, for a runtime of Θ(nlog⁡n)\Theta(n \log n)Θ(nlogn).

Problem 4
Problem 5

Metacognitive

  1. What would the runtime of modified_fib be? Assume that values is an array of size n. If a value in an int array is not initialized to a number, it is automatically set to 0.

public void modified_fib(int n, int[] values) {
   if (n <= 1) {
     values[n] = n;
     return n;
   } else {
     int val = values[n];
     if (val == 0) {
       val = modified_fib(n-1, values) + modified_fib(n-2, values);
       values[n] = val;
     }
     return val;
   }
}  
Problem 1

This is an example of dynamic programming, a topic covered in more depth in CS170. Note that since values is saved across calls, we only recompute each value of n once. Computing a single value of n only takes constant time, since we just add two already-computed values or do an array access. As such, the overall runtime is linear: Θ(n)\Theta(n)Θ(n).

Previous15.5 SummaryNext16. ADTs and BSTs

Last updated 2 years ago

from the Spring 2018 Midterm 2

from the Spring 2017 Midterm 2

and are linked here and on the course website.

are linked here and on the course website.

Problem 8
Problem 4
Solutions
walkthrough
Solutions