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
  • Conceptual
  • Procedural
  • Metacognitive
  1. 10. Inheritance II: Extends, Casting, Higher Order Functions

10.5 Exercises

Factual

Recall that the maxDog method has the following signature:

public static Dog maxDog(Dog d1, Dog d2) { … }
  1. What is the static type of Dog.maxDog(dogC, dogD)?

ShowDog dogC = new ShowDog("Franklin", "Malamute", 180, 6);
ShowDog dogD = new ShowDog("Gargamel", "Corgi", 44, 12);

Dog.maxDog(dogC, dogD);
  1. Which (if any), will compile:

Dog md = Dog.maxDog(dogC, dogD);
ShowDog msd = Dog.maxDog(dogC, dogD);
  1. In the code below, what are the dynamic types of o, d, stuff[0], and stuff[1]?

Object o = new Dog("Hammy", "Beagle", 15);
Dog d = new ShowDog("Ammo", "Labrador", 54);
Object stuff[] = new Object[5];
stuff[0] = o;
stuff[1] = d;
studd[2] = null;
Problem 1

The static type is Dog, the declared return type of the maxDog method.

Problem 2

Only the first line compiles. The static return type of maxDog is Dog, a superclass of ShowDog, so the compiler assumes that this method call return value is too broad for our declared variable msd.

Dog md = Dog.maxDog(dogC, dogD);
// ShowDog msd = Dog.maxDog(dogC, dogD);
Problem 3
  • o: Dog, since it is instantiated as a Dog.

  • d: ShowDog, since it is instantiated as a ShowDog.

  • stuff[0]: Dog, since it points to the same object as o, which has dynamic type Dog.

  • stuff[1]: ShowDog, since it points to the same object as d, which has dynamic type ShowDog.

Conceptual

  1. Is it possible for an interface to extend a class? Provide an argument as to why or why not.

  2. What are the differences between extends and implements inheritance? Is there a particular time when you would want to use one over the other?

Problem 1

This is not possible in Java. Conceptually, the reasoning is that classes have implementation details for each method, whereas interfaces do not implement methods. Thus, there is no way for an interface to "inherit" implementations from a superclass.

Problem 2

The primary difference is that extends inherits implementations, allowing a subclass to reuse code from the superclass, while implements only serves as a "contract" that a class will implement certain methods.

Use extends when you want a subclass to have the same behavior as a superclass in certain methods. Use implements when subclasses have different implementations of the same conceptual methods, or when you need to inherit from multiple supertypes.

Procedural

  1. Say there is a class Poodle that inherits from Dog. The Dog class looks like this:

public class Dog {
  int weight;
  public Dog(int weight_in_pounds) {
    weight = weight_in_pounds;
  }
}

And the Poodle class looks like this:

public class Poodle extends Dog {
 public Poodle() {}
}

Is this valid? If so, explain why. If it is not valid, then explain how we can make it valid.

  1. The Monkey class is a subclass of the Animal class and the Dog class is a subclass of the Animal class. However, a Dog is not a Monkey nor is a Monkey a Dog. What will happen for the following code? Assume that the constructors are all formatted properly.

Monkey jimmy = new Monkey("Jimmy");
Dog limmy = (Dog) jimmy;
  1. How about for this code? Provide brief explanation as to why you believe your answers to be correct.

Monkey orangutan = new Monkey("fruitful");
Dog mangotan = ((Dog) ((Animal) orangutan));
Problem 1

This will not compile because the Poodle constructor implicitly calls the Dog constructor (through super), but the Dog class has no zero-argument constructor.

To make this valid, we could add a zero-argument Dog constructor, or make the Poodle constructor take in an int argument and call super(weight_in_pounds).

Problem 2

This will not compile, since casting to a "sibling" class (same parent class, but unrelated), will error during compile.

Problem 3

This compiles, since the static types match up: mangotan is declared as a Dog and cast to a Dog on the right-hand side. However, the dynamic type of orangutan is a monkey, and we will run into a casting error since the Monkey class is unrelated to the Dog class.

Metacognitive

Problem 1
Problem 2

Previous10.4 Higher Order Functions in JavaNext11. Inheritance III: Subtype Polymorphism, Comparators, Comparable

Last updated 1 year ago

from the Spring 2018 Midterm 1

from the Spring 2017 Midterm 1

and are linked here and on the course website.

and are linked here and on the course website.

Problem 1
Problem 1
Solutions
walkthrough
Solutions
walkthrough