ECE 60800 - Computational Models and Methods

Course Details

Credits: 3

Areas of Specialization:

  • Computer Engineering
  • VLSI and Circuit Design

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 (e-book available through the Purdue Libraries) , 3rd Edition , T. Cormen, C. Leiserson and R. Rivest , MIT Press , 2009 , ISBN No. 0262033844

Recommended Text(s):

  1. Computers and Intractability: A Guide to the Theory of NP-Completeness , Garey, M. R.; Johnson, D. S. , W. H. Freeman , 1979 , ISBN No. 0716710455

Learning Outcomes

A student who successfully fulfills the course requirements will have demonstrated an ability to:

  • Analyze the computational complexity of algorithms for combinatorial problems.
  • Design polynomial time algorithms for combinatorial problems when they exist.
  • Identify NP-Hard combinatorial problems.
  • Provide efficient non-optimal solutions to HP-Hard combinatorial problems

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

Assessment Method:

Weekly graded assessments. (3/2022)