Assignment 1, due Aug. 30

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.)

    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)

    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)

    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)

    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)

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

  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)

    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)

    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)

    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)

    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)

    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)

    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)

 

Machine Problem I

Due Monday, Sep. 9

Here is a little C program to copy arbitrary files from standard input to standard output:

/* MP1 by --------- for 22C:112 */
#include <stdio.h>
int main() {
        int ch;
        while ((ch = getchar()) != EOF) {
                putchar(ch);
        }
}

Modify this program so that it the header comment has your name instead of the dashes shown in the code above.

And, modify it so that it deletes control characters other than newline and tab ('\n' and '\t' in C) from the input. Note that in ASCII (and UTF-8), all characters less than space are control characters. If you carelessly upload a text file in DOS format from a Windows system, your program will actually be useful -- it will strip out all of the extraneous carriage returns from the DOS line endings.

All of your code should conform, as much as is possible, to the manual of style:

-- http://www.cs.uiowa.edu/~jones/syssoft/style.html

The purpose of this assignment is to get you to use the departmental Linux servers, some text editor, and the C compiler. Your solution must be in a file named mp1.c (all lower case). Submit your solution using the coursework submission tools documented at:

-- http://www.divms.uiowa.edu/help/msstart/submit.html

In short, you will type the shell command submit, with no arguments, and when it prompts for a file name, you will type mp1.c, and then an extra carriage return to indicate that there is only one file in your submission. When it prompts for a course, type c_112 and finally, when it prompts for an assignment directory, enter mp1.