Assignment 1 Solutions

Part of the homework for 22C:50, Spring 2003
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. What is your E-mail address?
  2. What programming languages have you used to write even small programs?
  3. What programming languages have you used to write programs that you considered large?
  4. What text editors have you used to develop programs?
  5. What machine architectures have you studied -- at the level of the machine's assembly language or instruction set.
    no solutions offered to the above!

    Questions covering Prerequisites for the Course

  6. A binary tree has n internal nodes. How many leaves does it have?
    A complete binary tree has n+1 leaves, always, without exception. (Complete binary trees have no null pointers). If the tree might be incomplete, it has at most n+1 leaves, or alternately, the sum of leaves and null pointers is n+1.

  7. A binary search tree contains n items. Each item contains a pair of integers plus the minimum number of pointers required to construct the tree. What is the minimum amount of memory that must be allocated for the tree? State any assumptions you had to make in reaching your answer!
    For each item, we need space for two pointers, plus two integers. On most modern machines, an integer is 4 bytes and a pointer is 4 bytes, so we need 8 bytes per item. With n items, we therefore need n+1 bytes of memory.

  8. Given that:

    a) What is the address of p?

    ap

    b) What is the value of p?

    ao

  9. What is indirect addressing?
    Indirect addressing takes the value that might otherwise be used as an operand and uses it as a pointer to the operand. For example, register-indirect addressing uses the contents of a register as a pointer, where normal register addressing directly uses the contents of that register.

  10. What is indexed addressing?
    In its most elementary form, indexed addressing involves taking the sum of the contents of an index register with a displacement to compute the address of the operand.