Midterm

Know the following:

• The definition of an algorithm
• Systematic devising of algorithms
• Determine algorithm given outputs
• Big O notation, asymptotic behaviour, conventions
• Determine time complexity and the big O relationship
• Abstract data types, abstraction and why it is useful
• Queues, stacks, sets, and maps: definitions and common operations
• Given a problem, select the appropriate ADT.
• Implement stacks and queues using either an array or a linked list.

Linked lists:

• Singly and doubly linked lists
• Basic linked list operations: insertion, deletion and search
• Array comparision
• Solve a linked list problem such as the removing of duplicates or search, given a class definition.

Trees:

• Define the terms "full tree," "complete tree," "binary tree," and "binary search tree."
• Know how to perform inorder, preorder, and postorder traversal. Write down the order of node visits.
• Draw a resultant BST after operations.
• Define height and its relationship to depth.
• Know the rules of AVL and red-black trees and that they guarantee $\mathcal{O}(\log{N})$ operations.
• Know the pros and cons of each type of tree.
• Given a BST, determine if it satisfies the AVL/red-black ordering rules.
• Given an AVL or red-black tree, draw the resultant tree after inserting or removing one or more nodes.

Heaps and priority queues:

• Know the basic PQ operation time complexities.
• Know heap-ordering rules for min/max heaps.
• Know the operations to insert, delete, bubble up/down, and their time complexities.
• Given an array heap representation, find the parent/child or min/max.
• Draw a resultant heap from operations.
• Draw heap from an array (level-order traversal)
• Insert and remove heap elements.