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

• dynamic dictionaries -- ADT
  • create/ destroy
  • insert
  • delete
  • find

• implementation using binary trees
  • bst’s --operations are O(h)
    • inorder traversal sorts the elements
  • balanced bst’s -- the AVL tree
    • height is always O(log n)
    • insert/ delete may involve rotations
      • RR/ LL/ RL/ LR

Previous slide

Next slide

Back to first slide

View graphic version