PPT Slide

Course outline

Features of C++, object-oriented programming principles, and features of the Unix programming environment will be introduced concurrently with the study of these topics, as appropriate
Review of C++

Introduction to Unix
Review of program performance
• time and space complexity
• asymptotic notation
  -- searching (linear vs binary) & sorting (insertion sort vs mergesort)
Data representation and lists
Stacks and Queues
Hash tables
Binary trees
• representation
• traversal
Priority queues
• Linear lists
• Heaps
Search trees
• Binary search trees
• balanced binary search trees – AVL trees
Graphs
• representation
• traversal

• ADT specification
  • create/ destroy/ isEmpty
  • insert
  • min
  • deleteMin

• implementation
  • linear list -- one of the operations is O(n)
  • binary tree -- a complete tree
    • represented using array
      • O(log n) operations
      • fast implementations (bit-manipulation)

• other operations --
  • max
  • decrease/ increase
  • delete

Previous slide

Next slide

Back to first slide

View graphic version