ECE 606 - Algorithm Design and Analysis
Instructor
Professor Shreyas Sundaram
Course Description
This course provides an introduction to the analysis and design of algorithms. Emphasis will be placed on rigorous mathematical analysis of complexity, efficiency and correctness. Topics include sorting algorithms, data structures, dynamic programming, graph algorithms, complexity classes (tractability vs intractability of problems), and probabilistic analysis and design of randomized algorithms.
Course Outline
Introduction and Background
- Motivation and overview
- Growth of functions, asymptotic notation, solving recurrence equations
Sorting Algorithms
- Heapsort, quicksort, order statistics
Data Structures
- Stacks, queues, linked lists, hash tables, binary search trees, B-trees
Advanced Design and Analysis
- Dynamic programming
- Greedy algorithms
Graph Algorithms
- Graph representations, searching on graphs
- Spanning trees, shortest paths, maximum flow
Computational Complexity
- Turing Machine model of computation
- Optimization vs. decision problems
- P, NP, coNP, PSPACE, EXPTIME
- Cook and Karp Reductions
- Approximation algorithms
Probabilistic Analysis and Randomized Algorithms
- Introduction to randomized algorithms
- Probability theory and randomized min-cut
- Expected run-time of quicksort
- Markov and Chebyshev Inequalities, randomized median computation
Grading
The final grade for the course will be based on a set of homework problems (approximately four – five assignments total), a midterm exam (date TBA) and a final exam.
Homework:
20%
Midterm:
30%
Final
Exam:
50%
Late turn-in policy
Late homework will not be accepted, unless prior arrangements have been made with the instructor.
Recommended background
Data Structures and Algorithms, Probability, or consent of instructor.
Textbook
There is no required textbook. Parts of the course are based on the following books:
- T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition, 2009
- S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009
- M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2005
- J. Kleinberg and E. Tardos, Algorithm Design, 2005
Papers and electronic references may be made available on the course website.