ECE 606 - Fall 2014

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.