Due Sunday, June 29, 2014 @ 11:59pm
Goals
This assignment covers a range of topics related to C and number representation. It is also intended to get you to start writing C code on your own.
Submission
Submit your solution by creating a directory named hw1 that contains files named hw1.txt,
maxstring.c, and Life1D.c.
(File names are case-sensitive and the submission program will not
accept your submission if your file names differ at all from those
specified.) From within that directory, type submit hw1. Partners are NOT allowed on any homework.
Copy the contents of ~cs61c/hw/01 to a suitable location in your home directory to obtain files you will want for this homework.
$ cp -r ~cs61c/hw/01 ~/hw1
Exercises
Problem 1: Number representation
Assume we are dealing with 8 bit numbers for this problem. Fill in the following table according to the header of each column. If you are given binary or hex, convert it to decimal. If you are given a decimal value, convert it to hex. Assume that we use a bias of 127. Put "n/a" if the value cannot be converted. Some example rows has been filled out for you.
| unsigned | sign & magnitude | one's complement | two's complement | biased notation | |
0b00000000 |
0 | +0 | +0 | 0 | -127 |
0b11111111 |
255 | -127 | -0 | -1 | 128 |
0b01111111 | |||||
0x90
| |||||
0xE5
| |||||
138
| |||||
128
| |||||
-128
|
Put your solution in hw1.txt.
Problem 2: Overflow
Assume we are using 4-bit numbers. List (in decimal) all 4-bit numbers that, when added to 0b0100, will cause:
- unsigned overflow
- signed overflow
Problem 3: IEC Conversion
Give your answer to the following problems using IEC prefixes where applicable.
- Simplify the following decimal number: 2147483648 cats
- If you were to divide a 128 ZiB hard drive into 512 TiB sections, how many sections are there?
- If we gave a 16-question, ABCD multiple-choice exam, how many answer combinations are possible?
- What if it had 42 questions?
- If we gave a 8 question, T/F exam every year for 8 years, how many overall answer combinations could there be?
Problem 4: C Coding
Part 1: Complete the implementation of maxstring.c, which returns the string with the maximum number of occurances of a specified character from an array of strings.
In case of a tie, the first string is returned. If the array is empty or if the character does not exist in any of the strings, an empty string is returned.
The skeleton code contains both maxstring() and charcount(), which is a helper function that maxstring() should call.
Note: Make sure you are returning an empty string and not NULL. You can specify an empty string as "" or "\0", but make sure to use double quotes.
Remember to run the completed program to verify correctness. To compile maxstring.c and create an executable named maxstring:
$ gcc -o maxstring -std=c99 maxstring.c
Part 2: Modify maxstring.c to take the specified character and the array of strings from command line arguments (see K&R Sec. 5.10).
You may assume that the arguments will be as follows, with the first argument being a single char and subsequent arguments being the strings to look through:
$ ./maxstring [char] [string 1] [string 2] ...
The following is an example of the output of the program. Single quotes (') are used to pass in arguments with spaces.
$ ./maxstring l 'hello world!' 'welcome to cs61c' hello world! $ ./maxstring ' ' 'hello world!' 'welcome to cs61c' welcome to cs61c $ ./maxstring l $ ./maxstring b 'hello world!' 'welcome to cs61c' $ ./maxstring [the same results as from part a]
Problem 5: Game of Life
For hw1, you will be implementing an elementary cellular automaton, also known as Life 1D. A cellular automaton is composed of an array of cells and a rule describing the transition from one generation of cells to the next. Cells can be alive or dead, and whether a cell is alive or dead in the next generation depends whether the five closest cells (including itself) is alive during the current generation. For example, here is an array of 7 cells:
Cells are shaded if they are alive, otherwise they are dead. Therefore, only the center cell in this array is alive. For our implementation,
each array will be of type char[], and each cell will contain 1 if it is alive and 0 if not. In the initial generation
only the center cell is alive, so this is also how the initial generation of a 7-cell Life 1D automaton will look like.
We produce the next generation of cells using a rule consisting of 32 bits, which we will store as an unsigned int. We visit each cell
in the array and use one of the bits in the rule to determine if the cell will be alive or dead in the next round. To do so, first we take the value
of the cell's two closest left neighbors, the cell itself, and the cell's two closest right neighbors as a 5-bit key. Cells outside the array are
considered dead, so visiting the second cell in the example above produces the key 0b00001. The value of the key, n,
will be a number between 0 and 31.
Note that there are 32 possible values for the keys and 32 bits in our rule. To determine the value of the cell in the next generation,
we will examine the n-th bit of the rule (counting from the least significant bit) to determine whether the cell will be alive in the
next generation. If the n-th bit of the rule is 1, the cell will be alive, and if it is 0, the cell will be dead.
Let's walk through a simulation of our 7-cell example with the rule 3141592653, which is equal to 0b10111011010000001110011001001101:
| Position | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Value | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
Starting with the same 7 cell array, we first look at the leftmost cell.
It's dead, as well as its four neighbors. This corresponds to 0b00000, which for rule 3141592653 is 1 (i.e. on, alive). This means that in
the corresponding cell for the array representing the next generation, it will be alive.
Repeat the process for the second cell from the left. This one is 0b00001, so in the next generation it will be dead.
What about the third cell?
We can see that this cell is dead as well as its left neighbors, but its immediate right neighbor is alive.
This corresponds to 0b00010, which for rule 3141592653 is 1 (i.e. on, alive). Therefore, the third
cell of the next generation will also be alive.
The fourth cell corresponds to 0b00100, which is dead. We can repeat this process for the remaining cells to produce the
following next generation array.
By repeatedly applying this generation process and putting each new generation below the previous one, we can produce a pattern.
You will be completing a C program, Life1D.c to do this for any rule and number of rows. The program takes exactly two integer arguments:
$ ./Life1D [rows] [rule]
rows refers to the number of rows (after the initial generation) you will generate.
The number of cells in the array also depends on rows; there will be (2*rows+1) cells, which guarantees
that the number of cells is odd (so there will always be a center). rule is the rule to use, which will be stored as an unsigned int.
A skeleton has been provided for you in Life1D.c, which handles argument checking and memory management for you. Your task is to create the initial
generation, print it (see Output Format section for format), and then simulate and print rows more generations. Therefore, each run of
Life1D.c with n rows will print out a table that is n+1 high and 2*n+1 wide. Two char arrays
containing all 0s, row1 and row2, are available for you to use. Feel free to declare additional variables or functions when completing
the assignment.
Note that the skeleton code allocates space for 2*n+5 chars. Since checking cells on the border of each row requires examining cells outside the array,
one solution is to pad the array with 0s on either side so that we don't have to deal with edge cases. The actual portion of interest would then begin on the 3rd
char and end on the 2*n+3 char. You may choose to use the padding or any other methods you come up with.
Examples:
$ ./Life1D 3 58979
P1 7 4 ## 3 rows of Life1D (Rule 58979)
0 0 0 1 0 0 0
1 1 0 0 0 0 1
1 0 0 0 1 0 0
0 0 0 0 0 0 0
$ ./Life1D 5 32384626
P1 11 6 ## 5 rows of Life1D (Rule 32384626)
0 0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
$ ./Life1D 4 4338327
P1 9 5 ## 4 rows of Life1D (Rule 4338327)
0 0 0 0 1 0 0 0 0
1 1 1 1 1 0 0 1 1
1 0 0 0 0 0 0 0 1
1 0 0 1 1 1 1 1 1
1 1 0 1 0 0 0 0 0
$ ./Life1D 17 3141592653
P1 35 18 ## 17 rows of Life1D (Rule 3141592653)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0
0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 0
1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1
0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0
1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1
0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0
1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0
0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0
1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0
0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1
1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0
0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0
1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0
0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1
1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0
Output Format:
In order for the provided scripts to work properly your output format must follow these guidelines:
- Do not have any extraneous whitespace characters at the end of the row. Meaning, each row print out ends with "0\n" or "1\n", not "0 \n" or "1 \n".
- All rows end with a newline character. Meaning, after your program exits, the UNIX prompt starts on a new line and not on the same line as your last row.
- You must have spaces in between your columns (just like you see in the examples above) when you print out a row. Meaning, this is invalid (no spaces between columns):
000010000 000010100 000010010
and this is valid:0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0
Test your code!
Make sure your code compiles on the hive machines with the command:
$ gcc -o Life1D -std=c99 Life1D.c
Test your code to see if they generate the examples above, then try a few rules of your own and verify that they're correct for a few rows.
(If they are, then there's little reason to be wrong when producing more rows).You can generate a gif image by piping the output
into ppmtogif and redirecting the output to a file, and we have included a script, scale.sh,
that will help format the image. An example usage would be:
$ ./Life1D 3 58979 | ./scale.sh 10 | ppmtogif > Life1D_3_58979.gif
You may also run the compile file, which will compile your file and run several tests. Here are the gifs resulting from the examples above:
 Life1D 3 58979 |  Life1D 5 32384626 |  Life1D 4 4338327 |  Life1D 17 3141592653 |