Algorithm Engineering
Fall 2000 [Continually under revision]
Dr. David W. Matula
(Last update August 19 2000)
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, computational geometry, introduction to problem complexity, survey of NPcomplete problems. Reduction to practice: term project to design, test and validate, illustrate/animate and display results, and measure efficiency of an algorithm implementation.
Prerequisites: CSE3353 and CSE 3358 (For nonmajors: fluency in discrete mathematics and data structures)
Current Textbooks: Introduction to Algorithms by Cormen, Leiserson and Rivest, McGrawHill, 1991, 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 (6 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, decision trees, table lookup, popular algorithm notations, algorithm animation, 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, hash tables, numeric 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, divedandconquer, dynamic programming, backtracking, branchandbound, utilization of design paradigms for problems across application areas of sorting, selection, computer arithmetic and algebraic computation, graphs and networks, computational geometry.
IV. Algorithm Implementation Project (6 classroom hours):
Project description, specifying computational environments, data structure and algorithm selection, test problem design, illustration and algorithm animation, implementation validation, measuring implementation efficiency, result display.
V. Computation Models and Introduction to Complexity (6 classroom hours):
Topics from: Random access machines, parallel machines and algorithms, singleinstruction multipledata, multipleinstruction multipledata, parallel sorting procedures, randomized algorithms, nondeterministic machines, the classes P and NP, NPhard and NPcomplete problems, reducibility, survey of NPcomplete problems, parallel computation and NC.
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

3, 5, 6.1. Review links
cse3353 and cse2353



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

Divide and Conquer

1.3, 4, 8, 10, 31, 32, 35.4

3

Weeks 6,7

Dynamic Programming

16, 26 4


Weeks 8,9,10

EXAM 1





Week 8

[Project Assignment]

23, 27



Weeks 1015

Greedy Algorithms

17, 23, 24, 25

5

Weeks 11, 12,13

NP Theory/Survey

G & J: 1, 3, 6

6

Week 14

FINAL EXAM



Week 15

Fall 2000 Information:
Class location: 0125C
Day and Time: TTH 05:00PM06:20
Tentative Exam Times:
QUIZ (Background) Tuesday August 29 2000.
EXAM I Thursday October 19 2000.
FINAL EXAM Tuesday December 12 2000. (8:00AM to 11:00AM)
Share with your friends: 