NOTOC

Assignment 0: Representation of Information and C Self-Assessment

Assigned Thursday 9/6/2012
Question 0 Due Sunday 9/9/2012 at 11:59pm
Due Friday 9/14/2012 at 11:59pm

Instructions

Do Question 0 as soon as possible; it's just a simple survey.
Hand in your answers to the other questions either via code.seas.harvard.edu (instructions to follow next week), or via PDF email to cs61-staff@seas.harvard.edu, or via paper copy in class on Thursday 9/13.
Include your name and ID number in your submission.
Extension students, mention that you are extension students (remember that your due dates are 1 day later than those above).

0. Survey

(5 points) Please fill out the student demographic form. Please do this as soon as you can, and before Sunday night!

1. Base systems

(10 points) Fill out the following table by converting each mentioned number from the provided base system to the other two.

	Decimal	Binary	Hexadecimal
1.	2	__________	__________
2.	10	__________	__________
3.	16	__________	__________
4.	42	__________	__________
5.	4096	__________	__________
6.	__________	11₂	__________
7.	__________	101₂	__________
8.	__________	10101₂	__________
9.	__________	__________	0x13
10.	__________	__________	0x3F
11.	__________	__________	0xFFFFFFFF
12.	3735928559	__________	__________

2. Computer arithmetic

(20 points)

(a) Fill in the blanks so that the equations hold, using a different number for each blank except as noted. The equations use 32-bit unsigned computer arithmetic. This means that every value must be between 0 and 4294967295, inclusive.

(You will probably find this question easier to complete if you convert the numbers to hexadecimal or binary first.)


1.	__________	&	57	==	33
2.	__________	&	57	==	33
3.	__________	^	46	==	0
4.	__________	\|	~0	==	4294967295
5.	__________	-	100000	==	4294870310
6.	15	>>	__________	==	1
7.	__________	<<	__________	==	1024
8.	__________	+	~ __________	==	49
9.	(__________	&&	42139)	==	1
10.	(__________	==	42139)	==	1
11.	Use the same number for all three blanks: (It should differ from all your other answers)
	__________	+	~ __________	+	1

(b) Which of the above rows have unique well-defined solutions?¹

(c) Which of C's binary operators on unsigned integers (+, -, *, /, %, &, |, ^, ==, !=, <, >, <=, >=, <<, >>, &&, ||) are not associative, that is, do not obey the mathematical associative law?

3. Base –2 encoding

(20 points) The previous questions used bases 2, 10 and 16. Another possible encoding is to express the numbers in base –2. Representing numbers using a negative base works exactly the same as for a positive base: the kth column from the right represents multiples of b^k–1, where b is the base. For example, 1011 is the base –2 representation the number –9, since:


1 × (–2)³ + 0 × (–2)² + 1 × (–2)¹ + 1 × (–2)⁰
= –8 + 0 + –2 + 1
= –9.

(a) Write the base –2 representation for all integers from –8 to 8 inclusive.

(b) Suppose we use 2n bits to represent integers using base –2 encoding, for n > 0. What are the largest and smallest representable integers in this encoding?

4. C programming

(20 points)

(a) The following program should print out the binary representation of a given unsigned char variable. The printed binary value should be padded with leading 0s such that there are always 8 bits printed. Fill in the blanks in the program so that it functions as described.

void print_binary(unsigned char x) {
    int b = 128;

    while (__________________) {

        if (b <= x) {
            x -= b;
            printf("1");
        } else
            printf("0");

        ______________________;
    }
}

(b) Write another function, print_binary2, that performs the same function, but uses different logic. (This means that the function can't be a copy of print_binary with different variable names.)

5. Additional C self-assessment

This course requires programming in C. This question is intended to help you understand whether you know C well enough to be comfortable with the programming assignments that occur later in the course.

You do not need to submit your answers for this question. However, you are welcome to meet with course staff to discuss any difﬁculties you have with any of the questions.

If you can answer all of the questions conﬁdently, then you are likely to be fine with the C programming aspects of this course. If you are unsure of the answers to some of the questions, don’t panic: you may be alright in the course provided you spend time in the first few weeks learning C concepts, and practicing C programming. Feel free to contact course staff if you are unsure whether you are sufficiently prepared.

(a) What is the output of the following program?

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = 53;
    float *x = malloc(sizeof(float));
    *x = 5.9;
    n = n / (int) *x;
    printf("n = %d\n", n);
}

