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

• definition: G=(V,E), |V| = n; |E|=m;
  • lots of terminology

• representation
  • adjacency matrices
  • adjacency lists
  • compare and contrast

• example operations
  • traversals
    • depth first (DFS)
    • breadth-first (BFS)
  • topological sort of DAG’s
  • cycle detection
    • directed and undirected graphs
  • shortest paths
    • the Warshall-Floyd algorithm
  • graph connectivity
    • directed and undirected graphs
  • spanning trees
    • minimum cost spanning trees

Previous slide

Back to first slide

View graphic version