Assignment 1, due Jan 28

Part of the homework for 22C:60, Spring 2005
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated, and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

  1. What is your E-mail address? (If you have more than one, give the address you'd prefer used for class purposes.)

    Real Homework!

  2. To test your preparation for this course:

    a) Given a set S of n distinct items, how many distinct subsets of S are there, including the empty set and also including S itself.

    b) Given an array A containing n items sorted in ascending order, how many array elements must be examined in order to determine if one of the array elements contains the integer value i? Assume a binary search algorithm, and identify the worst case.

  3. Show the representation of the string "SHORT STRING" in the antique ILLIAC character set from Chapter 2 of the notes. Note that the initial state of the printer is unknown; it could be in L/S or F/S state, so your message must begin by selecting the correct shift code. Show your answer in the same visual notation as was used by the Illiac Minature Manual.

  4. Do exercise k) from Chapter 2 of the notes two times. (Note that this means the probability of any two students in the class converting the same numbers is extremely small.)

  5. Write code, in the programming language of your choice, that takes an integer and a number base as parameters and returns a character string that represents that integer in that number base, using whatever string representation is most convenient the programming language you have selected. You may not use any built-in conversion methods that do this for you, and your program must work for any number base from 2 to 36! For digits greater than 9, use consecutive letters starting with A; this means that Z, if used as a digit, has the value 35. (Your solution will almost surely be smaller than this paragraph.)

  6. Do exercise v) from Chapter 2 of the notes two times.