ECE 60800 - Computational Models and Methods

Credits: 3

Areas of Specialization(s):

VLSI and Circuit Design
Computer Engineering

Counts as:

Normally Offered: Each Fall, Spring

Catalog Description:
Computation models and techniques for the analysis of algorithm complexity. The design and complexity analysis of recursive and non-recursive algorithms for searching, sorting, set operations, graph algorithms, matrix multiplication, polynomial evaluation and FFT calculations. NP-complete problems.

Required Text(s):
  1. Introduction to Algorithms, 3rd Edition, T. Cormen, C. Leiserson and R. Rivest, MIT Press, 2009, ISBN No. 0262033844.

Recommended Text(s): None.

Lecture Outline:

Weeks Topic
1 Time and space complexity; analysis methods
2.5 Models of computation Turing machine
2.5 Recurrence formulas, discrete mathematics
1.5 Sorting
1.5 Search; Set Operations
2 Graph Algorithms
1 Polynomial, matrix and FFT algorithms
2 NP-complete problems