Computer Science 501
Data Structures and Algorithm Analysis

Fall 2015, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
• Lab 7: The Two Towers Problem [HTML] [PDF] recap
• Lab 8: P.S.: It's Just a Stack [HTML] [PDF] recap
• Lab 9: Best Of [HTML] [PDF] due now
• Lab 10: Trees [HTML] [PDF] out: no programming!
• Binary tree example: Huffman trees
• Array representation of trees
• Priority queues
  • Vector-based implementation
  • heaps
  • heap-based priority queue
• Heapsort

Readings and References

• Bailey Ch. 13.

Terminology

• Huffman coding
• balanced tree
• priority queue
• heap/min-heap/max-heap
• heapsort
• skew heap