Homework 1

Due Friday, Sep 14, 2018 at 8pm

A PDF version of this document is located here.

Use the following commands to download and unpack the distribution code:

$ wget https://eecs490.github.io/homework/hw1/starter-files.tar.gz
$ tar xzf starter-files.tar.gz
  1. Python practice. Implement a simulation of Conway's Game of Life in Python3. While the original simulation is on an infinite grid, your implementation should be on a finite grid. Edge cells have fewer neighbors but should otherwise follow the same rules as any other cell.

    Place your code in a file named life.py. Your simulation must have the following interface:

    def simulate(rows, cols, steps, live_cells):
        """Run Conway's Game of Life on a finite (rows x cols) grid.
    
        Runs the simulation for the number of time steps specified by
        the steps parameter. Initializes the grid such that all cells
        are dead except those listed in live_cells, which should be a
        sequence of (row, column) pairs. Prints the grid after each
        time step.
        """
        ...
    

    When printing the grid, you should first print a line consisting of cols + 2 dashes (-). Each row should then start and end with a pipe (|), each live cell should be printed as an asterisk (*), and each dead cell should be printed as a space. Finally, print another line consisting of cols + 2 dashes followed by another empty line.

    We have provided a test case in life_test.py and the expected output in life_test.correct.

    You may use the NumPy library if you wish.

    Hint: It is possible to implement the algorithm without special cases for the borders. Think about storing the data in a \((rows+2) \times (cols+2)\) grid rather than in a \(rows \times cols\) grid.

  2. Python classes and special methods. Read through the section in the Python reference on special methods, particularly the subsections on basic customization and emulating container types. Also read the section in the reference on iterators. Then complete the definition of the Range class, which is a simplified version of Python's built-in range type, in range.py.

    The Range class is a container representing a fixed sequence of integers. It has the following methods:

    • __init__: The constructor, which takes in the start, stop, and optional step. If the step is not given, it defaults to 1. We will only handle the case where the step is a positive integer.
    • __iter__: Returns an iterator over the range, represented as a RangeIter object.
    • __len__: Returns the number of integers in the range.
    • __contains__: Returns whether or not the given integer is a member of the range.

    The RangeIter class implements the iterator interface and is used for iterating over a Range.

    Once you have completed both classes, you can run the tests in the test() function from the command line:

    $ python3 range.py
    
  3. Literals and operators. Implement a BitVector type in C++17, representing a growable sequence of booleans. Your BitVector must support the following operations:

    • String literals that end with the _bv suffix construct a BitVector from the string with bits in order from left to right. A 0 character specifies false and a 1 character specifies true. Example:

      "1010"_bv  -->  [ true, false, true, false ]
      
    • The size() member function returns the size of the BitVector. The return type should be size_t.

    • The push_back() member function takes in a bool and appends it to the end of the BitVector.

    • The [] operator returns the boolean at the given position. You may return by value or reference (i.e. you do not have to support modifying a BitVector using the [] operator).

    • The bitwise operators &, |, and ^, when applied to two BitVectors, should result in a BitVector that consists of the AND, OR, and XOR of the two BitVectors, respectively. If they differ in size, then the operators should treat the smaller as if it were padded on the right with zeros.

    • The << stream insertion operator when applied to a BitVector should insert each boolean as a 0 or 1. Example:

      cout << "1010"_bv;  -->  prints 1010
      

    Write your code in BitVector.h. We have provided a test case in BitVector_test.cpp and expected output in BitVector_test.correct.

    You may use any standard libraries you like.

  4. Scope. For each of the following snippets of C++17 code, determine what value is printed when the code is executed. If the result is indeterminate according the the C++17 standard, write "undefined". If the code should result in a compilation error, write "error". For each case, write a brief (1-2 sentence) explanation of why the resulting value is printed or is undefined, or why the code is erroneous.

    a) int main() {
         int x = 3;
         {
           int y = x;
           int x = 4;
           cout << x + y;
         }
       }
    
    b) int main() {
         int x = 3;
         {
           int y = x, x;
           cout << x;
         }
       }
    
    c) int main() {
         int x = 3;
         {
           int y = x, x;
           cout << y;
         }
       }
    
    d) int main() {
         int x = 3;
         {
           int y = x, x = y;
           cout << x + y;
         }
       }
    
    e) int main() {
         int x = 3;
         {
           int x = x;
           cout << x;
         }
       }
    
    f) using x = int;
    
       int main() {
         x x = 3;
         cout << x;
       }
    
    g) using x = int;
    
       int main() {
         x x = x;
         cout << x;
       }
    
    h) using x = int;
    
       int main() {
         x x = 3, y = x;
         cout << x + y;
       }
    
    i) using x = int;
    
       int main() {
         x x = 3;
         x y = x;
         cout << x + y;
       }
    

Submission

Place your answer to question 4 in a PDF file named hw1.pdf. Make sure to list any other students with whom you discussed the homework, as per course policy in the syllabus. Submit life.py, range.py and BitVector.h to the autograder before the deadline. Submit hw1.pdf to Gradescope before the deadline.