Computer Science 501
Data Structures and Algorithm Analysis

Fall 2014, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
• Midterms back, and statistics about scores
• Lab 7: The Two Towers [HTML] [PDF] due (except parts due next week)
• Linked structures
  • simple singly-linked
    • complexity of public operations
    • iterator
    • adding a count
    • adding a tail pointer
  • circular
    • complexity of public operations
    • iterator
  • doubly-linked
    • complexity of public operations
• Linear structures
  • stacks
    • array-based
    • Vector-based
    • List-based
    • comparisons
  • queues
    • List-based
    • Vector-based
    • array-based
  • why these restricted structures?
• Lab 8: P.S.: It's Just a Stack [HTML] [PDF] out

Readings and References

• Bailey Ch. 9, 10.

Terminology

• lists
• linear structure
• linked list
• singly linked list
• circular linked list
• doubly linked list
• stack
• queue
• push/pop
• call stack
• heap
• enqueue/dequeue
• depth first search
• breadth first search

Examples

• SimpleLinkedList
• BinSearch
• MazeRunner