Lab 10 -- Trees

Computer Science 501
Data Structures and Algorithm Analysis

Fall 2014, The College of Saint Rose

Lab 10: Trees
Due: 6:00 PM, Tuesday, November 18, 2014

This lab contains a number of problems related to the tree-related topics we have covered.

You may work alone or in groups of 2 or 3 on this lab. However, in order to make sure you learn the material and are well-prepared for the exam, you should work through the problems on your own before discussing them with your group members, should you choose to work in a group.

Getting Set Up

Create a document where you will record your answers to the lecture assignment and lab questions. If you use plain text, call it "lab10.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab10.pdf" before you submit it.

Lecture Assignment Questions

We will usually discuss these questions at the start of class on the lab due date, so no credit can be earned for late submissions of lecture assignment questions.

LA Question 1: Bailey Problem 12.22, p. 312. (3 points)

LA Question 2: Bailey Problem 13.2, p. 338. (3 points)

LA Question 3: Bailey Problem 13.4, p. 338. (2 points)

LA Question 4: Bailey Problem 13.6, p. 338. (2 points)

Problem Set Questions

Binary Trees

Consider three-node integer-valued binary trees whose nodes contain the elements "1", "2", and "3". We have not yet studied binary search trees in detail but the idea is simple: each node in the tree has values only less than or equal to its value on the left subtree and only values greater than equal to its value on the right subtree.

Question 1: Draw all valid trees whose in-order traversal would visit the nodes in the order 1-2-3. Which of these are binary search trees? (2 points)

Question 2: Draw all valid trees whose preorder traversal would visit the nodes in the order 1-2-3. Which of these are binary search trees? (2 points)

Question 3: Draw all valid trees whose postorder traversal would visit the nodes in the order 1-2-3. Which of these are binary search trees? (2 points)

Binary Min-Heaps

Consider a binary min-heap like the ones we have discussed in class.

Question 4: Which locations in a binary min-heap of n elements could possibly contain the third-smallest element? (2 points)

Question 5: Which locations in a binary min-heap of n elements could possibly contain the largest element? (2 points)

Generalized Heaps

The heaps we have discussed in class, where the heap is represented by a binary tree stored in an array, are one specific case of a more general structure called a d-heap. In a d-heap, each node has up to d children. So the binary heaps we have been considering would be 2-heaps. For the questions below, assume that the minimum value is stored at the root node (i.e., that it is a min-heap). Note: for the parts below where you are to draw a heap, you may submit a hand drawing if you do not wish to use a drawing program.

Question 6: Draw a 2-heap after the following values are inserted: 18, 9, 23, 17, 1, 43, 65, 12. How many comparisons are needed? (2 points)

Question 7: Draw a 3-heap after the following values are inserted: 18, 9, 23, 17, 1, 43, 65, 12. How many comparisons are needed? (3 points)

Question 8: For the heap element at position i in the underlying array of a 3-heap, what are the positions of its immediate chidren and its parent? (Give formulas in terms of i.) (2 points)

Question 9: For the heap element at position i in the underlying array of a d-heap, what are the positions of its immediate chidren and its parent? (Give formulas in terms of i and d.) (2 points)

Question 10: Draw a 1-heap after the following values are inserted: 18, 9, 23, 17, 1, 43, 65, 12. How many comparisons are needed? (3 points)

Question 11: Draw a 7-heap after the following values are inserted: 18, 9, 23, 17, 1, 43, 65, 12. How many comparisons are needed? (3 points)

Huffman Trees

Ignoring case, the string

She sells sea shells down by the sea shore.

has the following character frequencies:

(s,8), (h,4), (e,7), (_,8), (l,4), (a,2), (d,1), (o,2), (w,1), (n,1), (b,1), (y,1), (r,2), (.,1)

Question 12: Construct a Huffman tree based on these frequencies. (6 points)

Question 13: Encode the substring "sea shore shells" using the code specified by your tree. (4 points)

Submitting

Before 6:00 PM, Tuesday, November 18, 2014, submit a PDF of your responses for grading using Submission Box under assignment "Lab10".

Grading

This assignment is worth 45 points, which are distributed as follows:

> Feature	Value	Score
LA Question 1 (12.22)	3
LA Question 2 (13.2)	3
LA Question 3 (13.4)	2
LA Question 3 (13.6)	2
Question 1 (in-order trees)	2
Question 2 (preorder trees)	2
Question 3 (postorder trees)	2
Question 4 (third-smallest min-heap element)	2
Question 5 (largest min-heap element)	2
Question 6 (2-heap drawing and comparisons)	2
Question 7 (3-heap drawing and comparisons)	3
Question 8 (3-heap formula)	2
Question 9 (d-heap formula)	2
Question 10 (1-heap drawing and comparisons)	3
Question 11 (7-heap drawing and comparisons)	3
Question 12 (build Huffman tree)	6
Question 13 (encode with Huffman tree)	4
Total	45