Object Oriented Programming

Q1: Next Fibonacci Object

Implement the next method of the Fib class. For this class, the value attribute is a Fibonacci number. The next method returns a Fib instance whose value is the next Fibonacci number. The next method should take only constant time.

Note that in the doctests, nothing is being printed out. Rather, each call to .next() returns a Fib instance, which is represented in the interpreter as the value of that instance (see the __repr__ method).

Hint: Keep track of the previous number by setting a new instance attribute inside next.

OOP

We now want to write three different classes, Mailman, Client, and Email to simulate email. Fill in the definitions below to finish the implementation! There are more methods to fill out on the next page.

Lab Check-Off

Q1: To Tree or Not to Tree

Sign up for checkoffs in your lab if you’d like to get credit for this week’s checkoff.
Say you have some function defined as follows:

1
2
3
4
5
6

>>> def sum_tree(t):
...     """Computes the sum of all the nodes in a tree"""
...     if is_leaf(t):
...         return t
...     else:
...         return t + sum([sum_tree(b) for b in branches(t)])

Trees

Q1: Replace Leaf

Define replace_leaf, which takes a tree t, a value old, and a value new. replace_leaf returns a new tree that’s the same as t except that every leaf value equal to old has been replaced with new.

Goals

The objective of this assignment is to get you familiar with string/pointer manipulation and C code. You’ll also likely get lots of good experience debugging with cgdb (or enhance your ability to use print statements).

Background

grep is a UNIX utility that is used to search for patterns in text files. It’s a powerful and versatile tool, and in this assignment you will implement a version that, while simplified, should still be useful.

Your assignment is to complete the implementation of rgrep, our simplified version of grep. rgrep is “restricted” in the sense that the patterns it matches only support a few regular operators (the easier ones). The way rgrep is used is that a pattern is specified on the command line. rgrep then reads lines from its standard input and prints them out on its standard output if and only if the pattern “matches” the line or some subsection of it. For example, we can use rgrep to search for lines that contain filenames that are at least 3 characters long (plus the “.txt”) as follows:

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

# show the contents of test_file.in:
$ cat test_file.in

fine.txt
reallylong.txt
abc.txt
s.txt
nope.pdf

$ ./rgrep '...+\.txt' < test_file.in

fine.txt
reallylong.txt
abc.txt

What’s going on here? rgrep was given the pattern “…+.txt”; it printed only the lines from its standard input (the contents of test_file.in) that matched this pattern. How can you tell if a line matches the pattern? A line matches a pattern iff the pattern “appears” somewhere inside the line. In the absence of any special operators, seeing if a line matches a pattern reduces to seeing if the pattern occurs as a substring anywhere in the line. So for most characters, their meaning in a pattern is just to match themselves in the target string. However, there are a few special clauses you must implement:

So, here are some examples of patterns and the kind of lines they match:

These are the only special characters you have to handle. With the exception of the null character that terminates a string, you should not have to handle other characters in any special way. You may assume that your code will not be run against patterns that don’t make sense.

Exercise 1: Bit Operations

For this exercise, you will complete bit_ops.c by implementing the following three bit manipulation functions. You will want to use bitwise operations such as and (&), or (|), xor (^), not (~), left shifts (<<), and right shifts (>>). Avoid using any loops or conditional statements.

Q1 C Memory Management

In which memory sections (CODE, STATIC, HEAP, STACK) do the following reside?

1
2
3
4
5
6
7

#define C 2
const int val = 16;
char arr[] = "foo";
void foo(int arg){
    char *str = (char *) malloc (C*val);
    char *ptr = arr;
}

• arg resides in STACK, str resides in STACK
• arr resides in STATIC, *str resides in HEAP
• val resides in CODE, C resides CODE

What is wrong with the C code below?

1
2
3

int* ptr = malloc(4 * sizeof(int));
if(extra_large) ptr = malloc(10 * sizeof(int));
return ptr;

Introduction

In this homework, you will learn how to write and use packages, as well as get some hands-on practice with interfaces and abstract classes. We’ll also get an opportunity to implement a simple data structure as well as an algorithm that’s easy to implement using that data structure. Finally, we’ll add support for iteration and exceptions (which we’ll cover on Friday) to our data structure.

1 Exceptions (Spring 2016 MT2 Q3)

Consider the code below. Recall that x / 2 rounds down to the nearest integer.

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

public static void checkIfZero(int x) throws Exception {
    if (x == 0) {
        throw new Exception("x was zero!");
    }
    System.out.println(x); // PRINT STATEMENT
}
public static int mystery(int x) {
    int counter = 0;
    try {
        while (true) {
            x = x / 2;
            checkIfZero(x);
        counter += 1;
        System.out.println("counter is " + counter); // PRINT STATEMENT
    }
    } catch(Exception e) {
        return counter;
    }
}
public static void main(String[] args) {
    System.out.println("mystery of 1 is " + mystery(1));
    System.out.println("mystery of 6 is " + mystery(6));
}

What will be the output when main is run?

1 Immutable Rocks

Access control allows us to restrict the use of fields, methods, and classes.

• public: Accessible by everyone.
• protected: Accessible by the class itself, the package, and any subclasses.
• default (no modifier): Accessible by the class itself and the package.
• private: Accessible only by the class itself.
  Read more »