Algorithm Engineering
Spring 2004 [Continually under revision]
Dr. David W. Matula
(Last update 8 January 2004)
Catalog Description: Methods for evaluating algorithm efficiency,
data type specification, numeric representation and data structure implementation,
algorithm design paradigms, fundamental algorithm case studies in sorting and
searching, arithmetic and matrix computation, graphs and networks, bio
informatics, computational geometry, introduction to problem complexity, certificates
and verification, survey of NP-complete problems. Reduction to practice: term
project to design, test and validate, illustrate and display results, and
measure efficiency of an algorithm implementation.
Prerequisites: CSE3353 and CSE 3358 (For non-majors: fluency in discrete mathematics and data structures)
Current Textbooks: Introduction to Algorithms, Second Edition by Cormen, Leiserson and Rivest, McGraw-Hill, 2001, Computers and Intractability, by Garey and Johnson, Freeman, 1979
Reference: The Algorithm Design Manual by S.S.Skiena, Springer Telos, 1998
Instructor: David W. Matula
Course Topics:
I. Measuring Algorithm Efficiency (9 classroom hours):
Implementation independent measurement of algorithm efficiency, time and space resources, growth in terms of input size, polynomial vs. exponential growth algorithms, worst and average case efficiency, big Oh notation, algorithm efficiency vs. inherent problem (any algorithm) complexity, certificates, verification algorithms, decision trees, table lookup, popular algorithm notations, deterministic and nondeterministic algorithms, algorithm analysis techniques, induction, recurrence equations, amortization, standards and implementation dependent resource measurement.
II. Data Type Specification and Data Structure Implementation (9 classroom hours):
Tools for algorithm design, abstract data types, selecting data structures, stacks, queues, priority queues, trees, heaps, ROM lookup tables/trees, hash tables, radix, residue and rational number representation, arrays and linked structures, data structure conversion and compression, data structure search and traversal, binary search, balanced data structures.
III. Algorithm Design Paradigms (18 classroom hours):
Characterization of algorithm design paradigms, greedy, dived-and-conquer, dynamic programming, backtracking, branch-and-bound, utilization of design paradigms for problems across application areas of sorting, selection, computer arithmetic and algebraic computation, graphs and networks, bio informatics, computational geometry.
IV. Algorithm Implementation Project (6 classroom hours):
Project description, specifying computational environments, data structure and algorithm selection, test problem design, walkthrough, illustrations, implementation validation, measuring implementation efficiency, result display.
Schedule: The following indicates the general schedule over 15 weeks. The specific times of the exams and due dates of the homeworks will be announced in the class.
The following outlines text readings from Introduction
to Algorithms that should accompany the topics covered in the course. There
is considerable additional material in the text that can not be covered in
class, so in many cases the readings are recommended simply to acquaint you
with the material, and a light reading is all that is suggested. The classroom
discussions and homework assignments will indicate the specific material to
cover in more depth.
|
Topics |
Text Readings by Chapters or Sections |
Homework Set Number |
Dates of Coverage |
|
Discrete Structures Background Material |
--- |
At your leisure |
|
|
Course Overview |
|
|
Week 1 |
|
QUIZ (Background) |
1,2,3,5,6.1,7.1,11 Sample quiz |
|
Week 1 |
|
Algorithm Analysis Tools & Models |
1, 2 |
1 |
Weeks 2,3 |
|
Data Structures for Algorithm Design |
7, 9, 11,12,13, 19, 23, 29 |
2 |
Weeks 4,5 |
|
Greedy Algorithms |
17, 23, 24, 25 |
3 |
Weeks 6,7 |
|
Divide and Conquer |
1.3, 4, 8, 10, 31, 32, 35.4 |
4 |
Weeks 8,9,10 |
|
EXAM 1 |
--- |
--- |
Week 8 |
|
[Project Assignment] |
23, 27 |
--- |
Weeks 10-15 |
|
Dynamic Programming |
16, 26 4 |
5 |
Weeks 11, 12,13 |
|
FINAL EXAM |
|
|
Week 15 |
Spring 2004Information:
Class
location: 0128C
Day and Time: TTH 05:00PM-06:20
Class project assistant:
Tentative Exam Times:
QUIZ (Background) Thursday January 15 2004.
EXAM I .
FINAL EXAM .