## Topics, Examples, Algorithms and Code Examples

• Week 1:
• Intro to course.
• Stacks and very simple "partially-filled array" implementation.
• Stack examples (with exercises): Parenthesis Checking; Checking Grouping Symbols.
• C++ Code Example: Basic Array-based Stack-of-Ints Class:
• Queues and (abstract) implementation with "circular" array;
• Queue examples: round-robin scheduling;
• Example: Palindrom Checking with a stack and queue;
• Array-based Queue-of-Ints class;
• Code Example: Basic Queue Implementation.
• Week 2:
• Big-Oh notation: especially O(1) and O(n).
• Dynamic Data Structures (DDS)
• Abstract linked lists (Text: Section 3.1 and 3.2);
• Abstract linked list implementation of stack.
• C++ addresses, pointers and arrays;
• Code Examples:
• --------- QUIZ 1 CUT-OFF ------------
• The call stack; Peeking at the call stack;
• Code Examples:
• Memory allocation on stack vs heap (dynamic memory), and the new operator;
• Accessing object members in C++;
• Week 3:
• Code Example: Dynamic (linked list) imlementation of basic stack class. (Notice that you use the same test program as used for the non-dynamic array-based stack, with no changes.)
• Linked list implementation of Queue.
• Exercise: Make a Dynamic (linked list) implementation of the basic int-queue class. Start from the header and test program from Week 1.
• QUIZ 1 (Monday Jan. 22).
• Weeks 4, 5:
• Basics of graphs and trees: (Text: Chapter 7)
• Graph terms: path (sequence of vertices); path length (number of edges); connected; cycle; tree (connected and acyclic).
• Rooted tree terms: root, leaves, internal nodes, parent, child, ancestor, descendent, node depth.
• Priority Queue ADT; complexity of operations for naive implementations (ordered and un-ordered arrays and linked lists).
• Binary tree terms: left/right child, proper, perfect, complete;
• Binary Heap data structure:
• "shape invariant"
• "order invariant"
• --------- QUIZ 2 CUT-OFF ------------
• QUIZ 2 (Monday Feb. 5).
• Weeks 6,7,8:
• Heaps:
• Level-order traversal of a binary tree;
• Complexity Analysis:
• number of nodes in a perfect binary tree;
• height vs number of nodes for complete binary trees;
• complexity of insert and extract-min;
• Big-Omega and Big-Theta.
• Lower bound on heap insert and extract-min algorithms.
• Number of nodes at depth d in a perfect binary tree;
• Complexity of make-heap (making a heap from scratch);
• Assignment 2 concepts: Deep copies; copy constructors; deconstructors;
• Recursion: (Text: Section 3.5)
• Recursive function definitions (mathematical and in programs)
• Example: computing S(n) recursively.
• --------- QUIZ 3 CUT-OFF ------------
• Recursion:
• Example: recursion on lists (sum)
• Tree of recursive calls (e.g., for Fib(n)), when there are two recursive calls.
• Recursion on binary trees: computing height and number of nodes recursively.
• Binary Tree Traversals: pre-order, in-order, post-order (recursively defined);
• Quiz 3.
• Weeks 9,10,11:
• Dynamic Set ADT.
• Binary Search Trees (order invariant; in-order traversal).
• BST: Operations insert, search (aka find or lookup), erase (aka remove or delete) (including iterative and recursive algorithms for pred(v)).
• BST: effect of insertion order on tree structure; complexity of operations in terms of height and number of nodes.
• Pseudo-code for BST operations
• m-ary search tree and generalization of in-order traversal
• B-Tree (def'n of order-m B-tree);
• Height of B-Tree with n nodes (big-Oh);
• B-Tree search;
• ------- Quiz 4 Cut-off -------------------------
• B-Tree insertion (simple two-pass)
• B-Tree removal (simple two-pass)
• B-Tree Operations: simple two-pass versions