Mon - March 26, 2007

Data Structures Homework for Week 11. (last one.) 


This homework asks questions on the topics of B-trees, multi-way mergesort, and skip lists, in preparation for the fifth and final quiz.
See the attached PDF file.

A11.pdf  

Posted at 09:37 AM    

Fri - March 16, 2007

Data Structures Homework for Week 10. 


Ex. 7.5 2, 3, 5, 16. 

Posted at 11:52 AM    

Fri - March 9, 2007

Data Structures Homework for Week 9. 


This homework is in preparation of quiz #4.

Ex. 8.14
Questions 6,7,9, 10, 11,12. 

Posted at 10:49 AM    

Fri - March 2, 2007

Data Structures Homework for Week 8. 


This homework is in preparation of quiz #4.

Ex. 8.14
Questions 2, 3, 4, 5, 15, 16, 17, 18 

Posted at 08:09 AM    

Thu - February 15, 2007

Data Structures Homework for Week 7. 


This homework is in preparation for quiz #3.

1. Using a heap will make a minimal difference, if any at all, of a "real" Huffman encoder/decoder. Can you explain why?

2. What would be a good hash code for a vehicle identification that is a string of numbers and letters of the form "9X9XX99X9XX999999",
where a "9" represents a digit and an "X" represents a letter?

3. Draw the hash table of length 11 that results from using the hash function

h(i) = (2i + 5) mod 11,

to hash the keys 12, 44, 13, 88, 23, 94, 11, and 39, assuming that collisions are handled by open addressing with linear probing.


All questions below are taken from Adam Drozdek Data structures and algorithms in C++, Course Technology 2005 (3rd ed.).


Ex. 6.12
Question 25.

Ex. 9.7
Question 1.

Ex. 10.7
Question 1.
 

Posted at 01:46 PM    

Wed - February 7, 2007

Data Structures Homework for Week 6.  


This homework is in preparation for quiz #3.

1. Suppose you are given a text consisting of the characters {A,B,C,D,E,F} with probabilities A= 0.05, B = 0.05, C = 0.10, D = 0.25, E = 0.30, and F = 0.25. Draw a Hufman tree corresponding to these characters and specify the code obtained for each character.

2. Draw a heap with keys values taken from the probabilities in the previous question.

All questions below are taken from Adam Drozdek Data structures and algorithms in C++, Course Technology 2005 (3rd ed.).

Ex. 11.6
Questions 1,2,4.

Ex. 6.12
Question 24.
 

Posted at 12:55 PM    

Thu - February 1, 2007

Data Structures Homework for Week 5. 


1. Define AVL tree.
Tree.pdf
2. Consider the AVL tree in the attached PDF file. Insert a node with key value 55 and rebalance if necessary.

3. Consider the AVL tree in the attached PDF file. Delete the node with key value 42 and rebalance if necessary.

4. Draw an example of an AVL tree such that a single delete operation could require ϴ(log n ) restructuring operations. 

Posted at 04:39 PM    

Thu - January 25, 2007

Data Structures Homework for Week 4. 


Insert into an initially empty binary search tree items with the following key values ( in this order ) 30, 40, 24, 58, 48, 26, 11, 13, 25. Draw the final tree.

Now delete 30 from the tree using the deletion by copying method. Draw the resulting tree.


Section 6.3 discusses the complexity of searching. The quantities that are used to determine this are internal path length and average path length. These quantities are obtained on page 224 for the worst and best cases for a binary tree. The presentation is quite terse. Your assignment is to use your best abilities to flesh the presentation out. That is supply all intermediate steps to obtain the quantities pathworst and pathbest . The analysis of the expected path length is opaque. I will discuss this a bit in class. However, a detailed analysis is beyond the scope of this course. 

Posted at 09:35 AM    

Thu - January 18, 2007

Data Structures Homework for Week 3.  


Questions are taken from Adam Drozdek Data structures and algorithms in C++, Course Technology 2005 (3rd ed.), unless otherwise noted.
This homework does not need to be handed in.

Exercises 6.12

2 a) b) c) d), 4, 6. 10. 

Posted at 09:53 AM    

Thu - January 11, 2007

Data Structures Homework for Week 2. 


Questions are taken from Adam Drozdek Data structures and algorithms in C++, Course Technology 2005 (3rd ed.), unless otherwise noted.
This homework does not need to be handed in.

Exercises 5.12

2, 3, 11, 14.

Supplemental questions.

1. We saw an algorithm with worst case complexity of O(n2) for the pillar problem. What input would cause the algorithm to realize this worst case?

2. Consider a sequence of n integer values (positive and negative). For concreteness assume that the integer sequence is stored in an array A. The maximum consecutive sub-sequence sum is the maximum value of the sum of a consecutive sub-sequence of A. For example if A is the sequence -2, 11, -4, 13, -5, -2, 6 the answer is 20, that is, 11 + (-4) + 13.
Determine an algorithm that finds the maximum consecutive sub-sequence sum of a sequence of integers. An O(n2) algorithm should be relatively easy to come up with. However, there is a very compact O(n) algorithm.

 

Posted at 02:18 PM    

Wed - December 20, 2006

Data Structures Homework for Week 1.  


All questions are taken from Adam Drozdek Data structures and algorithms in C++, Course Technology 2005 (3rd ed.).
This homework does not need to be handed in.

Exercises 2.11

1, 2 a) c) e), 9.

Exercises 4.8

1. a) b) c). 

Posted at 11:37 AM    

©