Curriculum for II-year CS&E – Data Science

B. E Computer Science and Engineering –

Program Program Code 24BEDAS
Data Science
Course Design and Analysis of Algorithms Course Code 24BEDAS303
Theory Practical
Semester III Credits 3 Total Hours 45
3 0
COURSE OBJECTIVES:
 Introduce fundamental concepts of algorithms, their performance analysis, and asymptotic
notations.
 Explore the Divide and Conquer paradigm and the Greedy method for problem-solving.
 Understand Dynamic Programming and Backtracking techniques for solving complex problems
efficiently.
 Learn various graph algorithms and understand their applications in real-world scenarios.
 Introduce computational complexity theory and explore approximation algorithms.
Teaching-Learning Process (General Instructions)
 Interactive Lectures: Use presentations, live coding, and case studies to explain concepts.
 Flipped Classroom: Provide pre-recorded tutorials or reading materials before class, focusing
discussions on problem-solving.
 Live Demonstrations: Showcase step-by-step implementation of classic algorithms like Merge
Sort, Dijkstra’s algorithm, and Dynamic Programming solutions.
 Problem-Solving Sessions: Conduct algorithm design challenges where students work in teams to
solve real-world problems.
Module Topics Hours
Introduction to Algorithms and Analysis
Introduction to Algorithms: Importance of Algorithm Design, Fundamentals of
Algorithmic Problem Solving, Characteristics of Good Algorithms.
Mathematical Foundations: Growth of Functions and Asymptotic Notations,
I 9
Summations and Recurrence Relations.
Complexity Analysis: Time and Space Complexity, Asymptotic Notations:
Big-O, Theta, Omega, Best, Worst, and Average Case Analysis.
Empirical and Theoretical Analysis: Techniques for Analyzing Algorithms
Divide and Conquer & Greedy Algorithms
Divide and Conquer: General Strategy, Insertion sort, Selection Sort, Merge Sort,
Quick Sort, Binary Search, Closest Pair Problem, Topological Sort, Finding the
maximum and minimum
II 9
Greedy Algorithm: Characteristics of Greedy Algorithms, Activity Selection
Problem, Huffman Coding.
Graph-based Greedy Algorithms: Minimum Spanning Trees: Kruskal’s &
Prim’s Algorithm, Dijkstra’s Shortest Path Algorithm
Dynamic Programming and Backtracking
III Dynamic Programming Concepts: Principle of Optimality, Overlapping 9
Subproblems, Comparison with Divide and Conquer.

24BEDAS303 - Design and Analysis of Algorithms 1

 Curriculum for II-year CS&E – Data Science

Problems Solved using DP: Fibonacci Numbers, Longest Common Subsequence,

Matrix Chain Multiplication, 0/1 Knapsack Problem.
Backtracking Approach: N-Queens problem, Graph Coloring
Graph Algorithms and Network Flow
Graph Basics: Representation of Graphs, BFS & DFS and their Applications.
Graph Properties and Applications: Topological Sorting Strongly Connected
IV Components. 9
Graph-based Dynamic Programming: Floyd-Warshall Algorithm
Network Flow Algorithms: Max-Flow Min-Cut Theorem, Ford-Fulkerson
Algorithm.
Complexity Theory and Approximation Algorithms
Computational Complexity Theory: P, NP, NP-Complete, and NP-Hard Classes,
Cook’s Theorem, Polynomial-Time Reductions.
V 9
Decision Problems and Optimization Problems: Examples of NP-Complete
Problems, Strategies to Deal with NP-Complete Problems.
Approximation Algorithms: Traveling Salesman Problem (TSP) Approximation
COURSE OUTCOMES:
On successful completion of this course, students will be able to:
 Analyze the efficiency of algorithms using time and space complexity.
 Apply divide and conquer and greedy strategies to solve optimization problems.
 Design and implement algorithms using dynamic programming and backtracking approaches.
 Apply graph algorithms for shortest paths, network flow, and connectivity problems.
 Classify problems into P, NP, and NP-Complete categories and analyze their approximations.
TEXT BOOKS:
 Anany Levitin, Introduction to the Design and Analysis of Algorithms, 3rd Edition (Indian),
2017, Pearson.
REFERENCE BOOKS:
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to
Algorithms, 3rd Edition, MIT Press.
 Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson Education.
 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-Hill Education.
 Michael T. Goodrich and Roberto Tamassia, Algorithm Design and Applications, Wiley.
 Steven S. Skiena, The Algorithm Design Manual, Springer.
E-Learning Sources:
 NPTEL – Design and Analysis of Algorithms (IIT Lectures)
 GeeksforGeeks – Design and Analysis of Algorithms
 HackerRank – Algorithm Challenges
 VisuAlgo – Algorithm Visualization

24BEDAS303 - Design and Analysis of Algorithms 2