R25 B.
Tech CSE and Allied Branches Syllabus Balaji Institute of Technology & Science
25CS420PC: ALGORITHM DESIGN AND ANALYSIS
[Link]. II Year II Sem. L T PC
3 0 0 3
Prerequisites: Programming for problem solving and Data Structures
Course Objectives
Develop proficiency in evaluating algorithms using asymptotic notations,
•
including best-, average-, and worst-case time/space complexities, and
solving related recurrence relations.
• Master various algorithmic strategies—divide-and-conquer, greedy, dynamic
programming, backtracking, and branch-and-bound—identifying suitable use
cases and demonstrating their application.
• Critically assess and contrast different algorithms in terms of efficiency,
scalability, and correctness through rigorous analytical reasoning and
empirical evaluation.
• Differentiate between tractable (polynomial-time) and intractable (super-
polynomial or exponential-time) problems;
• Identify and classify problems as P, NP, NP-hard, or NP-complete, and assess
their relationships through polynomial-time reductions and Cook’s theorem.
Course Outcomes
• Explain algorithmic concepts, performance analysis techniques, and asymptotic
notations to evaluate algorithm efficiency.
• Apply divide-and-conquer, backtracking, greedy, and dynamic programming strategies
to solve computational problems.
• Analyze the efficiency of algorithms using disjoint sets, priority queues, and graph
traversal/search techniques.
• Evaluate advanced problem-solving techniques such as branch and bound for
optimization problems like TSP and knapsack.
• Differentiate between P, NP, NP-Hard, and NP-Complete problems, and illustrate the
implications of computational intractability.
UNIT – I
Introduction: Algorithm, Performance Analysis-Space complexity, Time complexity,
Asymptotic Notations- Big oh notation, Omega notation, Theta notation, and Little oh notation.
Divide and conquer: General method, applications-Binary search, Quick sort, Merge sort,
Strassen’s matrix multiplication.
UNIT – II
Disjoint Sets: Disjoint set operations, union and find algorithms, Priority Queue- Heaps,
Heapsort Backtracking: General method, applications, n-queens problem, sum of subsets
problem, graph coloring, Hamiltonian cycles.
R25 B. Tech CSE and Allied Branches Syllabus Balaji Institute of Technology & Science
UNIT – III
Dynamic Programming: General method, applications- Optimal binary search tree, 0/1
knapsack problem, All pairs shortest path problem, Traveling salesperson problem,
Reliability design.
UNIT - IV
Greedy method: General method, applications- Job sequencing with deadlines, knapsack
problem, Minimum cost spanning trees, Single source shortest path problem. Basic Traversal
and Search Techniques: Techniques for Binary Trees, Techniques for Graphs, Connected
components, Biconnected components.
UNIT – V
Branch and Bound: General method, applications - Travelling salesperson problem, 0/1
knapsack problem - LC Branch and Bound solution, FIFO Branch and Bound solution. NP-
Hard and NP-Complete problems: Basic concepts, non-deterministic algorithms, NP - Hard
and NP-Complete classes, Cook’s theorem
TEXTBOOKS:
1. Fundamentals of Computer Algorithms, Ellis Horowitz, Satraj Sahni, and
Rajasekaran, University Press.
REFERENCE:
1. Design and Analysis of algorithms, Aho, Ullman, and Hopcroft, Pearson education.
2. Introduction to Algorithms, second edition, T. H. Cormen, C.E. Leiserson, R. L.
Rivest, and [Link], PHI Pvt. Ltd./ Pearson Education.
3. Algorithm Design: Foundations, Analysis and Internet Examples, M.T. Goodrich and
R. Tamassia, John Wiley and Sons.