1 Content

1.1 Schedule and due dates

1.2 Topical outline

  1. Inspiration, introduction
  2. C++ review
  3. Pointers
    1. Pointer basics, arrays
    2. Pointers and functions, arrays of pointers, pointers to classes
    3. Dynamic memory, dynamic arrays, memory leaks, classes with pointer members, constructors and destructors
  4. Inheritance and polymorphism
    1. Basic inheritance
    2. Polymorphism
  5. Exception handling
  6. Ch1 ADT, big picture on Data Structures
  7. Ch2 Mathematical preliminaries and recursion
    1. Basics of recursion
    2. Recursion(int day){return Recursion(day+=1);}
    3. Backtracking
  8. Ch3 Algorithm analysis
    1. Asymptotic analysis and Big O
    2. Analysis and complexity
  9. Ch4
    1. ADT list and array list
    2. (an aside) Modern C++ std:: iterators, containers, algorithms , std::vector
      • Reading:
        • Read well:
          • http://www.learncpp.com/cpp-tutorial/4-8-the-auto-keyword/
          • http://www.learncpp.com/cpp-tutorial/6-12a-for-each-loops/
          • http://www.learncpp.com/cpp-tutorial/16-1-the-standard-template-library-stl/
          • https://en.cppreference.com/w/cpp/container/vector
        • Skim
          • http://en.cppreference.com/w/cpp/iterator
          • http://www.cplusplus.com/reference/iterator/
          • http://en.cppreference.com/w/cpp/container
          • http://www.cplusplus.com/reference/stl/
          • http://en.cppreference.com/w/cpp/algorithm
          • http://www.cplusplus.com/reference/algorithm/
          • http://www.learncpp.com/cpp-tutorial/15-1-intro-to-smart-pointers-move-semantics/
      • Slides: Content/08b_Modern_Cpp_STL.pdf
      • Code: Content/08b_Modern_Cpp_STL.tar.gz
    3. Linked list
    4. Doubly linked list, free-lists
    5. Stack
    6. Queue
    7. Associative array, dictionary, map (sub-optimally in a list form)
  10. Ch5 and Ch6
    1. General trees, binary trees, traversals
    2. Binary search tree
    3. Heaps
    4. Applications of heaps
  11. Ch7
    1. Internal sorts
    2. Bin sort, Radix sort
  12. Ch8, File processing: caching and external sort (optional topic)
  13. Ch9, Search
    1. Basic search
    2. Hash tables
  14. Ch11, Graph theory
    1. ADT graph
    2. Graph implementations
    3. Traversals: Depth-first search, Breadth-first search
    4. Topological sort, Shortest path
    5. MST
  15. Wrap-up, review
  16. Ch10, Indexing, B-trees (optional topic, likely skip)