CSE 830:
Design and Theory of Algorithms

Fall 2009

Instructor: Dr. Charles A. Ofria
Office: 2140 Engineering
Phone: 355-8389
E-mail: ofria@cse.msu.edu
Textbook: Introduction to Algorithms, Second Edition by Cormen, Leiserson, Rivest, and Stein, McGraw Hill, 2001 ISBN 0-07-013151-1
Meeting time & Room: Tu/Th 10:20-11:40am, 1300 Engineering Building
Office Hours: TBD (in the meantime, by appointment).
Pre-reqs: Knowledge of at least one major programming language, basic data structures, and recursion.
Web page: http://www.cse.msu.edu/~cse830/

Description: Analysis of algorithms. Algorithm design techniques. Efficient algorithms for classical problems. Intractable problems and techniques to handle them.

Handouts

  • Basic Info
  • Schedule
  • Sample Exam I
  • Sample Exam II
  • Sample Final

    • Homework

  • Homework 1
  • Homework 2
  • Homework 3
  • Homework 4
  • Project
  • Homework 5

    • Lectures

  • Week 1 - Introduction
  • Week 2, part 1 - Analysis Tools
  • Week 2, part 2 - Recurrence Relations
  • Week 3, part 1 - Data Structures
  • Week 3, part 2 - Sorting
  • Week 4, part 1 - Quicksort
  • Week 5, part 1 - Optimization Problems
  • Week 5, part 2 - Dynamic Programming Examples
  • Week 6, part 1 - Workshop: Dealing with Hard Optimization Problems
  • Week 6, part 2 - Review
  • Week 7, part 1 - Exam
  • Week 7, part 2 - Canceled
  • Week 8, part 1 - Introduction to Graph Theory
  • Week 8, part 2 - Basic Graph Theory Algorithms
  • Week 9, part 1 - Algorithms on Weighted Graphs
  • Week 9, part 2 - Workshop: Dealing with Hard Graph Problems
  • Week 10, part 1 - Approximation techniques; Rules for dealing with hard problems.
  • Week 10, part 2 - Special Topic: Bit Magic