Indian Institute of Information Technology, Allahabad

Design and Analysis of Algorithms

Jan-May 2022 Semester

## Course Information

Course Description: In this course, students deepen their knowledge of the design and analysis of computer algorithms. Advanced topics in algorithms and algorithm analysis covered in the course include algorithmic thinking, complexity analysis, proof of correctness, devide and conquer, searching, sorting, greedy algorithms, string matching and indexing, graphs and graph algorithms, dynamic programming, and complexity classes.

Pre-requisite: Programming and Data Structures

Course Outline (Topics): The following list of topics is tentative. Based on available time slots, some topics may be dropped or added or reordered.

Part 1: Basic Concepts, Definition and Computation of time complexity in asymptotic notations, Heaps, Sorting, Searching, Selection, Hashing Greedy Algorithms - Definition, Designing, Analysis, Proof of Correctness;

Part 2: Dynamic Prograaming - Definiion, Designing, Analysis, Proof of Correctness; Divide and Conquer - Definition, Designing, Analysis; BackTracking Algorithms - Definition, Designing, Analysis;

Part 3: String Algorithms - KMP algorithm, Analysis, Proof of Correctness; Graph Algorithms - Depth First Search, Breadth First Search, Minimum Spanning Trees, Shortest Paths; Complexity Classes - P, NP, Defnitions, NP-hardness and Completeness, Reduction.

## Course Instructor

Dr. Shiv Ram Dubey (Part 3)

## TAs

- BULLA RAJESH - RSI2018007
- SAMBHAVI TIWARI - RSI2018503
- Naman Goel - MIT2020007
- ANUBHAB NANDY - MIT2020043
- SAMIKSHA GUPTA - MIT2020105
- SPANDAN ROY - MIT2021021
- ASHUTOSH NAUTIYAL - MIT2021068
- MONU KUMAR - MIT2021069
- PRATIK BHANKHODIYA - MIT2021076
- DHOTE ANURAG RADHESHAM - MIT2021082
- NEHA - MIT2021083
- RAJESH KUMAR SAH - MIT2021086
- NAGMA NAAZ - MIT2021087
- SAHIL DUBEY - MIT2021088
- YASH PATEL - MIT2021090
- VINAY KUMAR - MIT2021091
- ISHAN SHRIVASTAVA - MIT2021092
- SHASHANK PAL - MIT2021093
- ABHINANDAN KUMAR PUN - MIT2021094
- SANDIPAN DEY - MIT2021095
- TRINETRA DEVKATTE - MIT2021096
- RISHABH MAHENDRA SHIRKE - MIT2021098
- MUTHYAMPALLI AKHIL - MIT2021099
- AMBUJ KUMAR PANDIT - MIT2021100
- GOURAB PAL - MIT2021102
- HIMANSHU JOSHI - MIT2021103
- SHARMA RAVIKANT PRAHLADRAI - MIT2021104

- Class meets
- Class: Monday 09.00 AM - 11.00 AM, Tute: Monday 03.00 PM - 05.00 PM, Lab: Friday 05.00 PM - 07.00 PM

- Course Ethics
- Students are strictly advised to avoid the unethical practices in the course including review tests and practice components.
- It is best to try to solve problems on your own, since problem solving is an important component of the course.
- You are allowed to discuss class material, problems, and general solution strategies with your classmates. But, when it comes to formulating or writing solutions you must work/implement by yourself.
- You are not allowed to take the codes from any source, including online, books, your classmate, etc. in the assignments and exams.
- You may use free and publicly available sources (at idea level only), such as books, journal and conference publications, and web pages, as research material for your answers. (You will not lose marks for using external sources.)
- You may not use any paid service and you must clearly and explicitly cite all outside sources and materials that you made use of.
- Students are not allowed to post the code/report/any other material of course project in public domain or share with any one else without written permission from course instructors.
- We consider the use of uncited external sources as portraying someone else's work as your own, and as such it is a violation of the Institute's policies on academic dishonesty.
- Instances will be dealt with harshly and typically result in a failing course grade.
- Cheating cases will attract severe penalties.

## Schedule

Date | Topic | Class Material | Recorded Lecture |

L01: March 21, 2022 | String Matching Algorithms, FSM, KMP, Trie based Algorithms | Slide (String+Trie) | Recorded Video |

L02: March 28, 2022 | Graphs, DFS and BFS | Slide (Graph, DFS, BFS) | Recorded Video |

L03: March 28, 2022 | Minimum Spanning Tree | Slide (MST) | Recorded Video |

L04: April 04, 2022 | Shortest Paths | Slide (Dijkstra), Slide (Bellman Ford) | Recorded Video |

L05: April 11, 2022 | All-Pairs Shortest Path | Slide (DP+FloydWarshall) | Recorded Video |

L06: April 11, 2022 | Computational Complexity - P, NP, NP-Complete, NP-Hard, Reductions | Slide (Computational Complexity) | Recorded Video |

## Grading

- C1 (30%)
- C2 (30%)
- C3 (40%)

## Prerequisites

- Computer Programming
- Data Structures
- Problem Solving
- Ability to deal with abstract mathematical concepts

## Books/References

**Introduction to Algorithms**by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Third Edition, The MIT Press**Algorithms Design**by Jon Kleinberg and Eva Tardos, Pearson**The Design and Analysis of Algorithms**by A V Aho, J E Hopcroft, and J D Ullman, Pearson**Data Structures and Algorithm Analysis in C (DSAC)**by Mark Allen Weiss, Second Edition**Data structures and Network Algorithms**by Robert Endre Tarjan, Society for Industrial and Applied Mathematics Philadelphia, PA, USA, 1983, ISBN:0-89871-187-8**Knapsack Problems - Algorithms and Computer Implementations**by Silvano Martello and Paolo Toth, John Wiley & Sons, West Sussex, UK, 1990, ISBN: 0471924202

## Disclaimer

The content (text, image, and graphics) used in this slide are adopted from many sources for Academic purposes. Broadly, the sources have been given due credit appropriately. However, there is a chance of missing out some original primary sources. The authors of this material do not claim any copyright of such material.