Assignment #1

Theme: Some of Knuth's creations and a programming problem.

Assigned:September 10, 2015.

Due: September 18, 2015. Assignments are to be turned in at the beginning of class on the due date. Sometimes solutions will be discussed in that class. Turn in a paper copy of your assignment.

• Produce a TeX or LaTeX document that produces, as closely as you can, page 51 of the text. Turn in both your source and the output. This is the page that starts with De Morgan's laws.

• Compile and run the program (making use of the CWEB system downloadable from Knuth's website) KODA-RUSKEY on Knuth's page of programs. Turn in (a) the first page of the nice literate version of the program, (b) the first page of the C program listing, and (c) the output of the program on the input "((()((())())))()". There is no need to understand the program or the algorithm. We will get to that eventually.

• Section 7.1.1: Prove equation (4) from truth tables.

• Section 7.1.1: Exercise 10, except instead of (22) use the truth table 0110 1111 1001 0000. Note that this exercise leads into the next couple of exercises --- try to at least read them.

• [0 marks] Read pages v-12 (don't worry about understanding this material, just try to get a flavor of the subject) and 47-54 of the text (understand this material).

• A programming problem:
  • Turn off the internet and clear away all distractions.
  • Record your start time.
  • Read the problem. Do not peek ahead of time.
  • Formulate it mathematically.
  • Turn that formulation into a program and run it.
  • Check that your answer is correct.
  • Record your finish time.
  Too turn in: (0) Your mathematical formulation; (1) Your program listing; (2) Your start and finish times and the difference, (3) Your ideas about how to generalize the problem so that it has inputs and outputs. The program need not be commented or pretty, just turn in the version that first worked. Part (2) will not be marked except to note whether you turned it in or not; similarly (3) will not be marked.