Computer Science 501

Data Structures and Algorithm Analysis

Fall 2015, The College of Saint Rose

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.

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.

Binary Min-Heaps

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

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.

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)

Submitting

Before 6:00 PM, Wednesday, November 18, 2015, 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 4 (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 | |