### CSC 427: Data Structures and Algorithm Analysis Fall 2004 Course Overview

• To appreciate the role of algorithms in problem solving and software design, recognizing that a given problem might be solved with a variety of algorithms. The student should be capable of selecting among competing algorithms and justifying their selection based on efficiency.
• To understand both the specifications and implementations of standard data structures (lists, stacks, queues, linked structures, trees, maps), and be able to select and utilize appropriate data structures in developing programs.
• To develop programs using different problem-solving approaches (divide-and-conquer, backtracking, dynamic programming), and be able to recognize when one approach is a better fit for a given problem.
• To be able to design and implement a program to model a real-world system, and subsequently analyze its behavior.
• To recognize the importance of object-oriented techniques, and be able to utilize inheritance and polymorphism to build upon existing code.

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, ...