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

• a recursive definition
  • root
  • left [sub]tree
  • right [sub]tree

• implementation
  • representation using arrays
    • inefficient, except for complete trees
  • representation using linked structures
  • O(h) time operations (h: height of the tree)

• tree traversals -- recursively defined
  • preorder/ inorder/ postorder
  • each takes O(n) time (n: # elements)

Previous slide

Next slide

Back to first slide

View graphic version