Credits: 4

​

Brief Description

 

• After completion of this course successfully, the students will be able to:

• CO-1: Assess the inherent structure/hardness of a problem (Evaluate)

• CO-2: Select an appropriate strategy to solve a problem (Understand)

• CO-3 Design an algorithm that suits the time complexity requirements of the problem. (Create)

• CO-4: Estimate the time and space complexities of an algorithm along with the necessary mathematical proofs when necessary. (Evaluate)

• CO-5: Devise algorithms by choosing appropriate data structures (Create)

• Prerequisite Course/Knowledge (If any): Data Structures in under graduate level, discrete mathematical structures, knowledge of sorting algorithms and basic search strategies

 

Preferred Books/Material

 

Books 

 

1. Introduction to Algorithms-T. Cormen, C.E. Leiserson, R.L. Rivest, PHI, 3rdEdition 2009.

2. Algorithms- R. Johnsonbaugh and M. Schaefer, Pearson, 2004.

3. Fundamentals of Algorithmics - G. Brassard and P. Bratley, PH, 1996

4. The Algorithm Design Manual- Steven S. Skiena, Springer, 2009

 

Course Outline: 

 

Here is a preliminary and non-exhaustive list of topics we will be or might be covering. This is subject to change with advanced notice, partly based on the understanding of the students.

 

Lecture Notes

 

• UNIT-I: Analysis of Algorithms:

  • Asymptotic Notation; Best, worst and average case analysis of algorithms; Solving recurrence relations using substitution method, generating functions, Master’s theorem etc. Warm-up to complexity analysis: Heap data structure, priority queue application, Best, worst and average case analysis of a few sorting algorithms like heap sort, insertion, bubble, selection, counting and radix sort algorithms. Strategies for problem solving

 

Course Slides

Slide 1  Slide 2  Slide 3  ​Slide 4 

 

Practice Coding

​Coding 1  Coding 2 Coding 3

 

Theory Assignment

​Assign-1  Assign-2  Assign-3​

​​​​

• UNIT-II: Divide and Conquer strategy:

  • Time complexity analysis for Merge Sort and Quick Sort Algorithms

 

Course Slides

Slide 1  Slide 2  Slide 3  ​

 

Practice Coding

​Coding 1  Coding 2 Coding 3

 

Theory Assignment

​Assign-1  Assign-2  Assign-3

​​​​​

• UNIT-III: Greedy strategy:

  • Theoretical foundation of greedy strategy: Matroids Algorithms for solving problems like Knapsack Problem (Fractional), Minimum Spanning Tree problem; Shortest Paths, Job Scheduling, Huffman’s code etc. along with proofs of corrections and complexity analysis

 

Course Slides

Slide 1  Slide 2  Slide 3  ​

 

Practice Coding

​Coding 1  Coding 2 Coding 3

 

Theory Assignment

​Assign-1  Assign-2  Assign-3

​

• UNIT-IV: Dynamic Programming strategy:

  • Identify situations in which greedy and divide and conquer strategies may not work. Understanding of optimality principle. Technique of memorization. Applications to problems like Coin change, 0/1 and 0/n- Knapsack, Shortest Paths, Optimal Binary Search Tree (OBST), Chained Matrix Multiplication, Traveling Salesperson Problem (TSP) etc.

 

Course Slides

Slide 1  Slide 2  Slide 3  ​

 

Practice Coding

​Coding 1  Coding 2 Coding 3

 

Theory Assignment

​Assign-1  Assign-2  Assign-3

​

• UNIT-V: Backtracking and Branch & Bound strategies:

  • State space tree construction, traversal techniques and solving problems like 0/1 and 0/n knapsack, TSP, Applications of Depth First Search: Topological sorting, Finding strongly connected components and game problems.

​

Course Slides

Slide 1  Slide 2  Slide 3  ​

 

Practice Coding

​Coding 1  Coding 2 Coding 3

 

Theory Assignment

​Assign-1  Assign-2  Assign-3

​

• Programming Enterprise Clouds

  • Introduction, Aneka Architecture, Aneka Deployment, Parallel Programming Models, Thread Programming using Aneka, Task Programming using Aneka, and MapReduce Programming using Aneka, Parallel Algorithms, Parallel Data mining, Parallel Mandelbrot, and Image Processing.

 

Course Slides

Slide 1  Slide 2  Slide 3  ​

 

Practice Coding

​Coding 1  Coding 2 Coding 3

 

Theory Assignment

​Assign-1  Assign-2  Assign-3

​

• UNIT-VI: Theory of NP-Completeness:

  • Complexity classes of P, NP, NP-Hard, NP-Complete, Polynomial reductions, Cook’s theorem. Discussion of problems: Satisfiability(SAT), CNF-SAT, Min-Vertex Cover, Max-Clique, Graph Coloring, NP-Completeness proofs.

​​

Course Slides

Slide 1  Slide 2  Slide 3  ​

 

Practice Coding

​Coding 1  Coding 2 Coding 3

 

Theory Assignment

​Assign-1  Assign-2  Assign-3

​​

Assessments: Internal: 40 Marks

Three internals of 30 marks each (best two will be selected) Lab assignments (10) marks

​​