This website is preserved for historical and scholarly reference and is no longer actively maintained.
Reading Assignments and Reading Homework
CPSC 241 -- Spring 2001
The following reading assignments are made. Homework, in the form of a synopsis of the reading assignment, will be collected at the beginning of the designated class meeting.
The intention of these assignments is (1) to persuade everyone to read the text books, (2) to allow the instructor to emphasize major concepts and critical points in the text material, and (3) to allow class discussions to introduce material not covered in the text.
Homework must be typed (unless specified otherwise) and will be collected at the beginning of class on the date the homework is due.
Late homework (i.e., turned in after the beginning of class) will be accepted until 4 p.m. on the date the homework is due (with a 10% penalty).
Homework will not be accepted after 4 p.m. on the date due except in unusual (and documented) circumstances. Homework will not be accepted by email.
You will have the use of your own synopsis when taking hour tests, so
you should organize the synopsis to be most useful to you. Do not
copy large sections of the text, but do condense and organize the
material.
Homework is to be done individually. The purpose of the "read and
report" homework is to aid in your individual learning.
Thus, it is important that each person read and
write for themselves. If the instructor believes that homework has
been jointly written, on the first occurrence the grade will be
shared jointly among the writers. A second occurrence will be
considered academic dishonesty and appropriate action will be taken.
In general, do not copy large sections of code into your synopsis.
Any code you do copy is not included in the required length of the
text. Use 12 point new Roman Times or Times font, single spaced.
Double space between paragraphs.
If class is cancelled because of inclement weather, the reading assignment will be due at the next class meeting.
#1 -- due Wednesday, January 17
Chapter 1 (pages 1 - 27). Include (at least) definitions of mathematical
operations using exponents, static, Comparable, Exception, package, and
final. Text should be at least 1.5 pages (8 pts.).
Work problem 1.5 on page 26 and include a trace of your code (2 pts.). Your recursive method should be
public static int countBin ( int n )
// pre: n >= 0
// post: returns number of 1's in binary representation of n
#2 -- due Friday, January 19
From Chapter 3 (Section on lists, pages 55-63), write a synopsis
(8 pts.). Write a size method that could be included in an extension
of the LinkedList class that returns the number of Objects stored
in the list (2 pts.).
#3 -- due Monday, January 22
Write a synopsis of Chapter 2 ( pages 29-49) ( 8 pts.).
Give an analysis on the running time (theta) of the code segment in problems
2.7(1), 2.7(2), 2.7(3), and 2.7(4). State your conclusion
and give a justification, such as the result of solving
summations, to justify your conclusion. (2 pts.)
#4 -- due Wednesday, January 24 (2 pts. extra credit)
Write a method to solve problem 3.9 on page 95. This method should
use the LinkedList, ListNode, and ListItr methods, but should not
attempt to use the instance variables of any class.
The intersection of two sets, A and B, is defined to be the
set of all elements that occur in both set A and set B.
Thus, if set A contains elements 'b', 'c', 'd', and 'e' and
set B contains elements 'a', 'c' and 'e', the intersection of
sets A and B contains only 'b' and 'e'.
Another example: If set A is as given above and set C contains
elements 'a' and 'f', the intersection of sets A and C is empty
(I.e., contains no elements).
>br>
#5 -- due Friday, January 26 (Stacks, pages 75-88)
Write an explanation, with drawings, of how to evaluate a postfix
expression. Use your own example -- do not just copy the
example in the text. (2 pts.)
Include an explanation,
with drawings, of how to use Weiss' LinkedList to implement a
stack. Explain the growth rate of push and pop for this
implementation. (Let N represent the number of ListNodes in
the LinkedList.) (4 pts.)
Include an explanation, with drawings, of how to use an
array to implement a stack. Explain the growth rate of
push and pop for this implementation. (4 pts.)
Points will not be deducted for length, but may
be deducted if explanations are not clear and correct.
"Explanation" means your own words and, if code is included,
only a very few selected lines, not entire methods.
#6 -- due Monday, January 29 (Queues, pages 88-94)
Write an explanation, with drawings, of how to use an extension of Weiss'
LinkedList to implement a queue. Explain the growth rate
of enqueue and dequeue for this implementation. (5 pts.)
Your implementation should include a tail pointer in addition
to the header (head pointer). Both enqueue and dequeue should
be done in constant time.
Write an explanation, with drawings, of how to use
an array to implement a queue. Explain the growth
rate of enqueue and dequeue for this implementation (5 pts.)
No reading assignment for Wednesday, January 31 -- Program due tonight
#7 -- due Friday, February 2 (pages 99-118 and 138-139, Binary Trees, Binary Search Trees, and Tree Traversals)
Explain how any arbitrary tree can be stored as a binary tree. Using the
tree in Figure 4.8 (page 103), redraw this tree as a binary tree.
(1 pt.)
Draw an expression tree to represent (a - b) * c / e - f / g * h. (2 pts.)
Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 4.65 on page 146.
(3 pts.)
Work problem 4.9 on page 146. (4 pts.)
#8 -- due Monday, February 5, pages 118 - 130, AVL trees
Work problem 4.21 on page 147: Write the remaining procedures to
implement AVL single and double rotations. (10 pts.) It is not
necessary to compile and run these, but they must be typed.
#9 -- due Wednesday, February 7 -- Problem 4.31(b) on page 148 (2 pts.)
Write an efficient method that takes only a reference to the root of a binary tree, T, and computes the number of leaves in T. Must be typed.
#10 -- due Friday, February 9 -- AVL trees
Work problem 4.22 on page 147: Design a linear-time algorithm that
verifies that the height information in an AVL tree is correctly
maintained and that the balance property is in order. ( 5 pts. )
#11 -- due Wednesday, February 21 -- Hashing, Separate Chaining
Read pages 155-162 of Chapter 5. Answer the following questions:
(1) What advantages do hash tables have over other data structures
you have studied such as arrays, Vectors, and trees? (4 pts.)
(2) What disadvantages do hash tables have with respect to
other data structures? (4 pts.)
Work problem 5.1.a on page 178. (2 pts>)
#12 -- due Monday, February 26 -- Hashing, Open Addressing
Read pages 162-174 of Chapter 5. Answer the following questions:
(1) Is the size of the table more important with Open Chaining or
with Open Addressing? Explain why. (1 pt.) Work parts (b), (c), and (d)
of problem 5.1 on page 178. (3 pts. each part)
#13 -- due Friday, March 2 --
Prepare and turn in a 1-page spreadsheet (10 pts.) containing the following
information:
Your name
CPSC 241, Section 2
A list of grades for daily quizzes (1-14), showing quiz number
and date of quiz, the quiz average, and the quiz average
if 3 grades are dropped before computing average.
A list of reading grades (assignments 1-6 & 8), listing the
assignment number by each grade, and the average of these
reading grades (your sum / maximum possible).
Your grade on the first hour quiz, labelled.
The grade you would receive if the final grade were based on these
three componenets and their relative percentage allocation.
All information must be typed.
#14 -- due Monday, March 12 -- Disjoint Set ADT
Work problem 8.1 (a, b, and c) on page 287 (10 pts.).
#15 -- due Wednesday, March 14 -- union by size
The code for union-by-height (rank) is given in Figure 8.13 on page 277.
Write code for the union method if union is by size. (10 pts.)
**************************************************
the next assignment is subject to change
***************************************************
#11 -- due Monday, February 12