Assignment 1

Due Jan 27 on line

Part of the homework for CS:2820, Spring 2021
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Here is a recursive definition of a function defined over the non-negative integers designed to check your preparation for this course:
    f(i, j) = 0 when j = 0
    f(i, j) = i + f(i, j–1) otherwise

    What is this function?
    a) f(i, j) = i + j
    b) f(i, j) = i × j   –   the correct answer
    c) f(i, j) = i j
    d) f(i, j) = i ÷ j
    e) f(i, j) = i – j

  2. Another question to check your preparation: If a set has n elements, how many subsets of the set are possible?
    a) n2
    b) n!
    c) 2n   –   the correct answer
    d) log n
    e) n × (n – 1)

  3. Given a binary tree, if you recursively traverse the tree, processing each item in the tree after you process both subtrees, this is called:
    a) Pre-order traversal
    b) In-order traversal
    c) Post-order traversal   –   the correct answer
    d) Depth-first traversal
    e) Breadth-first traversal

  4. Suppose you have a set of items and a relationship between items that may be either present or absent. This can be modeled as a
    a) Digraph
    b) Graph   –   the correct answer (see below)
    c) Tree
    d) Linked list
    e) Doubly linked list

    Several students asked why not answer a) a digraph. The reason is that the phrase "a relationship between items" does not suggest directionality. Had the wording been "a relationship from one item to another" or had it been "the relationship can be either one way, the other way, or absent," then indeed, digraph would have been the best answer.

  5. Follow the instructions for obtaining a CLAS Linux account, and then use fastx to access that account, and open a shell window where you can execute the following shell command: 
         ~dwjones/2820log xxxx
    Where dwjones is Professor Jones's Hawkid because the 2820log command is one installed in his home directory, and xxxx is the section number of your discussion section. The 2820 command will tell you if it was successful and it will automatically log the fact that you completed this assignment. Repeating the exercise after you are successful is harmless but also pointless.

    Some students have had real difficulty with the command line in the past and needed significant help, so the discussion section Monday will be spent, in significant part, in walking you through this exercise.

    82 students successfully completed problem 5 by the deadline, as indicated by the contents of the log files.