CSC 344
Homework 1 Revisited

Assigned Feb. 21, due Mar. 9

Since so many of you did so poorly on homework 1, either because your "pseudocode" was too vague or because you misunderstood the question, I'm re-writing several of the problems as actual programming problems, to be written in an actual programming language so that they actually run and produce correct answers.

You may do as many or as few of these as you wish; they will be counted as extra credit and added onto your homework 1 grade. Since writing functions in an actual programming language is more time-consuming than writing pseudocode, the extra credit will be more than the original problem.

1. Write two functions in your favorite language (e.g. Java, C++, Scheme) which take in a number and a desired accuracy, and computes the square root of the number to within the desired accuracy. Both functions should accomplish the same task, but by different algorithms: one computes the square root using the Babylonian algorithm, and the other computes the square root using the bisection algorithm. Each of the two should report not only the square root it found, but how many iterations it took to get the desired accuracy. In addition, each of the two functions should produce tracing information, e.g. by printing a line like

   x=3.5 a/x=1.7142 err=1.7858

   for each iteration.

2. Write a function in your favorite language (e.g. Java, C++, Scheme) that takes in a string of digits and a base (an integer, at least 2 and no more than 10) and returns the integer the digits represent in that base. If there are any digits >= the base, or any characters that are not digits at all, your program should detect this and signal an error.

   For example, convert("325",10) should return the integer 325.
   However, convert("325",7) should return the integer 166, since 325 in base 7 is 3*7² + 2*7¹ + 5 = 166.
   And convert("325",4) should signal an error, because '5' is not a legal digit in base-4 notation.

3. Write a collection of functions in your favorite language (e.g. Java, C++, Scheme) to operate on a linked list of floating-point numbers, implemented as two parallel arrays: an array of floating-point numbers named data and an array of integers named next. (If you prefer, you may implement doubly-linked lists instead, adding another array of integers named previous.) The functions required are

   • makeEmpty(), which sets up the whole thing as an empty list, initializing the first pointer, the firstFree pointer, and the next fields of the free-list (which is initially the whole array).
   • insertAfter(position,value), which inserts a new entry with the floating-point number value into the list after the element indicated by position. If position is -1, your function should insert a new entry at the front of the list. If there is no spare room in the array, your function should signal an error.
   • deleteAfter(position), which deletes and returns the element after the one indicated by position and returns that array slot to the free-list. If position is -1, your function should delete the first element of the list. If position indicates the last element of the list, your function should signal an error.
   • reverse(), which reverses the entire linked list, preferably without moving any of the floating-point numbers in the data array.

4. Write three functions in your favorite language (e.g. Java, C++, Scheme) to operate on a queue of floating-point numbers, implemented as an array that "wraps around" and has at least one empty slot at all times so that the "queue full" condition can be distinguished from the "queue empty" condition. The functions are

   • makeEmpty(), which sets the front and rear pointers to indicate that the queue is empty.
   • enqueue(value), which takes in a floating-point number and adds an entry with that value at the rear of the queue. If the queue is already full, your function should signal an error.
   • dequeue(), which deletes and returns the entry at the front of the queue. If the queue is empty, your function should signal an error.