This website is preserved for historical and scholarly reference and is no longer actively maintained.

Homework Assignments

Spring 1999

Homework will either be submitted by Email or be collected at the beginning of class on the date the homework is due. When homework is to be collected at the beginning of class, homework will not be accepted after 8 a.m. (i.e., Do not cut class or be late to class in order to finish the homework.) When homework is to be collected by Email, the time will be earlier.



The amount of collaboration allowed will differ from assignment to assignment.

#8 (due Monday, March 8 by midnight. Use Email.)

This assignment is to be done individually. Do not work together. Late penalty is 5 points. Not accepted after 8 a.m., Tuesday, March 9.

#7 (due Thursday, March 4, at the beginning of class)

Prepare a spreadsheet summarizing your grades to date. The first information on the spread sheet must be your name, CPSC 241, Section 1, and the date.

You should include your hour quiz grade I and the percent it counts of the final grade. You should include a listing of your homework grades, identified as hw#1 and date, hw#2 and date, etc. Include an average of your homework grades. You should include a listing of your short quiz grades, identified as quiiz#1 and date, quiz#2 and date, etc. Include an average of your short quiz grades.

Also show an average of the best 80% of your combined shortquiz and homework grades. The number of grades to drop is the integer result of N*0.2, where N is the total number of homework and quiz grades. Four homeworks were turned back to you by February 25 and Quiz #9 was on February 25. Your spread sheet must include grades for the first four homeworks and quizzes 1 through 8. Additional grades may be included, if you have them.

If you cannot find some of your grades, you may Email the instructor for the grades. A penalty of one point per grade supplied will be assessed for each grade in excess of four. That is, you can request as many as four quiz grades that you do not have without penalty. Late penalty: 5 points. Not accepted after Friday, March 5. (Those submitted after class Thursday must be delivered to the instructor's mail box in the Computer Science Department.)

Quality of presentation as well as correctness will be considered in grade.

#6 (due Friday, March 5 at 7 a.m.)

Problem 5.18 (page 207) requires you to implement a spelling checker by using a hash table. This homework requests the design, but not the implementation, of the spelling checker.

Assume that the dictionary comes from two sources: an existing large dictionary and a second file containing a personal dictionary (or a document). Output all misspelled words and the line numbers on which they occur. Also, for each misspelled word, list any words in the dictionary that are obtainable by applying any of the following rules: Design an approach to this problem. What methods do you need? How will you subdivide the problem into self-contained methods that solve the problem. Show the interface of the class MySpellChecker. For each method, give the preconditions (if any), postconditions, and pseudocode algorithm.

Quality or presentation as well as correctness will be considered in grade.

This homework is to be individual work. Late penalty: 5 points. Not accepted after 7 a.m. Monday, March 8.

#5 (due Thursday, Feb. 25 at 7 a.m.)

This homework may be done in groups and submitted either in groups or individually. (Just be sure that I receive a copy from each group.) Submit by Email.

The constructor for the HashTable at the top of page 194 uses a call to a function "nextPrime(size)" which we assume returns the next prime number larger than size. Design the function nextPrime. (Do not write code.) Your design should include an algorithm, a description of any data structures required, and an analysis of the growth rate of the algorithm with the magnitude of size.

#4 (due Thursday, Feb. 18 at 7:00 a.m.)

This homework is to be individual work. You may discuss the ideas provided everybody present is sitting on their hands. No written communication is allowed.

Write C++ code for the following two user functions. Your code may use only the List, ListNode, and ListItr methods.

1. A user function that maintains non-descending order in a list as elements are inserted. As each element is added to the list, the element is placed in its correct position. You will need to write the C++ code for "void insertSorted( List <Object> & L, const Object & x)". Duplicates are allowed.

2. A user function that removes duplicates from an existing list. You will need to write a function such as "void removeDuplicates ( List <Object> & L )". Again, this function is not part of the List class and uses only List, ListNode, and ListItr methods. (This code is somewhat tricky because L.remove() does not do what you would really like it to do.)

Submit this homework by Email by 7 a.m., Thursday, Feb. 18. Late penalty is 5 pts. Not accepted after 7 a.m., Friday, Feb. 19.

#3 (due Tuesday, Feb. 16 at 7:00 a.m.)

This homework is to be individual work. You may discuss the ideas provided everybody present is sitting on their hands. No written communication is allowed. The following is quoted from Java Structures, by Duane A. Bailey (page 26):

"The precondition describes, as succinctly as possible in your native tongue, the conditions under which a method may be called and expected to produce correct results. Ideally the precondition is expressed in terms of the state of the program. This state is usually cast in terms of the parameters passed to the routine. ... When there is no precondition on a procedure, it may be called without failure.

"The postcondition describes the state of the program once the routine has been completed, provided the precondition was met. Every routine should have some postcondition. If it does not, then the routine does not change the state of the program, and the routine has no effect.

"Pre- and postconditions do not force you to write code correctly. Nor do they help you find the problems that do occur. They can, however, provide you with a uniform method for documenting the programs you write, and they require more thought than the average comment. More thought put into programs lowers your average blood pressure and ultimately saves you time you might spend more usefully playing outside, visiting museums, or otherwise bettering your mind."

1. Provide postcondition comments and precondition comments, if required, for the hash function in Figure 5.3 on page 183.

2. What value is returned by the hash function in Figure 5.2 if the key is "john" and the tableSize is 19?

3. What value is returned by the hash function in Figure 5.3 if the key is "john" and the tableSize is 19?

4. What value is returned by the hash function in Figure 5.4 if the key is "john" and the tableSize is 19?

5. Write a pseudocode algorithm for Problem 3.9 on page 116. ("Given two sorted lists, ...)

Notes on this homework: If you wish to compile and run the functions in questions 2, 3, and 4, you should use the string type found on pages 96 - 99 of C++ Primer. You will need to use the g++ compiler, because CC does not have a string type.

Submit this homework by Email by 7 a.m., Tuesday, Feb. 16. Late penalty is 5 pts. Not accepted after 8:00 a.m., Tuesday, Feb. 16.

#2 (due Thursday, Feb. 4 at 7:00 a.m.)

This homework is to be individual work. You may discuss the ideas provided everybody is sitting on their hands. No written communication is allowed.

Given a linked list L as input, write a pseudocode algorithm for a radix sort of N integers, maximum length of any integer = k digits, and m buckets. The buckets are an array of linked lists, B[0], B[1], ..., B[m-1]. You may use the variables N, k, and m, as needed. Do not use "magic numbers."

Rubric: Not accepted after Saturday, Feb. 7, at noon.

Do not send as an attachment. Use ":r filename" to include in body of Email.


Return to Eleanor Hare's home page.

Return to Department of Computer Science Home page.