Definitions and discussion (0-complexity of algorithms discussed: best-average-worst case, doubly linked list, trees, binary trees, binary search trees, AVL, and b-tree. Basic concepts such as complete trees and basic terms such as children, keys, height, should be known. You should be able to identify and create drawings of all such trees and concepts as well.
Review resources
- Handouts / class notes
- Assigned readings in our textbook since Test 1:
- Operator overloading
- Templates [for functions, for classes]
- Pointers and dynamic allocation:
- Linked lists and doubly linked lists:
- Trees :
- b-trees:
- Programming assignments
- Terminology, discussion points, advantages/disadvantages, average/best/worst cases, and practical applications.
Things to be able to code: Linked List: add to front, to middle (as in sorted), or to end, delete from first, from last, or one in the middle, traverse the list to do anything desired to each element.
Binary Search Tree: add a node (in correct location), delete an arbitrary node, delete the entire tree (the proper way), traverse the tree to process the node values in some desired order or in reverse order (can you say "recursion"), copying a tree, Use of C++ default constructor, initializer lists, copy constructor, overloaded assignment operator, destructors.
Algorithms to be able to "show" the use of: add to an AVL tree (any one of 4 cases if imbalance occurs), add or remove an item from a b-tree, conversion of general multi-way trees to first child/next sibling trees.
Terms to be able to define and explain : garbage, dangling reference, scope, lifetime, 3 storage classes (automatic, static and dynamic), pointers, & address-of operator, when to use *& in a parameter list, new, delete, NULL, friend, public, private, p->x notation, (*p).x notation, doubly linked list, stack, queue, tree, binary tree, first child/next sibling tree, expression tree, complete tree (and node densities of these!), AVL tree, b-tree, file data structures (as opposed to main memory data structures), traversals (in-order (e.g. LNR) , pre-order (e.g. NLR), post-order (e.g., LRN)), iterative level-order traversals (with queue) - this is a breadth-first traversal or tree! Complexity of various algorithms to manipulate stacks, queues, linked lists, and trees (such as add, remove, find, etc.); C++ objects on stack or heap, default constructor, abstractions and support for them (declarations and definitions), use of arrays versus linked list versus BST to implement an abstractions of a "list" - comparison of algorithm complexities? Use of C++ templates: how?