Homework 1 Solutions

22C:18, Fall 1996

1. Part A: Write, in legal Pascal, C or C++, the declarations necessary to create a doubly linked list data structure where each node contains a single character called ch.

   	struct listitem {
   		struct listitem * next, prev;
   		char c;
   	}
   

   Some students went on for pages about destructors, constructors, and methods without giving describing the data structure itself.

   Part B: Write, in legal Pascal, C or C++, the declarations of a function that will search the list described above; the function should take, as parameters, a character and a pointer to a doubly linked list, and it should return a pointer to the node in the list that contains that character, or a null pointer in the case that the character is not found in the list.

   struct listitem * search( struct listitem * list, char c)
   {
   	while (list != NULL) {
   		if (list->c == c) return list;
   		list = list->next;
   	}
   	return NULL
   }
   

2. Write, in legal Pascal, C or C++, function that takes, as parameters, a number base (an integer from 0 to 35) and the textual representation of a positive integer written in that base (a blank or null terminated character string) and returns that number as an integer. Obviously, the set of digits must be extended beyond the normal 0 to 9 to handle this! Use upper case letters as extended digits, so that the digit A has the value 10, the digit B has the value 11, etc.

   	int atoi( char * ptr, int base );
   	{
   		char * p = ptr;
   		int value = 0;
   		while (isxdigit(*p)) {
   			int digit;
   			if (isdigit(*p)) {
   				digit = *p - '0';
   			} else if (isupper(*p)) {
   				digit = *p - 'A' + 10;
   			} else {
   				digit = *p - 'a' + 10;
   			}
   			if (digit >= base) error();
   			value = value * base + digit;
   			p++;
   		}
   		return value;
   	}
   

   The above will work for bases up to 16 using the standard C function isxdigit, and if isxdigit is redefined as isalnum (true if isalpha or isdigit), it will work for bases up to 36.
3. Convert the following numbers to base 10:

   55₆ = 5x6 + 5 = 35
   555₆ = 5x36 + 5x6 + 5 = 215
   55₈ = 5x8 + 5 = 45
   555₈ = 5x64 + 5x8 + 5 = 365
   D00B₁₆ = 13x16³ + 11 = 53259
   1ED0₁₆ = 1x16³ + 14x16² + 13x16 + 0 = 7888
   IOWA₃₄
   = Ix34³ + Ox34² + Wx34 + A
   = 18x34³ + 24x34² + 32x34 + 10
   = 736314

4. 10 = 14₆ = 12₈ = A₁₆
   100 = 234₆ = 144₈ = 64₁₆
   1000 = 4344₆ = 1750₈ = 3D8₁₆

5. Convert the following string to ASCII, and show how it would be stored in consecutive words of memory by a Hawk system, starting at address #1000. Your answer should show the contents of each word of memory in hexadecimal.

   	The string is this!
   
           001000: 20656854
           001004: 69727473
           001008: 6920676E
           00100C: 68742073
           001010: xx217369
   

6. The Computer Control Corporation DDP-516 was one of the first minicomputers sold in the 1960's. This machine had word addressing only (no byte addresses!), a 16 bit word, and a 14 bit memory address. The character set used for textual I/O on this machine was 8 bit ASCII.

   Part A: How much memory can you attach to this machine, in words?

   14 bit memory addresses allow 2¹⁴ distinct addresses, and this allows addressing of 2¹⁴ different words of memory, or 16384 words.

   Part B: How many characters of text could you store in the memory of this machine?

   Each word is 16 bits, so 2 8-bit characters could be stored there. This gives a total memory capacity of 32768 characters.

7. On a Hawk machine, the 32 bit memory location 10₁₆ contains the value 76543210₁₆. Give, in hex, the contents of each 8 bit byte at locations 10₁₆, 11₁₆, 12₁₆ and 13₁₆.

   	10: 01
   	11: 32
   	12: 54
   	13: 76