CSci 2101 Data Structures: Problem set 1

Due Monday, February 7th at 8pm.

Problem 1 (5 points)

The following program computes the circumference and the area of a circle with an integer diameter. The program has rounding errors. Identify the errors and correct them so that the program computes with the maximum precision that the type double allows. Make sure to test your program carefully and convince yourselves that the there is no precision loss (Hint: diameter = 1 is a good test case). You may not change the type of the variable diameter, but you may change its value to test the program. 

// Written by Elena Machkasova 9/5/04
// Modified by 

public class Precision {
    public static void main(String[] args) {
	int diameter = 1; // change values to test
	final double PI = 3.141592654; // a constant (usually named in CAPS)
	int circumference = diameter * (int) PI;
	double radius = diameter / 2;
	double area = PI * radius * radius;

	System.out.println("If the diameter of a circle is " + diameter);
	System.out.println("then the circumference is " + circumference);
	System.out.println("and the area is " + area);
    }
}
Please submit the corrected program with comments explaining the errors. Don't worry about the formatting of the output.

Problem 2 (10 points)

Write a program that has two variables of type double: fahrenheit and celsius. Initialize fahrenheit to some value. Then the program must perform the following operations:
  1. Convert the temperature to Celsius. Click here for the formula.
  2. Print out the value in Celsius.
  3. If the temperature is above 100 degrees Celsius, print out "The water is boiling", otherwise print out "The water is not boiling"

Problem 3 (10 points)

Write a program to reverse a queue using a stack. Use the classes CharStack.class and CharQueue.class provided.

To test the program, create a new queue, insert some elements into it, then reverse it using a stack, and then print out the elements in the resulting queue. You don't need to put the elements back into the queue after you have printed them out.

Make sure that you have tested your program for different queue sizes, including an empty queue.

Problem 4 (10 points)

Write a program to find out the position of a given element on a stack counting from the top of the stack. More precisely, the program should print out 0 if the element occurs on the top, 1 if there is another element on top of it, and so on. If the element occurs several times, only the topmost position should be printed. If the element doesn't occur at all, -1 must be printed. Use a while loop to accomplish this task. Important: at the end the stack should be returned to the original state (i.e. no elements should be removed and the order of the elements should not change).

Problem 5 (10 points)

Updated 1/28: fixed the program code below, changed the total number of points -- Elena
Code the matching brackets problem. The data to the program should be stored in a string (as in the previous problems, you don't need to read the data in the program, just initialize the string). The string may contain 3 types of brackets, letters, and numbers. For instance, 

String s1 = "(aaa(bc)[6{nn}])";
is a string with matching brackets, while the string 

String s1 = "{[1](2[3)]}";
is not. Below is an example of a loop that goes through the entire string character by character: 

String s1 = "(aaa(bc)[6{nn}])";
int i = 0;
while(i < s1.length()) {
   char c = s1.charAt(i);
   i = i + 1; // to get the next character
   // the rest of your code goes below:

}
Another helpful tip is on how to exit a program: if you have discovered that backets don't match, you should print a message and exit. To exit a program, use
System.exit(0);.
This will terminate the program, even if it hasn't finished the loop. Make sure that the program prints the message before exiting.

Make sure to test your program extensively. Keep your test cases in comments so that I can check how you tested the program. Important: the program must print the answer for any given string, it should never produce a run-time error. If any of the test cases don't work, please write a note in comments explaining what didn't work and, optionally, why you think this is happening. Understanding the cause of an error helps your grade.

If you have any questions about any of the problems, please ask!

This is a problem set from CSci 2101 course.