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
Campus/Online:
On-campus and online
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):
- 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):
- 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)