COSC 320 - Exam 1 Study Guide

Study Material  Textbook Chapters 3 (3.3, 3.6-3.7), 10, 11, Handouts, Lecture PPTs, Homework, Labs, Programming assignments

Topics:

Notations of O, Ω, Θ

Comparison of constant, logarithmic, linear, polynomial, exponential growths

Theorems of Asymptotic Analysis (be able to prove theorems 1-5)

Definition of best, worst, and average cases

Recursive functions (be able to write recursive function definitions)

Hanoi puzzle using recursion

Master Theorem

Difference between sequence containers and associative containers

Tree Terminology (root, descendent, leaf, interior node, parent, child, edge, path, path length, size of tree, tree level and tree depth)

Binary tree (left and right)

Degenerate tree, complete binary tree, perfect complete binary tree

Evaluating  binary tree density (be able to calculate and prove the maximum number of nodes in a binary tree of depth d, be able to find out the depth of a complete binary tree with n nodes)

Implementing and build of a BT

Recursive tree traversals (LNR, NLR, LRN)

Iterative tree traversal

Implementations of tree traversals (count leaf, find depth, copy tree, delete and clear tree ...)

Binary Search Trees

Operations of BST (build BST, search, remove and insert item)

Test Format

Close book, close notes, and no calculators needed.

There are total no more than 10 problems. Each problem may contain multiple questions

The test questions are similar to the questions given in homework, class discussion problems, and lab assignments.