MA30207: Design And Analysis Of Algorithms
| MA21007 | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Design And Analysis Of Algorithms | ||||||||||||||||||||||||||||
| Offered by | Mathematics | ||||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||||
| L-T-P | 3-1-0 | ||||||||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
| Semester | Autumn | ||||||||||||||||||||||||||||
Syllabus
Syllabus mentioned in ERP
Prerequisite: Programming and Data Structures Basic concepts of algorithms, Complexity, Asymptotic notations, Trees: Binary tree, Binary Search Tree, Tree traversals. Heap as data structure. Basic sorting algorithms: selection sort, insertion sort. Greedy algorithms: Coin change problem, activity selection, Minimum Spanning Tree, Single source shortest path, knapsack problem. Divide – and – Conquer technique: Merge sort, quick sort. Solving Recurrence relations. Dynamic programming: matrix chain multiplication, all pair shortest path algorithm, 0-1 Knapsack. Graph algorithms: Warshall’s algorithm, Depth First Search, Breadth First Search. Height Balanced Tree. Branch and Bound technique, Backtracking. NP completeness.
Concepts taught in class
Data Structures - Trees, Graphs, Heaps, Hash Tables; Sorting Algorithms; Graph Algorithms - Minimum Spanning Tree, Dijkstra, Depth-First Search, Breadth-First Search, Floyd-Warshall etc.; Greedy Algorithms; Dynamic programming; Asymptotic analysis
Student Opinion
| Course content similar to any basic DS-Algo course such as Algorithms-I offered by the CSE Department, with examinations and grading being considerably easier. Prof. Sourav Mukhopadhyay is a genuinely helpful professor, who has no qualms in repeating each topic multiple times till one understands it. Final opinion - Take this course as an additional only if you want to get done with the least effort put in. Otherwise, would recommend Algorithms-I any day. |
How to Crack the Paper
| Most questions in the mid-semesters and end-semesters are repeated from previous year papers, so having a look at those is recommended. Some questions are asked from the MIT-OCW assignment questions too |
Classroom resources
The teaching style is eerily similar to the course offered by Stanford, while slides are exactly the same. Any standard DS Algo book will do, eg: Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
Additional Resources
Practice solving problems on online platforms such as Codechef, Hackerrank, Leetcode, InterviewBit to get a good grip on the subject.
Time Table
| Day | 8:00-8:55 am | 9:00-9:55 am | 10:00-10:55 am | 11:00-11:55 am | 12:00-12:55 pm | 2:00-2:55 pm | 3:00-3:55 pm | 4:00-4:55 pm | 5:00-5:55 pm | |
|---|---|---|---|---|---|---|---|---|---|---|
| Monday | NR312 | |||||||||
| Tuesday | ||||||||||
| Wednesday | NR312 | NR312 | ||||||||
| Thursday | ||||||||||
| Friday |