CS61B

Object-Oriented Programming ​

• A model for organizing programs
  • Modularity: Define each piece without worrying about other pieces, and they all work together.
  • Allows for data abstraction: You can interact with an object without knowing how it’s implemented.
• Objects
  • An object bundles together information and related behavior.
  • Each objet has its own local state.
  • Several objects may all be instances of a common type.
• Classes
  • A class serves as a template for all of its instance.
  • Each object is an instance of some class.

Static and non-static ​

• 静态方法和常量只能通过类名调用
• 非静态方法可以通过实例名调用

Question ​

据我所知，静态方法内能执行的只有静态方法，那么通过调用实例的非静态方法是如何执行的?

• 静态方法始终只能调用的是同一个类中的静态方法，而实例与它无关
• 静态方法无法直接访问实例方法或实例变量，但可以通过接受实例对象作为参数间接调用实例方法

Primitive Types and References Types ​

• 等号的黄金法则：=始终传递变量空间（memory box）的比特位
• 原始类型变量的变量空间保存变量的值，引用类型变量的变量空间保存实例的空间地址

Build a List ​

• 正向构建列表和反向构建列表，递归和迭代计算链表长度，根据索引获取值

public class IntList {
  public int first;
  public IntList rest;
  public IntList (int f, IntList r) {
    first = f;
    rest = r;
  }
}

SLLists ​

• 用 SSLists 实现对 IntNode 的封装

public class SLList {

  public IntNode first;

  public SLList (int x) {
    first = new IntNode(x, null);
  }
}

Sentinel Node ​

• 采用哨兵节点优化特判

public class SLList {

  /* the first item, if it exists, is at sentinal.next.*/
  public IntNode sentinel;

  public SLList (int x) {
    sentinel = new IntNode(-1, null);
    sentinel.next = new IntNode(x, null);
  }
}

Invariants ​

An invariant is condition that is guaranteed to be true during code execution (assuming there are no bugs in your code).

Invariants make it easier to reason about code:

• Can assume they are true to simplify code.
• Must ensure that methods preserve invariants.

DLLists ​

• 双向链表优化查找时间

Arrays vs. Classes ​

• Array indices can be computed at runtime.
• Class member variable names CANNOT be computed and used at runtime.

变量名在编译时被处理成内存地址，所以类成员变量名是无法在运行是计算并查找的

Testing ​

import org.junit.jupiter.api.Test;
public class SLListTest {
  @Test
  public void testSLList() {
    SLList L = new SLList(15);
    L.addFirst(10);
    L.addFirst(5);
    assertEquals(5, L.getFirst());
    assertEquals(10, L.size());
  }
}

Static Type vs. Dynamic Type ​

Every variable in Java has a "compile-time type", a.k.a. "static type"。

• This is the type specified at declaration. Never changes!

Variables also have a "run-time type", a.k.a. "dynamic type".

• This is the type specified at instantiation (e.g. when using new).
• Equal to the type of the object being pointed at.

Interface vs. Implementation Inheritance ​

Interface inheritance (a.k.a. what):

• Allow you to generalize code in powerful simple way.

Implementation inheritance (a.k.a. how):

• Allows code-reuse: Subclasses anc rely on superclasses or interfaces.
  • Example: print() implemented in List61B.java.
  • Gives another dimension of control to subclass designers: Can decide whether or not to override default implementation.

Important: In both case, we specify "is-a" relationship, not "has-a".

• Good: Dog implements Animal, SLList implements List61B.
• Bad: Cat implements Claw, Set implements SSList.

Dynamic Method Selection and Type Checking Puzzle ​

For each line of code, determine:

• Does that line cause a compilation error?
• Which method does dynamic method selection use?

• 编译时检查: 确保所有语法正确，并检查类型安全。
• 运行时检查: 动态方法选择根据对象的实际类型选择适当的方法实现。

Type Checking and Casting ​

• 编译器不关心如何实现，只关心静态类型是否匹配
• 慎用类型转换

