Course Objectives

The main objective of this course is to introduce students to the fundamental principles and techniques of algorithm design and analysis. The course will cover the following concepts:

• Basic concepts of algorithm analysis, including time and space complexity.
• Various algorithm design paradigms, such as divide-and-conquer, greedy algorithms, and dynamic programming.
• Analysis of common algorithms for sorting, searching, and graph problems.
• Introduction to NP-completeness and approximation algorithms.

Course Outcomes

Upon completion of this course, students will be able to:

1. Analyze the time and space complexity of algorithms.
2. Apply different algorithm design paradigms to solve problems efficiently.
3. Understand and implement common algorithms for sorting, searching, and graph problems.
4. Identify NP-complete problems and apply approximation algorithms when necessary.
5. Design and analyze their own algorithms for specific problems.

Detailed Syllabus

Module 1: Introduction

• Algorithms, Pseudo code for expressing algorithms, Performance Analysis-Space complexity, Time complexity, Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation (Θ) and Little-oh notation (o).

Module 2: Divide and Conquer

• General method, applications-Binary Search, Merge sort, Quick sort, Strassen’s matrix multiplication.

Module 3: Greedy Method

• General method, applications-Job sequencing with deadlines, 0/1 knapsack problem, Minimum cost spanning trees, Single source shortest path problem.

Module 4: Dynamic Programming

• General method, applications-Matrix chain multiplication, Optimal binary search trees, 0/1 knapsack problem, All pairs shortest path problem, Travelling sales person problem, Reliability design.

Module 5: Backtracking

• General method, applications- N Queen problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles.

Module 6: Branch and Bound

• General method, applications-Travelling sales person problem, 0/1 knapsack problem- LC Branch and Bound solution, FIFO Branch and Bound solution.

Module 7: NP-Hard and NP-Complete problems

• Basic concepts, non deterministic algorithms, the classes NP – Hard and NP, NP – Completeness, Cook’s theorem.

Module 8: Approximation Algorithms

• Introduction, Vertex Cover, Travelling Salesman Problem.

Text Books

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
• Fundamentals of Computer Algorithms by Ellis Horowitz & Sartaj Sahni.

Reference Books

• Algorithm Design by Jon Kleinberg and Éva Tardos.
• The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman.

List of Experiments

1. Implement and analyze the time complexities of the following sorting algorithms:
   • Bubble Sort
   • Selection Sort
   • Insertion Sort
   • Merge Sort
   • Quick Sort
   • Heap Sort
2. Implement and analyze the time complexities of the following searching algorithms:
   • Linear Search
   • Binary Search
3. Implement Divide and Conquer technique for:
   • Finding the maximum and minimum element from an unsorted array.
   • Matrix Multiplication
4. Implement Greedy technique for:
   • Job Sequencing with Deadlines
   • Fractional Knapsack problem
5. Implement Dynamic programming for:
   • 0/1 Knapsack problem
   • Finding Longest Common Subsequence
6. Implement Backtracking for:
   • N-Queens problem
7. Implement Graph Traversals:
   • Breadth First Search (BFS)
   • Depth First Search (DFS)
8. Implement:
   • Prim's Algorithm
   • Kruskal’s Algorithm
9. Implement Dijkstra’s Algorithm for finding shortest path.

Course Outcomes

Upon completion of this lab, students will be able to:

1. Implement various algorithms in a programming language like C/C++/Java.
2. Analyze the time and space complexity of implemented algorithms.
3. Compare the performance of different algorithms for the same problem.
4. Choose appropriate algorithms for specific problem scenarios.