cs2223 Exam 4

[WPI] [cs2223] [cs2223 text] [News] [Syllabus] [Exams]

cs2223, D97/98 Exam 4

Question 4.1

Laser printers produce gray by printing random patterns of white and black dots. Here are two algorithms for painting a digital picture (matrix of chars) gray. Assume both start with the picture all white, which means all array values are initialized to zero.

char picture[480][640]; // global variable
void gray1(int xmax, int ymax)
   {
   for (int y = 0; y < ymax; y++)
      for (int x = 0; x < xmax; x++)
         if (rand()%2) picture[y][x] = 1; // black
   }
void gray2(int xmax, int ymax)
   {
   for (int n = 0; n < xmax*ymax/2; n++)
      {
      int x = rand() % xmax; int y = rand() % ymax;
      picture[y][x] = 1; // black
      }
   }

Compare these algorithms and tell which you would choose and why. Compare the order of the algorithms, the average level of gray produced, the uniformity with which the black dots are distributed, and others criteria you think important.

Question 4.2

The rook is a chess piece which can move any number of spaces along rows or columns only; the bishop can move any number of spaces along diagonals only. On a square chessboard with N rows and N columns, we want to know how many rooks can be placed without being able to capture or be captured. As a separate problem, how may bishops can be placed?

Figure illustrating the types of moves rooks and bishops can make.

Q2a). Describe, in words, an algorithm to place as many as possible rooks on a NxN chessboard.

Q2b). Describe, in words, an algorithm to place as many as possible bishops on a NxN chessboard.

Hints: A trivial algorithm is still an algorithm. You may refer to any algorithm we have studied, but only if you carefully explain the ways in which your algorithm is similar and the ways in which it is different.

Question 3.3

A trinary tree is made of nodes with up to three children. It is doubly-linked, which means each node knows its children and its parent. The nodes are defined by this struct.

struct node
   {
   int val; // the value
   struct node *left; // pointers to children
   struct node *center;
   struct node *right;
   struct node *parent; // pointer to the node's parent
   };
typedef struct node node; // you can call it "struct node" or "node"

Write a function which takes two node pointers and returns the address of the nearest mutual ancestor. You may use any C/C++ libraries. Include a calculation or estimate of the order of your algorithm assuming the tree is complete - which means that each level is completely filled before anything is placed in the next level down.

Use this function prototype:

node *nearest_ancestor(node *nodeA, node *nodeB)