Computer Science 210
Data Structures
Fall 2017, Siena College
Lecture 34: Huffman Trees; Maps
Date: Friday, December 8, 2017
Agenda
- Announcements
- still time to sign up for the party on reading day: see the
email from Dr. Flatland, send in your RSVP soon, and be
there
- Check out Robo Show and graphics demos today starting at 11:30 and 12:30
in RB 340 and RB 328!
- Final exam
- practice final exam out
- I have RB 328 reserved so we have will have more space and time
- scheduling a review on Wednesday?
- Lecture 32 assignment recap
- Programming Project 5: Best Of due Monday
- Lab 9: Trees due Monday, but no late penalty
before the final exam if you need the time
- Lab 10/Bonus: Huffman Trees due before the
final exam
- Huffman Trees
- The map/dictionary data structure idea
Lecture 34 Assignment
Due at the start of class, Monday, December 11.
Please submit answers to these
questions by the start of class. zyBook activities should be done
right in your zyBook, and all others should be submitted to
Blackboard under "Lecture 34 Assignment" . We will
discuss these questions at the start of class, so no late
submissions can be accepted.
Read and complete all participation activities in your zyBook, Chapter
17. This is worth 15 points.
Then, answer the questions below in Blackboard.
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)
- Construct a Huffman tree based on these frequencies. (8 points)
- Encode the substring "sea shore shells" using the code
specified by your tree. (6 points)
Terminology
- coding
- fixed-length encoding/variable-length encoding
- prefix-free coding
- Huffman tree/Huffman encoding
Examples