CSE 326 Autumn 2001

Homework Assignment 2

Due:

Friday, October 26

Readings:

Weiss Chapters 3, 4

Note:

Unless specified otherwise, write your algorithms in pseudocode, following the course pseudocode guidelines.

Problems:

1. Weiss 3.5, list splicing. Write the functions in C++.

2. Weiss 3.9, list intersection.

3. Linked-list polynomial multiplication, take 2.

1. Weiss 3.12(a).

2. Which part of the algorithm were we neglecting when we (including me!) so flippantly concluded in class that linked-list polynomial multiplication could be done in O(m*n) time?

4. Write a non-recursive algorithm to reverse a singly-linked list in place, i.e. without creating and copying out to a new list (this is Weiss 3.17(b)). What is the time complexity of your algorithm?

5. Show how to implement a queue using two stacks. You may use pseudocode or a clear description with diagrams. What is the time complexity of the queue operations?

6. Show how to implement a stack using two queues. You may use pseudocode or a clear description with diagrams. What is the time complexity of the stack operations?

7. Weiss 4.6, numbers of full nodes and leaves in a binary tree. (It may help to first prove the result in Weiss 4.4.)

8. Weiss 4.10, average numbers of nodes and leaves in a BST.

9. Weiss 4.27 and 4.28, splay tree operations.

10. Weiss 4.26, function for efficient AVL tree double rotation. Write the function in C++.

11. Weiss 4.37, function for BST range searching. Write the function in C++.

12. Extra credit Weiss 4.47 (a) and (b), BST transformations.