CSci 4651 Problem set 1.

Due Monday, February 8th at 11:59pm (by e-mail)

26 points

All textbook problems are in section 1.18

Problem 1 (6 points)

Problem 1 p. 23 (please submit your kernel language programs).

Problem 2 (5 points)

Modify GenericPascal so that one can pass to the function not only the operation to combine the list elements, but also the starting row value (currently 1) and the element added as "padding" when shifting rows (currently 0).
Check that you can generate the original Pascal triangle by passing 1 for the starting row value and 0 as padding.
Generate a triangle by starting with the row of 1, using 2 for padding, and multiplication as a combining function. How many rows does one need to compute to produce a value of 2^64 or higher [Corrected on 2/4] as the highest value in a row? Please explain your answer.

Problem 3 (5 points)

Exercises 7, 8 on p. 24. Submit the corrected code for 8.

Problem 4 (10 points)

Construct an EBNF for a language of boolean constants T, F (that stand for true, false), operations not, and, or, and parentheses. In the language:

• not has the highest precedence, meaning that it refers to the smallest element that follows it. For instance, not T or F should be parsed as if parentheses are as follows: (not T) or F,
• and has a higher precedence than or, so T or F and T is parsed as T or (F and T),
• both and and or are left-associative, i.e. T or T or F is parsed as (T or T) or F,
• parentheses overwrite any default rule, just like in arithmetic expressions.

• T or not F and not T and F
• not (T or F) and not T

How to submit

Submit your file(s) to me by e-mail. The subject must be Problem Set N, where N is the problem set number.
Handwritten problems can be scanned and attached (good quality scanning, please!) or submitted in class or in my office in person. If submitting handwritten work, please clearly write your name and problem set number on it.

CSci 4651 course web site.