1 Playing with Puppers

Suppose we have the Dog and Corgi classes which are a defined below with a few
methods but no implementation shown. (modified from Spring ’16, MT1)

1
2
3
4
5
6
7
8
9
10
11

1 public class Dog {
2       public void bark(Dog d) { /* Method A */ }
3 }
4
5 public class Corgi extends Dog {
6       public void bark(Corgi c) { /* Method B */ }
7       @Override
8       public void bark(Dog d) { /* Method C */ }
9       public void play(Dog d) { /* Method D */ }
10      public void play(Corgi c) { /* Method E */ }
11 }

1 Flatten

Write a method flatten that takes in a 2D array x and returns a 1D array that
contains all of the arrays in x concatenated together.
(Summer 2016 MT1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public static int[] flatten(int[][] x) {
    int totalLength = 0;

    for (int[] arr:x) {
        totalLength += arr.length;
    }

    int[] a = new int[totalLength];
    int aIndex = 0;

    for (int[] arr:x) {
        for(int i = 0; i < arr.length; i++) {
            a[aIndex] = arr[i];
            aIndex++;
        }
    }
     return a;
}
flatten({{1, 2, 3}, {}, {7, 8}}) // {1,2,3,7,8}

Introduction/Review of IntLists

As discussed in Monday’s lecture, an IntList is our CS61B implementation for a naked recursive linked list of integers. Each IntList has a first and rest variable. The first is the int element contained by the node, and the rest is the next chain in the list (another IntList!).

In the IntList directory for this lab, we’ve provided a much larger IntList.java than the one we created in class. It has five important new static methods, two of which you’ll fill in:

Creating Cats

1.1 Given the Animal class, fill in the definition of the Cat class so that when greet()
is called, the label “Cat” (instead of “Animal”) is printed to the screen. Assume
that a Cat will make a “Meow!” noise if the cat is 5 years or older and “MEOW!”
if the cat is less than 5 years old.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Animal {
    protected String name, noise;
    protected int age;

    public Animal(String name, int age) {
        this.name = name;
        this.age = age;
        this.noise = "Huh?";
    }

    public String makeNoise() {
        if (age < 5) {
            return noise.toUpperCase();
        } else {
            return noise;
        }
    }

    public void greet() {
        System.out.println("Animal " + name + " says: " + makeNoise());
    }
}
public class Cat extends Animal {
    public Cat(String name, int age) {
        super(name,age); // Call superclass's constructor
        this.noise = "Meow!"; // Change the noise field of this instance
    }
    public void greet() {
        System.out.println("Cat" + name + " says: " + makeNoise()); // Change label to Cat
    }
}

Q1 More Practice with Linked Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class SLList {
    private class IntNode {
        public int item;
        public IntNode next;
        public IntNode(int item, IntNode next) {
            this.item = item;
            this.next = next;
        }
    }

    private IntNode first;

    public void addFirst(int x) {
        first = new IntNode(x, first);
    }
}

1.1 Implement SLList.insert which takes in an integer x and inserts it at the given
position. If the position is after the end of the list, insert the new node at the end.
For example, if the SLList is 5 → 6 → 2, insert(10, 1) results in 5 → 10 → 6 → 2.

Q1

Implement fib which takes in an integer n and returns the nth Fibonacci number.
The Fibonacci sequence is 0,1,1,2,3,5,8,13,21,….

1
2
3
4
5
6
7

public static int fib(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Q1: Has Seven

Write a recursive function has_seven that takes a positive integer n and returns whether n contains the digit 7. Use recursion - the tests will fail if you use any assignment statements.

Lecture example

The order of recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def cascade(n):
    """
    >>> cascade(1234)
    1234
    123
    12
    1
    12
    123
    1234
    """
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n // 10)
        print(n)

Guerrilla Section 1: Functions, Control, Environment Diagrams

Functions

Question 0:
What will Python output?

1
2
3
4
5
6
7
8
9
10
11
12

>>> from operator import add, mul
>>> mul(add(5, 6), 8)
88
>>> print(‘x’)
x
>>> y = print(‘x’)
x
>>> print(y)
None
>>> print(add(4, 2), print(‘a’))
a
6 None

Q3: Lambdas and Currying

We can transform multiple-argument functions into a chain of single-argument, higher order functions by taking advantage of lambda expressions. This is useful when dealing with functions that take only single-argument functions. We will see some examples of these later on.