Homework 10 for Computer Science 125

Introduction to Computer Science

Boise State University, Spring 1999

Warm-up and Practice Problems

• CCJ: Exercise R13.4, p 535.
• CCJ: Exercise R13.5, p 535.
• CCJ: Exercise R13.13, p 536.
• CCJ: Exercise P13.10, p 539.
• CCJ: Exercise P13.13, p 539.
• CCJ: Exercise R14.1, p 562.
• CCJ: Exercise R14.5, p 563.
• CCJ: Exercise P14.2, p 566.
• Give 3 examples of ethical dilemmas arising from Artificial Intelligence and Expert Systems. What makes these dilemmas distinct to AI?
• In Chapter 8 of the Ethics Book, the effect of computers on the workplace is discussed. Should this chapter be included in a book on ethics? Justify your answer.

Graded Problems

Extra Credit: There will be extra credit points for turning these programs in early. For each program turned in by Thursday 9 pm, you receive 5 extra credit points. For each program turned in by Wednesday 9 pm, you receive 10 extra credit points.

P29. (Daily Appointments) Write a class called Daily to keep track of daily appointments. Your class should contain a list of appointments (you may assume that there will be no more than 50 appointments per day) and a counter that keeps track of the number of appointments. Your class should contain a default constructor that initializes the array and sets the counter to 0.

Your class should also contain the following methods:

• public void addAppointment(Appointment a) that inserts an appointment into the list. The list should be sorted by beginning time of appointments.
• public Appointment getAppointment(int n) that returns the nth appointment on the list. If n is larger than the number of appointments, this function should return null.
• public void print() that prints all the appointments.
• public int search(String s) that finds the first appointment that contains s as part of its description and returns its index in the list.

Your main program should ask the user to enter an appointment as many appointments as they wish. Then, it should give them the choice of adding an appointment, finding an appointment by substring or number, or printing. For example:

> javac Program29
Please enter the beginning time for an appointment
(year month day hour min second):
1999 5 10 15 30 0

Please enter the ending time for an appointment
(year month day hour min second):
1999 5 10 17 30 0

Please enter a description of the appointment:
Final Exam!

Do you want to enter another appointment? (y/n)
y
	
Please enter the beginning time for an appointment
(year month day hour min second):
1999 5 10 4 0 0

Please enter the ending time for an appointment
(year month day hour min second):
1999 5 10 15 0 0

Please enter a description of the appointment:
Study for exam
	
Do you want to enter another appointment? (y/n)
n

Choose one of the following options:
  1) Add another appointment
  2) Find an appointment by substring
  3) Find an appointment by appointment number
  4) Print all appointments
  5) Quit
Your choice:
2

Enter the substring:
Final

The appointment is: Final Exam!
Beginning Time: 1999 5 10 15 30 0
Ending Time: 1999 5 10 17 30 0
	
Choose one of the following options:
  1) Add another appointment
  2) Find an appointment by substring
  3) Find an appointment by appointment number
  4) Print all appointments
  5) Quit
Your choice:
5

Thank you for using the daily appointments program!

You should include comments for each of your functions that can be used by javadoc to generate documentation (see notes from class or the book for more details about using javadoc). This program should be console-based. Submit this as program 29 using the electronic submission. Please call the file (and the class) Program29.

P30. (Sun Sorting Demo) On their Applets page, Sun has a sorting demonstration. Copy the following files into your directory from the Sun site:

• The applet.
• The "generic" sorting algorithm.
• The Bubble Sort algorithm.
• The HTML file (view the source of this).

Make two new subclasses of the SortAlgorithm class for selection sort and merge sort (see the book for the algorithms, or, for merge sort, you may use P25 of Homework 8). Make a new HTML file (based on the one above) that displays selection sort, merge sort, and bubble sort. Note that you do not modify SortAlgorithm. Instead you create new classes, similar to BubbleSortAlgorithm, called SelectionSortAlgorithm and MergeSortAlgorithm.

Submit this as program 30 using the electronic submission. Please call the file (and the class) Program30. Include an HTML file in the directory called Program30.html that displays your applet.

P31. (Binary Search Tree) Write a program that reads in words from a file called dictionary.dat and inserts each word into a binary search tree. Your program should then print out the words in alphabetical order. Words may occur multiple times in the input file. However, they should only be placed in the binary search tree the first time they occur.
Submit this as program 31 using the electronic submission. Please call the file (and the class) Program31.
Extra Credit: Extra credit will be given if, along with the sorted list you also print out the height of the binary search tree used. For example, for dictionary.dat, the resulting binary search tree would be:
The height of this tree is 5.
Hints:
• Modify the program Etree.java (from Chapter 13) to work with words instead of employees. The programs from the book can be found in:

  	    /usr/local/javas/ccj
  	    

• Since we allow duplicate words, your inserting method must also check if the word is already in the binary search tree.
• On the extra credit, think recursively.