CPSC 320 — Pending Homework Questions

Last modified: 2022-09-05

This is a course web page of
David Casperson

Associate Professor
Computer Science
University of Northern British Columbia

Generally speaking, questions that have been assigned but not yet give a due date can be found on this page. Questions that have been given a due date can be found here. There is now homework due.

Pending homework questions

All homework now has a due date. Please see Homework Due.

Consider the following Racket program:

#lang racket

(define (fred)
  (define x 64)
  (define ichabod (gertrude))
  (ichabod 5))

(define (gertrude)
  (define x 32)
  (define (harriet y)
    (+ x y))
  harriet)

(module+ main
  (displayln (format "(fred) returns ~v" (fred)))
  )

What output does this program produce?
What output would this program produce if Racket used static scoping?
What output would this program produce if Racket used dynamic scoping?

2016-11-04

Figure 1

<condition> ::= true | false

<var>       ::= a | b | c | d

<value>     ::= 3 | 5

<assignment> ::= <var> := <value>

<block> ::=
      begin <block-body> end
    | begin              end

<block-body> ::=    <statement>
   | <block-body> ; <statement>

<statement> ::=
      <if-then-stat>
    | <bal-stat>

<if-then-stat> ::=
      if <condtion> then <statement>

<bal-stat> ::=
      <block>
    | <if-then-else-stat>
    | <assignment>

<if-then-else-stat> ::=
      if <condition> then <bal-stat> else <statement>

Consider the grammars shown in Figures 1 and 2. They both specify vaguely C like-languages that differ only in their treatment of if-then statements.

Determine which of the following statements have legal parses according to the two grammars:

```
begin end
```
```
b := 3
```
```
b := 3; c := 5
```
```
begin b := 3; c := 5 end 
```
```
if false then begin b := 3 end 
```

if false then
      begin if true then b := 3
      end
      else c := 5

NB: there is a correction in part (f.) above. Thanks to Lee C. for noticing.

Figure 2

<condition> ::= true | false

<var>       ::= a | b | c | d

<value>     ::= 3 | 5

<assignment> ::= <var> := <value>

<block> ::=
      begin <block-body> end
    | begin              end

<block-body> ::=    <statement>
   | <block-body> ; <statement>

<statement> ::=
      <if-then-else-stat>
    | <no-last-else-stat>

<no-last-else-stat> ::=
      <assignment>
    | <block>
    | <if-then-stat>

<if-then-stat> ::=
      if <condtion> then <no-last-else-stat>

<if-then-else-stat> ::=
      if <condition> then <statement> else <statement>

Does either grammar solve the problem of dangling else statements? If so, how? If not, why not?

2016-11-16

Write a Scheme function average that takes an arbitrary number of numeric arguments and computes their average. The point is to show that you know how to write a Scheme function that receives an arbitrary number of arguments.
Write a Scheme function (format-seq arg ...) that takes an arbitrary number of numeric arguments and returns that is similar to (format "~s" (list arg ...)).

For instance, (format-seq 3 "cow" 5) should return the string “(3 "cow" 5)”.

However, format-seq should also have three optional keyword arguments #:start, #:end, and #:sep (with default values "(", ")", and " " resepctively) that determine the initial, final, and separator strings.

For instance, (format-seq #:end " <<<" 3 "cow" 5 #:sep "+") should return the string “(3+"cow"+5<<< ”.

The point is to show that you know how to write a Scheme function that receives optional and keyword arguments.
This question is really about Floyd-Hoare axiomatic semantics. Which statement
- Barack Obama is president of the United States.
- Donald Trump is president of the United States.
is more likely to make a valid loop invariant? Under what assumptions? Why?

>>>>>>> final 320 homework for "Semesters/2016-05F".

2016-11-17

```
Figure 3
private static <E extends Comparable<E>>
void partition(E [] data, E key, Box<Integer> cut)
    {
    int left = -1 ;
    int right = data.length ;

    while(left<right)
        {
        do {++left ;  } while (data[left ].compareTo(key)<0) ;
        do {--right ; } while (data[right].compareTo(key)>0) ;
        if (left<right) swap(data,left,right) ;
        }
    cut.set(left) ;
    }
```
Consider the Java code shown in Figure 3. This is the partitioning algorithm from Quick sort.
1. What parameter passing mechanism does Java use?
2. Is the calling function's copy of data modified by this routine? Explain.
3. How does Java’s parameter passing mechanism explain the point of the cut argument? Why isn't this just passed back as an int?
4. What is the (useful) loop-invariant for the outer the while-loop?
5. Write a {P} C {Q} claim where C is the entire first do-while loop.
6. Consider the first inner do-while loop. What condition needs to be true for the loop to terminate?
7. This algorithm doesn’t always run without errors. What pre-condition is necessary for the algorithm to return without errors?
8. If the algorithm does return without errors, what is true on return?

2016-11-20

Consider the statement
```
while (i>0) { a *= (i--) ; } 
```
- What is one pre-condition that results in the post-condition “i=0, a=120”?
- What is the weakest pre-condition that results in the post-condition “i=0, a=120”?
Consider the statement
```
while (i>0) { s += (i--) ; } 
```
What is the strongest post-condition that we can assert for the pre-condition “i=4, s=5”?

======= ======= >>>>>>> Removed a stash.