EECS 4980 - Algorithms Course Syllabus
Credits/Contact Hours
3 credit hours & 150 minutes lecture contact per week.
Instructor's Name
Dr. Henry Ledgard
Textbook
J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
Course Information
Techniques for devising efficient computer algorithms. Topics include divide-and-conquer
techniques, dynamic programming, linear programming, graph algorithms, greedy algorithms,
NP and P complexity classes, and approximation algorithms for NP complete problems.
Prerequisites: EECS 2520 and EECS 4100
Elective course.
Specific Goals - Student Learning Objectives (SLOs)
Upon the completion of this course, students will be able to:
1. Understand and solve the Stable Matching Problem
2. Become competent at determining Big-O notation for an algorithm
3. Solve problems in Graph Connectivity and Graph Traversal
4. Apply Greedy Algorithms to solve problems such as Interval Scheduling and Optimal
Caching.
5. Use Recurrence Relations to solve problems such as Counting Inversions and Closest
Pair of Points
6. Use Dynamic Programming to solve problems such as Weighted Scheduling and Spell
Checking.
7. Understand and solve the Maximum Flow Problem.
8. Develop approximate solutions to NP and NP-complete problems.
9. Identify the characteristics of problems for which no computational solution exists.
Topics
1. Techniques for Devising Efficient Computer Algorithms
2. Solutions to the Stable Matching Problem
3. Greedy Algorithms
4. Divide-and-Conquer Techniques
5. Solutions for finding the Closest Pair of Points
6. Dynamic Programming
7. Weighted Interval Scheduling
8. Solutions for Optimal Sequence Alignment
9. Network Flow Algorithms
10. Graph Algorithms
11. NP and P Complexity Classes
12. Approximation Algorithms for NP Complete Problems
13. Problems in P-Space