Algorithm Analysis & Design
Textbook:
Reference books:
|
Introduction to Algorithms, 2nd Edition Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein September 2001, 1202 p. ISBN-10: 0-262-03293-7 ISBN-13:978-0-262-03293-3 Publisher: MIT Press |
Reference books:
|
Foundations of Algorithms using C++ Pseudocode, Third Edition Richard Neapolitan and Kumarss Naimipour, Copyright 2004, 617 p. ISBN-10: 0763723878 ISBN-13: 9780763723873 Publisher: MIT Press |
|
Algorithms Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Copyright 2008, 336 p. ISBN: 0073523402 / 9780073523408 McGraw-Hill |
Schedule :
Announcements:
There are no notices yet!
Homework, Exams, and Grades
As the name of course suggests half of our work throughout the semester will be focused on algorithm design and the other half will be about analysis.
We well study several paradigms of algorithm design including divide and conquer, greedy approach, dynamic programming, and backtracking. For each of
these paradigms we will examine sample problems. For the design portion of the course, your homework is to implement the selected problems form those we
introduce in class, and a few problems which we don’t examine in class but is relevant to, and easy to solve, if you attend carefully to the lectures.
For the analysis part of the course we well have some assignments that you will hand over to me on the deadline which will be announced alongside every homework.
Download the 1st homework by clicking here. Due date: Tuesday October 20, 2009
Download the 2nd homework by clicking here. Due date: Saturday October 31, 2009
Download the 3rd homework by clicking here. Due date: Friday November 27, 2009
Download the 4th homework by clicking here.
Download the 5th homework by clicking here.
Download the 6th homework by clicking here.
Midterm Exam: Saturday 14 Azar, 1388
Final Exam:
Download the 1st homework by clicking here. Due date: Tuesday October 20, 2009
Download the 2nd homework by clicking here. Due date: Saturday October 31, 2009
Download the 3rd homework by clicking here. Due date: Friday November 27, 2009
Download the 4th homework by clicking here.
Download the 5th homework by clicking here.
Download the 6th homework by clicking here.
Midterm Exam: Saturday 14 Azar, 1388
Final Exam:
Grading
Homework and programming assignments: 25%
Midterm exam: 30%
Final exam: 40%
Class participation: 5%
Midterm exam: 30%
Final exam: 40%
Class participation: 5%
Previous Exams
Lecture Slides
Download the first set of slides. In these slides we speak
about what the name of the course means and what we are going to study in this semester.
To be more precise, we speak about the term analysis of algorithms and introduce asymptotic notations.
We also speak some other introductory issues related to algorithm design and analysis.
In this set of slides we start speaking about the first paradigm for algorithm design. Divide and conquer is a recursive approach for solving problems. The first problem we solve using D&C is Maximum Contiguous Subarray.
The third set of slides are uploaded here. We continue our discussion on Divide and Conquer paradigm by introducing Polynomial Multiplication Problem.
The 4th set of slides are uploaded here. The worst case growth rate of some Divide and Conquer algorithms is not that good. Quicksort is an example of such problem. We use Randomization to mitigate this problem. We also solve The Selection problem using Randomized-Partition.
The 5th set of slides are uploaded here. We introduct second paradigm of algorithm design. It is Dynamic Programing. First we examine recursive solution to Fibonacci problem and by it we introduce this paradigm. Next we solve the 0-1 Knapsack Problem using this paradigm.
This handout contains some problems on Dynamic programming. I only examine these problems briefly in case you have any question, and we are not going to study them in class. Please consult the textbook in case you need more explanation on these problems.
The 6th set of slides are uploaded here.
The 7th set of slides are uploaded here.
The 8th set of slides are uploaded here.
The 9th set of slides are uploaded here.
The 10th set of slides are uploaded here.
The 11th set of slides are uploaded here.
The 12th set of slides are uploaded here.
The 13th set of slides are uploaded here.
In this set of slides we start speaking about the first paradigm for algorithm design. Divide and conquer is a recursive approach for solving problems. The first problem we solve using D&C is Maximum Contiguous Subarray.
The third set of slides are uploaded here. We continue our discussion on Divide and Conquer paradigm by introducing Polynomial Multiplication Problem.
The 4th set of slides are uploaded here. The worst case growth rate of some Divide and Conquer algorithms is not that good. Quicksort is an example of such problem. We use Randomization to mitigate this problem. We also solve The Selection problem using Randomized-Partition.
The 5th set of slides are uploaded here. We introduct second paradigm of algorithm design. It is Dynamic Programing. First we examine recursive solution to Fibonacci problem and by it we introduce this paradigm. Next we solve the 0-1 Knapsack Problem using this paradigm.
This handout contains some problems on Dynamic programming. I only examine these problems briefly in case you have any question, and we are not going to study them in class. Please consult the textbook in case you need more explanation on these problems.
The 6th set of slides are uploaded here.
The 7th set of slides are uploaded here.
The 8th set of slides are uploaded here.
The 9th set of slides are uploaded here.
The 10th set of slides are uploaded here.
The 11th set of slides are uploaded here.
The 12th set of slides are uploaded here.
The 13th set of slides are uploaded here.
Teaching Assistants
Morteza Aghamohamadian is my assistant in this course this semester. Below is his nice picture.
He will have problem solution sessions and I strongly advise you to attend those sessions.
The time and place of the sessions will be defined in the first session of our class. Feel free
to contact him via email if you have any question. He is very decent and eager to answer your questions.
 Morteza Aghamohamadian |