Programming Language Concepts


The following table indicates assignments and due dates for Computer Science 302. Unless otherwise indicated,

Due Date Text Chapter Collaboration Problems Answer Format and Notes
January 23 Gries1 No 1.3,1.4 in writing
Gries2 No 2.5, 2.6cegk in writing
January 26 Gries2 Yes 2.6fhjl in writing
Mitchell1-2 Yes 2.1 in writing
Yes Problem 1 (below) in writing
January 28Mitchell3 Yes 3.2, 3.3class presentation; group assignment 0
January 30 Gries4 No 4.1.3, 4.2.6a-bjkm, 4.4.2, 4.5.2acin writing
February 4 Mitchell4 yes 4.1-4.4, 4.6 in writing; group assignment 1
February 6 Gries5-6 No 5.1.1ace, 5.1.2bfg, 5.2.2, 5.2.3, 6.2.1deg in writing
February 11 Michell 4 Yes Problem 2 (below) in writing; group assignment 2
February 18 Michell 4 Yes 4.8, (4.9 or 4.10), 4.13 in writing; group assignment 3
February 25 Michell 5 No ML Programming Assignment 1 program and tests
February 27Gries7 No 7.1acef, 7.2(1,3,5), 7.4, 7.5 in writing
Gries8 No 8.1, 8.3, 8.6 in writing
March 8 Gries9 No 9.1.1ace, 9.2.2, 9.2.3bdf, 9.2.4ace, 9.3.1ace in writing
Gries10 No 10.1, 10.3, 10.5, 10.6, 10.8 in writing
March 10 Mitchell5-6 Yes ML Programming Assignment 2 program and tests
Mitchell6 Yes 6.1, 6.2, 6.5, 6.6, 6.7 in writing, group assignment 4
March 12 Gries11 No 11.1, 11.8, 11.9, 11.10, 11.12 in writing
Gries14 No 14.1abd in writing
March 31Mitchell7 Yes Problem 3 (below) in writing, group assignment 5
April 2 Gries15 No 15.1.3, 15.1.4, 15.2.2, 15.2.3, 15.2.4 in writing
April 7 Gries 15-16 Yes Problem 4 (below) in writing, group assignment 6
April 9 Gries16 No 16.2.2, 16.2.3 in writing
Gries16 No 16.3.1, 16.3.5, 16.3.7 in writing
April 14 Mitchell 8 Yes 8.8 and any 3 of 8.1, 8.2, 8.4, 8.5 in writing, group assignment 7
April 16 Gries16 No 16.5.2, 16.5.5, 16.5.9 in writing
April 16 Gries16 No Problem 5 (below) in writing , group assignment 8
April 23 Gries16 No 16.5.2 (proof required) in writing
16.5.5 (1 pass through data, proof required)
16.5.9 (simple arithmetic only, no logs,
assume array large enough without
declaration, proof required)
April 28 [Prolog] Yes Problem 6, Problem 7 (below)
April 30 [Prolog] No Problem 8, Problem 9 (below)
Due Date Text Chapter Collaboration Problems

Additional Exercises

Problem 1: Find a partial function that has all three of the following three properties:

Note: In the preferred solution to this problem, "at least 2 values" would be replaced by "an infinite number of values" in each case above.

Problem 2: Give the BNF grammar and the corresponding denotational semantics for the Roman numerals between 1 and 99 (inclusive).

Problem 3: Write a program with just two procedures which prints the single integer shown in the following table, based on the type of parameter passage and scoping rules:

Desired Result Description
1. Parameter passage is by value and with static scoping rules.
2. Parameter passage is by value-result and with static scoping rules.
3. Parameter passage is by reference and with static scoping rules.
4. Parameter passage is by name and with static scoping rules.
5. Parameter passage is by value and with dynamic scoping rules.
6. Parameter passage is by value-result and with dynamic scoping rules.
7. Parameter passage is by reference and with dynamic scoping rules.
8. Parameter passage is by name and with dynamic scoping rules.

Thus, if the program were interpreted as parameter passage by value-result with dynamic scoping rules, then the program should print the number 6.

Problem 4: Develop a binary search program with the following conditions:

Preconditions: integers m, N are given with 0 ≤ m < N
integer array a[0..N] is defined and initialized
array segment a[0..m] is in non-descending order
that is, a[k] ≤ a[k+1] for each 0 ≤ k < m
item is an initialized integer variable
Postconditions: integer variable i satisfies the following:
((0 ≤ i ≤ m) cand (item = a[i])) or ((0 ≤ i ≤ m+1) and (item > a[0..i-1]) and (item < a[i..m]))


Problem 5: A class handout gives seven solutions that were turned in to solve the binary search program (Problem 4). This problem asks you to:

  1. Analyze two submitted solutions, work to develop a proof of correctness for each, and complete either your own correctness proof or an explanation of why such a proof cannot be done from the submitted material. If additional information could be added to what is given to support a proof, then you should specify what this material would be.
  2. Translate each solution to a running program in a language of your choice, and provide thorough testing of each program. In the case that you conclude that the submitted program is not correct, you should demonstrate the errors with selected test cases.

Assignments for reviewing code are as follows:

Problem 6: Define Prolog relations to determine if a list has an even number of elements.

Problem 7: Define Prolog relations to determine if a list:

  1. is a permutation of another.
  2. is formed by merging two lists.

Problem 8: Write a Prolog program that succeeds if the intersection of two given list parameters is empty.

Problem 9: Draw Prolog search trees for the query:

?- reverseList([a, b, c, d], W).
where reverseList is defined by the rules:
reverseList([ ], [ ]).
reverseList([A|X], Z) :- reverseList(X, Y),append(Y, [A], Z).
reverseList(X, Z) :- rev(X, [ ], Z).
rev([ ], Y, Y).
rev([A|X], Y, Z) :- rev(X, [A|Y], Z).

This document is available on the World Wide Web as

created December 20, 2003
last revised April 18, 2004
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at