Design and Analysis of Algorithms

This course covers the design and analysis of fundamental algorithms used in practice. It
focuses on three major aspects of algorithms. The first aspect is how to measure the time/space complexity of existing algorithms for basic problems. The worst-case and average-case scenarios will be studied using asymptotic notations such as big-oh, big-omega, and big-theta. The second aspect is understanding well-known paradigms for designing algorithms, including divide-and-conquer, dynamic programming, and greedy approaches. The third aspect covers designing efficient (also known as polynomial-time) algorithms for several fundamental problems
in computer science along with their time complexities. The course also includes complexity theory, where one can observe some decisional problems, referred to as hard problems, for which deterministic polynomial-time algorithms are believed to be intractable.

This course is structured into eight modules. It begins by reviewing essential topics in discrete mathematics in Module 1. Module 2 formally introduces worst-case and average case complexity measurements using various asymptotic notations, and presents algorithms by induction along with different variants of binary search algorithms. Module 3 covers recursion, the divide-and-conquer approach to algorithms, and time complexity using the master theorem. Moving on to Module 4, the course presents various sorting algorithms, comparing their time complexities, and introduces selection algorithms. Module 5 teaches basic graph traversal algorithms such as breadth-first search and depth-first search along with their applications. Module 6 introduces dynamic programming techniques for problem-solving, focusing on problems like the longest-common subsequence, knapsack, and matrix chain multiplication. Module 7 presents a greedy approach for solving problems such as single-source shortest paths and minimum spanning trees. Finally, Module 8 exposes students to complexity classes (P and NP), NP-Hard, NP-Completeness, polynomial-time reduction, and provides the statement of Cook’s theorem.

By the end of this course, students will be able to:

• Understand and apply asymptotic notations to measure the time and space complexity of algorithms in worst-case and average-case scenarios.
• Learn and apply key algorithm design paradigms, including divide-and-conquer techniques, dynamic programming approaches, and greedy techniques, to solve complex problems effectively.
• Implement and analyze graph traversal techniques, such as breadth-first search (BFS) and depth-first search (DFS), and their applications.
• Implement and analyze graph algorithms for real-world problems, such as finding the shortest path and minimum spanning tree.
• Understand complexity classes (P, NP, NP-Hard, and NP-Complete) and polynomial-time reductions.

After completing this course, students should be able to:

• CO1. Explain asymptotic notations and their uses in analyzing the worst-case and average-case time/space complexity. | Know/Knowledge Outcome
• CO2. Demonstrate the time and space complexity of well-known algorithms for sorting, searching, graph problems, matrix multiplication, and polynomial evaluation. | Comprehend Outcome
• CO3. Design and implement efficient algorithms for solving computational problems, such as sorting, searching, and graph-related problems. | Comprehend Outcome
• CO4. Understand the principles behind the divide-and-conquer, dynamic programming, and greedy paradigms, including when and how they can be applied to solve problems. | Comprehend Outcome
• CO5. Comprehend the complexity of problems within different classes (e.g., P vs NP) and understand the implications of NP-Hard and NP-Complete problems. | Comprehend Outcome
• CO6. Apply graph algorithms to solve practical problems like network flow, shortest paths, and minimum spanning tree construction. | Apply Outcome

Attendance: 10%

Quizzes: 30%

Group Assignments: 10%

Mid Semester: 20%

Final Semester: 30%

If p denotes the class attendance (in %), then the corresponding weightage w(p) is calculated as follows:

• A 50-minute lecture will contribute one attendance. If a tutorial is occasionally conducted as a lecture, it will also contribute one attendance. Although the likelihood of this is very low, such instances will be announced in advance.
• Since 80% attendance ensures 10 out of 10, no excuses for missing classes (unless due to a very genuine reason approved by the OAA) will be entertained.
• Your attendance score may be 0 if you do not follow class discipline (see below).

The best three out of four quizzes, each worth 10%, will be counted. If one has taken fewer
than three quizzes and has a genuine reason for this, then either an additional quiz or a viva will be conducted. The exact time for a quiz will be announced through Moodle one week in advance and will be conducted during class/tutorial hours.

Each group will have a maximum of four members. A couple of programming assignments will be assigned to each group, on a module-wise basis. Different modules will carry different weightage, which will be discussed later. Every programming assignment will have a strict
deadline. Failing to meet the deadline will result in a penalty. A group viva, carrying a weightage of up to 5%, will be conducted. Any form of academic misconduct (including plagiarism) will be strictly dealt with.

Obey the following guidelines:

• Electronic gadgets, such as laptops and mobile phones, are strictly prohibited during class or tutorial hours.
• More specifically, these gadgets must not be visible once the class or tutorial starts.
• During class hours, you should have at least one exercise book and one pen.
• You must not enter the classroom if you are more than 10 minutes late. You may leave the class at any time, but once you leave, do not re-enter the class.

• Introduction to Algorithms by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein.
• Introduction to Algorithms: A Creative Approach by Udi Manber

• The Design and Analysis of Computer Algorithms by Alfred Aho, Jeffrey Ullman, and John Hopcroft.
• Fundamentals of Computer Algorithms by Sahni Horowitz.