CSC 427: Data Structures and Algorithm Analysis
Fall 2004

Course Overview

Object-Oriented Programming class design interacting classes, private data fields & public member functions private member functions, templated classes and functions inheritance private vs. protected, overriding member functions, polymorphism abstract class, virtual member functions Data Structures previous structures: array, vector, stack, queue, Matrix dynamic memory new, delete, pointer manipulation destructor, copy constructor, operator= lists and iterators list class: front, push_front, pop_front, back, push_back, pop_back, empty, clear, begin, end, insert, erase doubly linked list implementation iterator class: *, ++, -- <algorithm> library: find, binary_search, random_shuffle, sort, ... trees and non-linear structures binary search tree binary tree implementation, tree recursion, binary search AVL tree: variant on binary search tree, ensures O(log N) tree height heap complete binary tree, heap property, vector implementation priority queue application, heap sort associative containers set class: insert, find, erase, empty, size, begin/end balanced binary search tree implementation map class: operator[], find, erase, empty, size, begin/end balanced binary search tree implementation hash table implementations (hash_set and hash_map) hash function, collisions, clustering, load factor, rehashing linear probing vs. quadratic probing vs. chaining Algorithm Analysis big-Oh notation formal definition, rate-of-growth analysis, asymptotic behavior searching & sorting sequential search vs. binary search insertion sort vs. selection sort vs. merge sort recursion base case(s), recursive case(s), analysis via recurrence relation algorithmic approaches divide&conquer: binary search, merge sort, tree algorithms, ... greedy: optimal change with U.S. coins, job scheduling, ... backtracking: N-queens, blob count, boggle search, ... dynamic: optimal change, binomial coefficient, ...