Computer Science 111: Computers and Computing Spring 1997

General Information Labs Problem Sets Course newsgroup Links What's New?

Problem Sets

Problem Set 10

From the Brookshear text: Chapter Ten Review Problem 19 (p. 392), Chapter Eleven Review Problems 8 and 10 (p. 427). For the Turing Machine problem, you may use the design style of the text (e.g., Figure 11.4) or the graphical style we've used in class (which is usually easier).

extra credit: Of all the computer programs that ever were or ever could be, some of them print your name. Can there exist an algorithm which will, given some arbitrary program P as its input, always correctly tell whether or not P ever prints your name? Why or why not?

Problem Set 9

not from the Brookshear text: Design linked tree structures that can represent the genealogical history of a family. Do two different designs: one that represents all of the ancestors (back some small number of generations) of an individual (e.g., the ancestors of Prince Charles), and one that represents all the decendants of an individual (e.g., all of Queen Victoria's descendants). For each design, specify what links you would store with each node, in addition to the name of the individual.

extra credit: The first genealogical tree is pretty clearly binary. Come up with a way to make the second one into a binary tree that represents the same information (all the descendants).

Chapter Ten Review Problem 14 (pp. 391-392)

Problem Set 8

From the Brookshear text: Chapter Seven Review Problems 7, 8, 11, 14, 18, 21 (pp. 297-298)

Problem Set 7

From the Brookshear text: Chapter Four Review Problems 33 and 39 (p. 180); Chapter Five Review Problems 2, 18, 21 (pp. 227-8). When you are asked for a program in the machine language of Appendix C, feel free to use instead the somewhat richer assembly language we used in class, which is described in Rege Colwell's note.

Problem Set 6

From the Brookshear text: Chapter Four Review Problems 6, 7, 14, 21, 27, 30, 41 (pp. 177-180)

extra credit: Problem 42

Problem Set 5

From the Brookshear text: Chapter Three Review Problems 5, 7, 9, 17, 34, 37 (pp. 126-8)

extra credit: Problem 39

GRADING NOTE: as an aid to midterm studying, this problem set will be graded and returned Tuesday evening. We'll move the return box down to the ledge outside the classroom for the evening. Your grader will be happy if you can turn in your problem set earlier in the day.

Problem Set 4

GCD problem (Tuesday lab people: if you do this before your lab session, the lab will probably be easier):

• What is the greatest common divisor of 36 and 28? How did you figure it out?
• Show how you would use the algorithm on page 3 of the Brookshear text (Euclid's algorithm) to solve the same problem. Show the values of M, N, and R at each step.

From the Brookshear text: Chapter Two Review Problems 17, 27a, 27b, 36, 39 (pp. 85-87). When you are asked for a program in the machine language of Appendix C, feel free to use instead the somewhat richer assembly language we have been using in class, which is described in Rege Colwell's note.

Problem Set 3

From the Brookshear text: Chapter Two Review Problems 3, 8, 9, 11, 15a, 15b (pp. 84-5)

extra credit: Problem 15c

Problem Set 2

From the Brookshear text: Chapter One Review Problems 23, 24, 31, 37, 38, 48, 51 (pp. 53-5)

extra credit: What lesson could you draw from your answer to question 48?

Problem Set 1

From the Brookshear text: Chapter One Review Problems 1, 2, 3, 4, 5, 8, 11 (pp. 52-3)

From the Turing Omnibus: Chapter 13, problem 4 (p. 89)

extra credit: Omnibus Chapter 28, problem 1 (p. 191) or Chaper 56, problem 1 (p. 373)