Assignment 1, due Aug. 30

Solutions

Part of the homework for 22C:112, Fall 2013
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

  1. What is your E-mail address? (probably firstname-lastname@uiowa.edu, but this does not always work, for example, douglas-jones@uiowa.edu is not teaching this course.)

    No solution offered.

    Homework questions based on prerequisite material

  2. Background: The terms activation record and stack frame are synonyms.

    a) Typical Unix-like operating systems offer each running process 3 memory segments, the code segment, the static segment, and the stack segment. Which one holds that process's activation records? (0.2 points)

    The stack segment.

    b) When a Java or C++ or C# program is executed, what action, taken by the program, triggers the allocation of a new activation record? (0.2 points)

    A call (to a method or function)

    c) Programs have local variables and global variables, and in some languages, the latter may be declared as static (the default is dynamic). Which of these is typically part of the activation record? (0.2 points)

    Dynamic local variables.

    d) Activation records contain some of the variables mentioned above. What else do they typically contain (Hint, consider things that are there even if you don't mention them, see b above.) (0.2 points)

    The return address.

    e) What is the relationship between activation records and recursion? (0.2 points)

    Storing local variables in an activation record allows each recursively called instance of a routine to have distinct values for local variables even though they have the same name.

    (There are numerous ways to give a sensible answer to this question.)

  3. Background: Consider a non-empty circular doubly linked list, where a is a pointer to an item in the list (equivalently, a is the handle for an object in the list), where b may point to an item that is not part of the list referenced by a. Each item has fields named next and back that reference the successor and predecessor of that item.

    a) What simple comparison can you make to determine if the list referenced by a contains more than one item? (0.2 points)

    if (a->next != a) ...

    b) Assuming that the list contains more than one item, how many assignment statements, at minimum, are required to delete the successor of the item referenced by a from the list? (0.2 points)

    2 -- giving code was not required, but here is an example:

    a->next->next->back = a;
    a->next = a->next->next;
    

    c) How many assignment statements, at minimum, are required insert the single item referenced by b as the new successor of the item referenced by a in the list? (0.2 points)

    4 -- giving code was not required, but here is an example:

    a->next->next->back = b;
    b->next = a->next->next;
    a->next = b
    b->back = a
    

    d) Given that you know that the circularly linked list contains at least three elements, how many assignment statements, at minimum, are required to exchange the position of the element referenced by item a and its successor in the list. Note, after this is done, a still references the same element. (0.2 points)

    6 -- giving code was not required, but here is an example:

    a->back->next = a->next;
    a->next->next->back = a;
    a->next->back = a->back;
    a->back = a->next;
    a->next = a->next->next;
    a->back->next = a;
    

    e) The computation described in d) is fairly simple if an auxiliary variable such as b is used to keep track of the second item throughout the exchange. Can it be done without using any named auxilary variables (the compiler may, of course, use anonymous variables during expression evaluation). (0.2 points)

    See above. It takes at least 1 more assignment with a named auxiliary variable.

    Homework questions based on new material

  4. Background: Read the article by D.L. Parnas on the concept of transparency cited in lecture 1 (either the tech report or the CACM article -- they are substantially the same; access to the CACM article is free from any on campus computer).

    a) When Parnas refers to virtual machines in this work, he is referring to a concept with much broader applicaton than software. Give an example of an example virtual machine he uses that illustrates the broader applicability of this concept. (0.5 points)

    The steering linkage of a vehicle. The low level machine allows each wheel to be steered independently, while linkages in the higher-level control system coordinate the steering of the wheels -- forbidding unsafe configurations but also preventing some useful configurations.

    b) In what sense is a class library, in connection with a programming language such as C++ or Java, an example of a virtual machine? Is it opaque or transparent? (0.5 points)

    A class library extends the instruciton set of the underlying machine. To the extent that the class semantics of the language prevents access to the representation of a class instance except through methods of the class, there is some opacity, but class libraries do not block the programmer from creating classes with identical behavior to the library except without private components, and as such, class libraries are not opaque -- all configurations of the underlying machine remain reachable.