University of California at Berkeley
College of Engineering
Department of Electrical Engineering and Computer Science

CS 61C, Summer 2010

HW 1

Due Friday, June 25, 2010 @ 11:59pm

Last updated Wednesday, Jun. 23, 2010 @ 2:00pm


This assignment checks your understanding of the material in P&H Chapter 1 as well as some number representation basics. It will also give you practice compiling and executing C programs.

Background reading

Submitting Your Solution

Submit your solution by creating a directory named hw1 that contains files named cod.txt and majorbit.c. (Note that capitalization matters in file names; 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 this assignment.

Problem 0

Copy the contents of ~cs61c/hw/01 to a suitable location in your home directory (create cod.txt yourself).
  $ mkdir ~/hw
  $ cp -r ~cs61c/hw/01/ ~/hw
All the files referred in this homework will be in the folder you copied.

Problem 1

In cod.txt, answer the following questions:

P&H (4th) problems 1.1.1-1.1.26 (these are very short questions), reproduced below:

Find the word or phrase from the list below that best matches the description in the following questions. Use the numbers to the left of the words in the answer. Each answer should be used only once.

1. virtual worlds 14. operating system
2. desktop computers 15. compiler
3. servers 16. bit
4. low-end servers 17. instruction
5. supercomputers 18. assembly language
6. terabyte 19. machine language
7. petabyte 20. C
8. datacenters 21. assembler
9. embedded computers 22. high-level language
10. multicore processors 23. system software
11. VHDL 24. application software
12. RAM 25. cobol
13. CPU 26. fortran
  1. Computer used to run large problems and usually accessed via a network.
  2. 10^15 or 2^50 bytes.
  3. Computer composed of hundreds to thousands of processors and terabytes of memory.
  4. Today's science fiction application that probably will be available in the near future.
  5. A kind of memory called random access memory.
  6. Part of a computer called central processor unit.
  7. Thousands of processors forming a large cluster.
  8. A microprocessor containing several processors in the same chip.
  9. Desktop computer without screen or keyboard usually accessed via a network.
  10. Currently the largest class of computer that runs one application or one set of related applications.
  11. Special language used to describe hardware components.
  12. Personal computer delivering good performance to single users at low cost.
  13. Program that translates statements in high-level language to assembly language.
  14. Program that translates symbolic instructions to binary instructions.
  15. High-level language for business data processing.
  16. Binary language that the processor can understand.
  17. Commands that the processors understand.
  18. High-level language for scientific computation.
  19. Symbolic representation of machine instructions.
  20. Interface between user's program and hardware providing a variety of services and supervision functions.
  21. Software/programs developed by the users.
  22. Binary digit (value 0 or 1).
  23. Software layer between the application software and the hardware that includes the operating system and the compilers.
  24. High-level language used to write application and system software.
  25. Portable language composed of words and algebraic expressions that must be translated into assembly language before run in a computer.
  26. 10^12 or 2^40 bytes.

P&H (4th) problems 1.2.4:

Assuming that a cache memory is ten times faster than a DRAM memory, that DRAM is 100,000 times faster than magnetic disk, and that flash memory is 1000 times faster than disk, find how long it takes to read a file from a DRAM, a disk, and a flash memory if it takes 2 microseconds from the cache memory?

P&H (4th) problems 2.7.1, 2.7.2, 2.7.5:

The following problems explore number conversions from signed and unsigned binary number to decimal numbers.

a. 0b 1010 1101 0001 0000 0000 0000 0000 0010
b. 0b 1111 1111 1111 1111 1011 0011 0101 0011

2.7.1. For the patterns above, what base 10 number does it represent, assuming that it is a two's complement integer?

2.7.2. For the patterns above, what base 10 number does it represent, assuming that it is an unsigned integer?

a. 2147483647
b. 1000

2.7.5. For the base ten numbers above, convert to two's complement hexadecimal.

Problem 2

What are the decimal values of each of the following binary numbers if you interpret them as 2's complement integers? Add your answers in cod.txt.

Problem 3

What are the decimal values of each of the following hexadecimal numbers if you interpret them as unsigned integers? Add your answers to cod.txt.

Problem 4

For each of the bit lengths and number representations below, list the binary encodings and values of the possible numbers closest to +infinity and to -infinity. (For each of the four parts to this question, you will provide two binary strings and two corresponding decimal numbers.) Add your answers to cod.txt

Problem 5

Write a function named majorBit() in majorbit.c that returns the bit that appears the most in the binary representation of its unsigned integer argument. For example, for the number 5 (101 in binary), the function will return 1 since 1 appears 2 times whereas 0 only appear 1 time. Similarly, for the number 4 (100 in binary) the function will return 0. If there is a tie the program should return 2. Remember to fill in the identification information and run the completed program to verify correctness.
    Lab section time:

  #include <stdio.h>

  int majorBit (unsigned int n);

  int main ( )
    printf ("# majority bit in base 2 representation of %u = %d, should be 0\n",
      0, majorBit (0));
    printf ("# majority bit in base 2 representation of %u = %d, should be 1\n",
      1, majorBit (1));
    printf ("# majority bit in base 2 representation of %u = %d, should be 2\n",
      2863311530u, majorBit (2863311530u));
    printf ("# majority bit in base 2 representation of %u = %d, should be 0\n",
      536870912, majorBit (536870912));
    printf ("# majority bit in base 2 representation of %u = %d, should be 1\n",
      4294967295u, majorBit (4294967295u));
    return 0;

  int majorBit (unsigned int n)
    /* your code here */

Problem 6

You have decided that you want your majorbit program above to work from the command-line (see K&R Sec. 5.10), as follows:
  # ./majorbit 17
  # ./majorbit 255
  # ./majorbit 10 20
  too many arguments!
  # ./majorbit
  [the same result as from problem 5]
You may assume that the single argument will always be an integer in the range from 0 to 2^31-1. You will find the function atoi helpful.

Extra for experts: Implement this exercise without using the library function atoi (or something comparable).