Design and Analysis of Algorithms

Monsoon 2003

• Announcements
• General Information
• Schedule and Assignments
• Course Topics
• Assignments

• 2/12/2003: The master method primer is here.
• 9/10/2003: Primers on master method and NP-completeness will be put up soon.

• Instructor: Udayan Kanade, udayan at codito dot com
• Web Page: http://www.codito.com/~udayan/daa/
• Mailing List: coming soon!
• Timings:
• Grading:
  • Assignments (About 10 Assignments)
  • Midterm Examination
  • Final Examination (administered by the University of Pune)
• Other Activities:
  • Scribing lectures
  • Discussion on newsgroup

Following are the topics that we covered (in VIT) this year.

• Introduction to DAA
• Searching
• Sorting (3 lectures)
• Asymptotic Notation
• Knapsack Problem (2 lectures)
• Heaps
• Mergeable Sets
• Optimal Matrix Multiplication Pattern
• Bridge Crossing Problem
• Optimal Binary Search Tree
• Stable Marriage Problem
• Analysis of Quicksort
• Order Statistics
• NP-Completeness
• Master Method
• Minimum Spanning Tree
• Graph Search
• Shortest Path