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 -------------------------
- Partial Quiz 4 Sample Solutions:
Q1-Q3;
Q4;
- B-Tree removal (simple two-pass)
- B-Tree Operations: simple two-pass versions
- Weeks 12, 13:
- Memory Read Latency and CPU Cache
(The experiments I described in class are
reported
here)
- The Unrolled Linked List.
- Relative speeds of traversing an array, standard linked list, and unrolled linked list.
- CPU Cache and B-Trees
- Selection Sort; complexity of Selection Sort
- Pseudocode for Selection Sort (and Insertion Sort);
- Heap Sort: algorithm and complexity ;
- Pseudocode for Heapsort;