Assignment 1 solutions

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

  1. What is your E-mail address?

    Survey Questions

  2. What high level programming languages have you used to write even small programs?

  3. What high level programming languages have you used to write programs that you considered large?

  4. Have you previously used Unix or Linux systems?

  5. What machine architectures or assembly languages have you studied?

    Real Homework!

  6. This quesiton is one you should be able to answer based entirely on courses that are prerequisites to this course: Given a complete binary tree with n leaves, how many edges does it have?

    A complete binary tree with n leaves has n-1 internal nodes for a total of 2n-1 nodes. Every node but the root has an edge leading to it, so we have 2n-2 edges.

  7. This quesiton is one you should be able to answer based entirely on courses that are prerequisites to this course: Given an array of n items, where each item consists of a pair of integers and a fixed size character string of k ASCII characters, what is the minimum memory required to hold this data, in bytes, on a typical modern 32-bit machine?

    A pair of integers would require 2 32-bit words, or 8 bytes. A string of k ASCII characters would require k bytes, so we can say, naively, that the storage for n items of this kind will be n(k+8) bytes.

    But, many compilers will round up to the nearest word, so we actually use 4(ciel(k/4)) bytes for the string, where ciel(x) is the nearest integer greater than or equal to x. This means the actual requirement will be more likely to be n(4ciel(k/4)+8) bytes.

  8. Explain, in a very few sentences, the meaning of the term fetch-execute cycle.

    The steriotypical CPU operates by repeatedly fetching an instruction from memory and then executing it. This is called the fetch-execute cycle.