Assignment 1, Solved

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

  1. What is your E-mail address?

    No solution available

    Survey Questions

  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.

    Questions covering Prerequisites for the Course

  6. A complete binary tree has n leaves. How many internal nodes does it have? If you've completed 22C:34, you should be able to answer this.

    n - 1

    In a complete binary tree, each node has either no children (a leaf) or two children (an internal node). The basis case is a root with two leaves, that is, 1 internal node and 2 leaves. For our induction step, note that any leaf of a tree can be replaced with an internal node that has two leaves. In doing this, we added 1 leaf and 1 internal node, preserving the difference of one. Any complete binary possible tree can be built by a sequence of these induction steps starting from the basis case.

  7. If a machine has 1 gigabyte of main memory, how many bits are required, at minimum, to hold a pointer. If you've completed 22C:40, you should be able to answer this.

    30 bits

    1 gigabyte is 1,000,000,000 bytes or 10003 bytes.
    210 is 1024. 230 = (210)3.
    Since 1024 > 1000, 230 bytes > 1 gigabyte.
    Therefore, a 30 bit address will suffice to address one gigabyte of RAM.

  8. At minimum, a node in a binary search tree needs only two pointers, one to the left child and one to the right. Sometimes, a third pointer is added, to the parent. What are some of the additional tree operations that you can do if you have this extra link? If you've completed 22C:30, you should be able to answer this.

    With an uplink added to each node, it becomes possible to find the parent of that node when given a pointer to the node. This, in turn, allows deletion of an arbitrary node without first searching for that node from the root. Uplinks also allow, with some tricky code, traversal of a binary search tree without the use of a stack.

  9. What is the difference between indirect-indexed addressing and indexed-indirect addressing? If you've completed 22C:40, you should be able to take a stab at this, even if the machine you studied didn't use these terms.

    Indirect addressing involves following pointers. Indexed addressing involves addressing an element of an array using a base and a displacement. Therefore, indirect indexed addressing or indexed indirect addressing involve both indexing into an array and following a pointer. One of these must follow a pointer to an array and then select an element. The other must select an element of the array and use it as a pointer. Which is which? Fortunately, that wasn't the question, because it's not clear that there is a consensus about that!