Subtype Polymorphism ​

The biggest idea of the last couple of lectures: Subtype Polymorphism

• Polymorphism: "providing a single interface to entities of different types"

Consider a variable deque of static type Deque：

• When you call deque.addFirst(), the actual behavior is based on the dynamic type.
• Java automatically selects the right behavior using what is sometimes called "dynamic method selection".

Example:

public class Dog<T> implements Comparable<T> {

    public String name;
    public int size;

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    /* Dog barks. */
    public void bark() {
        System.out.println(name + " says: bark");
    }

    /* Compare two dogs based on their sizes. */
    @Override
    public int compareTo(T t) {
        return this.size - ((Dog) t).size;
    }

    /* Compare two dogs based on their names. */
    public static class NameComparator implements Comparator<Dog> {
        @Override
        public int compare(Dog d1, Dog d2) {
            return d1.name.compareTo(d2.name);
        }
    }
}

Summary ​

This course we built our own Array based Set implementation.

To make it more industrial strength we:

• Added an exception if a user tried to add null to the set.
  • There are other ways to deal with nulls. Our choice was arguably bad.
• Added support for "ugly" then "nice" iteration.
  • Ugly iteration: Creating a subclass with next and hasNext methods.
  • Nice iteration: Declaring that ArraySet implements Iterable.
• Added a toString method.
  • Beware of String concatenation.
• Added a equals method.
  • Used instanceof to check the class of the passed object.

Summary ​

• 程序运行时会进行两次检查：编译时检查和运行时检查，编译时检查主要检查语法和类型安全，运行时检查主要检查动态方法选择。
• 注意静态上下文中不能够使用泛型，泛型参数与类的实例相关联，而静态变量与方法与类相关联。
• access modifier（访问修饰符）: public, protected, default, private

Summary ​

• 介绍实现非交集连接的数据结构（并查集），并优化其查找和合并操作
• 加权并查集（按集合大小）的查找和合并操作的时间复杂度为 O(logN)

LLRB Tree ​

• LLRB 和 2-3 树具有相同的旋转操作；
• LLRB 将两个节点连接的情况视作一个红链接（虚拟节点）；
• 红链接总是向左倾斜；
• LLRB 最坏情况下的高度为 2-3 树的两倍。

A* ​

• A* 算法是一种启发式搜索算法，用于最快查找图中两个节点之间的最短路径（不一定正确）。
• 根据现有距离的大小施加惩罚，距离越小，惩罚越大。因为相较距离的大的点，距离小的点到达终点时需要查询的点更多。
• 如果想要避开某个顶点，可以将其惩罚值设置为最大，但是不一定能避开该顶点。

Cut Property ​

• 将顶点随机划分成两组，两组顶点集的连接边中的最短边必然是最小生成树中的边。
• 反证，任选一条连接边构成最小生成树，然而有更短的连接边存在，这怎么可能，所以矛盾。

Prim ​

• Prim 算法是一种贪心算法，用于查找图中的最小生成树。
• 从一个顶点开始，每次选择距离最近的顶点，直到所有顶点都被访问。
• 用 Cut Property 解释就是，一开始任选一个顶点为一组，然后每次选择距离该顶点集最近的顶点加入该组，直到所有顶点都被加入。

Topological Sort ​

• 查找最短路时，由于 Dijkstra 算法要求图中不存在环，所以需要对图进行拓扑排序。

Select Sort ​

Heapsort ​

• Naive Heapsort
• In-place Heapsort

Summary ​

• 采用比较方法的排序算法，其时间复杂度的期望值为 θ(NlogN)，无法找到更快的排序算法。
• 证明，通过决策树判断任意两点大小，一共产生 N! 种排序结果，查找时间复杂度为 Ω(logN!) = Ω(NlogN)。

Shannon Entropy ​

• Formal definition: E(-log(p(X))), where E is expected value and p(X) is the probability that X is a given value (averaged over all possible values of X).