# Design and Analysis of Algorithms Fall 2015

## Course Information

Class meetings | Tue-Wed 11:45PM – 1:15PM in LT4 |

Pre-requisites | Knowledge of basic concepts in mathematics and data structures is assumed (e.g. sets, functions, probability, proof by induction, permutations, logarithms, and the basics of solving recurances, graphs, trees). |

Required text | Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani Algorithms |

Reference text | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms |

## — Bulletin Board —

Date | News | |
---|---|---|

Jan 30 |
Here is the solution for Quiz # 8 | |

Jan 30 |
Here is the solution for Quiz # 7 | |

Jan 30 |
Here is the solution for Quiz # 6 | |

Jan 30 |
Here is the solution for Quiz # 5 | |

Jan 30 |
Here is the solution for Homework # 5 | |

Jan 30 |
Here is the solution for Homework # 4 | |

Dec 26 |
Here is the Homework # 5. Deadline for submission is Jan 6, 2016 | |

Dec 21 |
Here is the Solution for Homework # 3 | |

Dec 18 |
Here is the Homework # 4. Deadline for submission is Dec 23, 2015 | |

Dec 8 |
Here is the Homework # 3. Deadline for submission is Dec 15, 2015 | |

Nov 26 |
Here is the Solution for Homework # 2 | |

Nov 24 |
Here is the Solution for Quiz # 4 | |

Nov 19 |
Here is the Solution for Quiz # 3 | |

Nov 15 |
Here is the Solution for Quiz # 2 | |

Nov 15 |
Here is the Solution for Quiz # 1 | |

Nov 12 |
Here is the Homework # 2. Deadline for submission is Nov 18, 2015 | |

Nov 1 |
Lecture # 7 and 8 Notes Uploaded (See Below) | |

Oct 26 |
Lecture # 5 and 6 Notes Uploaded (See Below) | |

Oct 23 |
Solution of HW# 1 | |

Oct 18 |
Lecture # 4 Notes Uploaded (See Below) | |

Oct 18 |
Lecture # 3 Notes Uploaded (See Below) | |

Oct 15 |
Here is the Handout for better understanding of solving recurrence relations. | |

Oct 14 |
Here is the Homework # 1. Deadline for submission is Oct 21, 2015 | |

Oct 11 |
Lecture # 2 Notes Uploaded (See Below) | |

Oct 9 |
Lecture # 1 Notes Uploaded (See Below) | |

Oct 6 |
Intro Class |

## Policies

#### Grading

There will be 6-10 homeworks, 6-10 in-class quizzes, presentations, some lecture notes and two exams. The grade break down will be as follows:
Note : Final grades will be curved. |

The homework assignments are mathematically oriented and involve derivations of mathematical equations, and proofs of statements. |

Students can form groups of up to two for the purposes of homework. Homework is to be done independently within each group. Each group should understand and be able to explain the answers submitted. Each group should turn in one assignment, clearly marked with group-member names. Once you form a group, it can’t be changed. |

NO LATE HOMEWORKS WILL BE ACCEPTED. |

To fairly account for natural disasters and emergencies, everyone is allowed to skip one homework and one quiz. If you choose to solve all homeworks(quizzes), your homework(quiz) with the least score will be discarded while computing your final grade. |

25% credit will be given for any question for clearly marking the question with “I DON’T KNOW”. Questions with an entirely wrong answer will get 0% credit, but a partially correct answer will get partial credit. So if u don’t have any idea about a problem, it’s better for you to admit that you don’t know something, rather than trying to fake it. But, if you have some idea, but its not entirely correct but is partially correct, you should show your partial solution |

#### Academic dishonesty

Under the Honor Code, each of you is expected to submit your own work in this course. However, as outlined above, for the homework submissions, you are allowed to work in groups or to ask for general advice from the course staff or other experts. Such activity is both acceptable and encouraged, but you must indicate any collaboration or assistance on your solution sets. . |

Any collaboration or assistance that is not given proper citation may be considered a violation of the Honor Code. . |

You are responsible for understanding and being able to explain the solutions you submit. |

In case of plagiarism you may receive an ‘F’ grade in this course along with penalties dictated by university policy. The course staff will actively pursue any suspected cases of Honor Code violations. |

#### Homework Submission

Use standard 8 by 11 sheets of paper with no ragged edges.. |

Your group name should appear at the top of each page. Pages should be numbered and stapled together. . |

You should have a cover page that gives your name and a table with three columns. The first column lists each of the assigned problems in the order that they appear on the assignment (whether you did them all or not). The second column contains the number of the page of your work where the solution to the problem appears (or the words “Not done” if you did not do it.) The third column is left blank for me to record the score. |

Submissions in TeX is mandatory |

## Topics

# | Topic | Notes | |
---|---|---|---|

1 | Intro to Algorithms | (PDF) (TeX) | |

2 | Puzzle 3.1 | (PDF) (TeX) | |

3 | Find Kth Smallest Element in a List | (PDF) | |

4 | Solving Recurrences | (PDF) | |

5 | Divide and Conquer | (PDF) | |

6 | Puzzle 4.0 | (PDF) | |

7 | Revisiting Selection Problem | (PDF) | |

8 | Some Sorting | (PDF) | |

9 | Heap Sort | (PDF) | |

10 | Counting Sort | (PDF) | |

11 | Lecture 11 | (PDF) | |

12 | Lecture 12 | (PDF) | |

13 | Lecture 13 | (PDF) | |

14 | Lecture 14 | (PDF) | |

15 | Lecture 15 | (PDF) | |

16 | Lecture 16 | (PDF) | |

17 | Data Structure Algorithms | (PDF) | |

18 | Spanning Trees | (PDF) | |

18 | Spanning Trees | (PDF) | |

19 | Shortest Path Algorithms | (PDF) | |

20 | Data Compression | (PDF) | |

21 | Huffman Coding | (PDF) | |

22 | Network Flow Problem | (PDF) | |

23 | NP and NP-Complete: | (PDF) | |

24 | NP Hardness | (PDF) | |

25 | NP Hardness and Reductions | (PDF) | |

26 | Approximation Algorithms | (PDF) | |

26a | Approximation Algorithms | (PDF) |