(b) What is the output of the following program, when run on a 32-bit x86 machine?

#include <stdio.h>

int main() {
    int x;
    printf("%d\n", sizeof(char) + sizeof(short) * sizeof(int) + sizeof(double) / sizeof(&x));
}

(c) The following program is intended to take an array of integers as an argument, along with the length of the array. Then, for each integer in the array, it prints ‘ZERO’ if the integer is 0, ‘ONE’ if the integer is 1, and ‘NONE’ if the integer is anything else. Each print statement is terminated with a newline. What is/are the mistakes?

void print_binray_array(const int *arr, int len) {
    for (int i = 1; i < len; ++i) {
        switch (*arr[i]) {
        case 0:
            printf("ZERO\n");
        case 1:
            printf("ONE\n");
        default:
            printf("NONE\n");
        }
    }
}

(d) Implement the function void underscoreize(char *dst, const char *src), which copies the string src into dst and in the process replaces all instances of the character ' ' (a space) with the character '_' (an underscore).

(e) Suppose we have a doubly linked list data structure, where nodes in the list are represented with the following structure:

struct node {
    int data;
    struct node *next;
    struct node *prev;
}

The prev field of the first element contains NULL, as does the next field of the last element.

Implement the function struct node *remove_nth(struct node *head, int n), which removes the nth element from the linked list that begins with the node head. The function should return the head pointer of the modified list, which often (but not always) equals the head argument. If n is invalid (What would that mean?) or out of range, return head without changing the list. Remember to 0-index, and remember that head might be NULL!

(f) Does the following function correctly return the ith Fibonacci number (so fib(0) == 1, fib(1) == 2, fib(2) == 3, fib(3) == 5, fib(4) == 8, fib(5) == 13, etc.), whenever the ith Fibonacci number is representable in an unsigned value? If not, fix it.

unsigned fib(unsigned a) {
    if (a <= 0)
        return 1;
    else
        return fib(a - 1) + fib(a - 2);
}

Extra-credit challenge

Find a media file online that contains runnable x86 code for sum.

Specifically, turn in a URL and an offset, so that the mysum-web program (which we distribute as part of the lecture notes code), when executed like this:

mysum-web URL OFFSET A B

will print (after some nonsense) "A+B=X". For instance, try this (after make):

kohler@ubuntu:~/cs61-lectures/l02$ ./mysum-web http://cs61.seas.harvard.edu/cs61wiki/skins/common/images/cs61hello.jpg 0x9f00 2 2
--2012-09-06 21:57:16--  http://cs61.seas.harvard.edu/cs61wiki/skins/common/images/cs61hello.jpg
Resolving cs61.seas.harvard.edu (cs61.seas.harvard.edu)... 140.247.173.30
Connecting to cs61.seas.harvard.edu (cs61.seas.harvard.edu)|140.247.173.30|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 69082 (67K) [image/jpeg]
Saving to: `STDOUT'

61% [======================>                ] 42,149       269K/s   in 0.2s


Cannot write to `-' (Broken pipe).
 00009f00 8b442408 03442404 c380ea5d fd80c653 c58ed1fe
2 + 2 = 4

Ground rules:

The cs61hello.jpg file doesn't count.
The media file must have been posted to the Internet unrelated to this class. (For instance, no files you modified by hand.)
The file must have a media-related MIME type (image or audio; PDF's OK too, why not).
The offset must point into a part of the file reserved for media (rather than a comment or metadata or anything similar).
The media must be displayable in a browser.

Ideas and notes:

Write or modify a web crawler and search images in parallel.
Use local computing resources or get some free time on Amazon EC2.
We aren't actually sure whether such a media file exists. We'd be most impressed by you finding an actual media file. But what creative, interesting systems could you build to “cheat” on the file, while strictly following the rules above?
Have fun!

This extra-credit challenge may be completed in groups and has no deadline.

Notes

Don’t invoke behavior that is undefined in C. In this problem, only #6 and #7 could invoke undefined behavior, if they shifted by too-large values. You should enter shift amounts between 0 and 31, inclusive. See the book's aside, “Shifting by k, for large values of k”, on p55 of CS:APP2e, for more. Undefined behavior is much more prevalent in signed arithmetic in C. ↩︎