CS 3304
Solutions to Homework Assignment 4
July 31, 1997

[15] 1.

Chapter 9, Problem 5.

See Figure  for an illustration of the activation records on the stack, beginning with the activation record for BIGSUB.

  
Figure: Stack contents with dynamic and static links

Dynamic and static links are as shown.

[15] 2.

Chapter 9, Problem 6.

See Figure  for an illustration of the activation records on the stack, together with the display in place of the static links.

  
Figure: Stack contents with dynamic links and display

To be able to restore the display values on procedure exit, each activation record has space allocated to save the old display value. The figure assumes that the parent of BIGSUB is at level t.

[15] 3.

Chapter 10, Problem 12. To ensure some uniformity of solutions, use queue_elem as the type of an element of the queue and queue_size as the maximum number of elements that may be in the queue.

For a queue, there are four obvious operations (or equivalents):

1. enqueue(queue,item) -- put item at the end of queue;
2. dequeue(queue) -- retrieve an item from the front of queue;
3. empty_queue(queue) -- check whether queue is empty; and
4. full_queue(queue) -- check whether the capacity of queue has been reached.

Here is an implementation in C:

#define true 1
#define false 0
typedef int boolean;

typedef struct {
  queue_elem store[queue_size];    /* storage for actual queue elements */
  int in;    /* next position to insert a queue element */
  int out;   /* next position to retrieve a queue element */
  int count;    /* count of number of elements currently in queue */
} QUEUE;

void enqueue(queue,item)
QUEUE queue;
queue_elem item;
{
if (queue.count >= queue_size) raise("queue overflow");
else {
  queue.count++;
  queue.store[queue.in] = item;
  queue.in = (queue.in+1) % queue_size;
}
};    /* end enqueue */

queue_elem dequeue(queue)
QUEUE queue;
{
queue_elem item;
if (queue.count <= 0) raise("queue underflow");
else {
  queue.count--;
  item = queue.store[queue.out];
  queue.out = (queue.out+1) % queue_size;
  return item;
}
};    /* end dequeue */

boolean empty_queue(queue)
QUEUE queue;
{
if (queue.count == 0) return true;
else return false;
};    /* end empty_queue */

boolean full_queue(queue)
QUEUE queue;
{
if (queue.count == queue_size) return true;
else return false;
};    /* end full_queue */

The subroutine raise handles exceptions but is not defined here.

[15] 4.

Chapter 10, Problem 14. You are to define 6 operations on an abstract data type called complex. You may do this in C, if you prefer, with the following key type definition:

typedef struct {
    double re;	/* real part */
    double im;	/* imaginary part */
} COMPLEX;

As help in implementing division, note that if a + b i is a nonzero complex number, then its reciprocal is

An attempt to divide by 0 should result in an exception being raised, say by a call to a procedure exception (which you can just assume exists).

Here is an implementation in C:

typedef struct {
    double re;  /* real part */
    double im;  /* imaginary part */
} COMPLEX;

COMPLEX Cadd(z1, z2)    /* add two complex numbers */
COMPLEX z1,z2;
{
COMPLEX result;
result.re = z1.re + z2.re;
result.im = z1.im + z2.im;
return result;
};

COMPLEX Csubtract(z1, z2)    /* subtract two complex numbers */
COMPLEX z1,z2;
{
COMPLEX result;
result.re = z1.re - z2.re;
result.im = z1.im - z2.im;
return result;
};

COMPLEX Ctimes(z1, z2)    /* multiply two complex numbers */
COMPLEX z1,z2;
{
COMPLEX result;
result.re = z1.re * z2.re - z1.im * z2.im;
result.im = z1.re * z2.im + z1.im * z2.re;
return result;
};

COMPLEX Cdivide(z1, z2)    /* divide one complex number by another */
COMPLEX z1,z2;
{
COMPLEX reciprocal;
double modulus;
modulus = z2.re * z2.re + z2.im * z2.im;
if (modulus == 0) exception(); /* raise an exception for divide by zero */
reciprocal.re = z2.re / modulus;
reciprocal.im = - z2.im /modulus;
return Ctimes(z1,reciprocal);
};

double Creal(z)    /* extract the real part of a complex number */
COMPLEX z;
{
return z.re;
};

double Cimaginary(z)  /* extract the imaginary part of a complex number */
COMPLEX z;
{
return z.im;
};

COMPLEX Cconstruct(x,y)    /* construct a complex number
                              from two real numbers */
double x,y;
{
COMPLEX result;
result.re = x;
result.im = y;
return result;
};

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -t CS 3304 Solutions to Homework Assignment 4 solvehw4.

The translation was initiated by cs3304sm class account on Fri Aug 8 07:43:07 EDT 1997