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.
<![CDATA[
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, ...
]]>