Welcome to ECE 537 Foundations of Computing, at the Department of Electrical and Computer Engineering at the University of New Mexico. This class focuses on the theoretical foundations of computing. Students will learn about machine models and computability, classification and performance analysis of algorithms, advanced data structures, approximation algorithms, introduction to complexity theory and complexity classes.
The final exam is now available. Please email me to get a copy of it. You get 48 hours from the time you receive it to send it back to me.
Instructor: Pradeep Sen
Class Location: ECE Room 210
Class Time: Tu, Th 12:30 - 1:45pm
Office Hours: Wed 2:00 - 4:00pm
Textbook: Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms, 2nd Edition. The MIT Press, 2003
Recommended Text: Michael Sipser. Introduction to the Theory of Computation, 2nd Edition. Thomson Course Technology, 2006
Complete syllabus is available here. Please read it carefully and let me know if you have any questions.
In this section, we provide the slides and notes for each lecture. Note that
these are not a substitute for coming to class.
| Date | Description | Slides | Notes |
| 8/21/07 | Lecture 1: Introduction, overview of the course, preliminaries in logic | [ pdf ] | [ pdf ] |
| 8/23/07 | Lecture 2: Proof Techniques | [ pdf ] | [ pdf ] |
| 8/28/07 | Lecture 3: Introduction to DFA's | [ N/A ] | [ pdf ] |
| 8/30/07 | Lecture 4: DFA's and regular languages | [ N/A ] | [ pdf ] |
| 9/4/07 | Lecture 5: PDA's and context-free languages | [ N/A ] | [ pdf ] |
| 9/6/07 | Lecture 6: Turing machines | [ N/A ] | [ pdf ] |
| 9/11/07 | Lecture 7: Decidability and Halting | [ N/A ] | [ pdf ] |
| 9/13/07 | Lecture 8: Introduction to P and NP | [ N/A ] | [ pdf ] |
| 9/18/07 | Lecture 9: Reductions and NP-completeness | [ N/A ] | [ pdf ] |
| 9/20/07 | Lecture 10: Cook-Levin Theorem | [ N/A ] | [ pdf ] |
| 9/25/07 | Lecture 11: NP-Complete Algorithms | [ N/A ] | [ pdf ] |
| 9/27/07 | Lecture 12: Algorithms and sorting | [ N/A ] | [ pdf ] |
| 10/2/07 | Lecture 13: Recurrence Relations | [ N/A ] | [ pdf ] |
| 10/4/07 | Midterm | [ N/A ] | [ solns ] |
| 10/9/07 | Lecture 14: Characteristic equation method | [ N/A ] | [ pdf ] |
| 10/11/07 | Fall Break | [ N/A ] | [ N/A ] |
| 10/16/07 | Lecture 15: Characteristic equation method II | [ N/A ] | [ pdf ] |
| 10/18/07 | Lecture 16: Generating functions | [ N/A ] | [ pdf ] |
| 10/23/07 | Lecture 17: Divide and Conquer / Dynamic programming | [ N/A ] | [ pdf ] |
| 10/25/07 | Lecture 18: Matrix Multiplication / Greedy Algorithms | [ N/A ] | [ pdf ] |
| 10/30/07 | Lecture 19: Greedy Algorithms | [ N/A ] | [ pdf ] |
| 11/01/07 | Lecture 20: Amortized Analysis | [ N/A ] | [ pdf ] |
| 11/06/07 | Lecture 21: Amortized Analysis (cont) | [ N/A ] | [ pdf ] |
| 11/08/07 | Lecture 22: Amortized Analysis (cont) | [ N/A ] | [ pdf ] |
| 11/13/07 | Lecture 23: Heap Data Structures | [ N/A ] | [ pdf ] |
| 11/15/07 | Lecture 24: Binary and Leftist Heaps | [ N/A ] | [ pdf ] |
| 11/20/07 | Lecture 25: Binomial, Skew and Lazy Heaps | [ N/A ] | [ pdf ] |
| 11/27/07 | Lecture 26: Fibonacci Heaps | [ N/A ] | [ pdf ] |
| 11/29/07 | Lecture 27: Graph Algorithms | [ N/A ] | [ pdf ] |
| 12/4/07 | Lecture 28: Graph Algorithms | [ N/A ] | [ pdf ] |
| 12/6/07 | Lecture 29: Graph Algorithms and Recap | [ N/A ] | [ pdf ] |
Homework 1 - Available here. The solutions are here.
Homework 2 is available here. The solutions are here.
Homework 3 is available here. The solutions are here.
Homework 4 is available here. The solutions are here.
Homework 5 is available here. It is an optional assignment, so you don't have to do it if you don't want to. It is good practice for the midterm, however.
Homework 6 is now available here. It is due in class on Thursday October 18. The solutions are here.
Homework 7 is simply the last problem of Homework 6 (which we did not do last time). It is due in class on Thursday October 24. You might find these tables helpful. The solutions are here.
Homework 8 is now available here. It is due in class on Thursday November 1. The solutions are here.
Homework 9 is now available here. It is due in class on Thursday November 15. The solutions are here.
Homework 10 is now available here. It is due in class on Tuesday November 27. The solutions are here.