Dr. David W. Matula (Last update August 19 2000)

Download 24.23 Kb.
Size24.23 Kb.
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 NP-complete 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 non-majors: fluency in discrete mathematics and data structures)

Current Textbooks: Introduction to Algorithms by Cormen, Leiserson and Rivest, McGraw-Hill, 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, 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, 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, single-instruction multiple-data, multiple-instruction multiple-data, parallel sorting procedures, randomized algorithms, nondeterministic machines, the classes P and NP, NP-hard and NP-complete problems, reducibility, survey of NP-complete 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.



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


Weeks 2,3

Data Structures for Algorithm Design

7, 9, 11,12,13, 19, 23, 29


Weeks 4,5

Divide and Conquer

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


Weeks 6,7

Dynamic Programming

16, 26 4


Weeks 8,9,10




Week 8

[Project Assignment]

23, 27


Weeks 10-15

Greedy Algorithms

17, 23, 24, 25


Weeks 11, 12,13

NP Theory/Survey

G & J: 1, 3, 6


Week 14




Week 15

Fall 2000 Information:
Class location: 0125C

Day and Time: TTH 05:00PM-06: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)


Download 24.23 Kb.

Share with your friends:

The database is protected by copyright ©ininet.org 2024
send message

    Main page