UNIQUE SERIES AKTU Syllabus
BCS503BCS503H

Design and Analysis of Algorithm

L-T-P3-1-0 Credits4 Session2024-25 TypeTheory
Appears in 12 semesters · 12 branches

B.Tech Computer Science & Engineering · Sem 5 (Core, code BCS503) · B.Tech Information Technology · Sem 5 (Core, code BCS503) · B.Tech Artificial Intelligence & Machine Learning · Sem 5 (Core, code BCS503) · B.Tech Artificial Intelligence & Data Science · Sem 5 (Core, code BCS503) · B.Tech CSE (Artificial Intelligence) · Sem 5 (Core, code BCS503) · B.Tech CSE (AI & ML) · Sem 5 (Core, code BCS503) · B.Tech CSE (Data Science) · Sem 5 (Core, code BCS503) · B.Tech CSE (Cyber Security) · Sem 5 (Core, code BCS503) · B.Tech CSE (Internet of Things) · Sem 5 (Core, code BCS503) · B.Tech Computer Science & Design · Sem 5 (Core, code BCS503) · B.Tech Computer Science (Hindi) · Sem 5 (Core, code BCS503H) · B.Tech Electronics & Computer Engineering · Sem 5 (Core, code BCS503)

Download PDF

Syllabus

5 units · 40 lecture hours
Unit1

Unit 1: Introduction

8 hrs

Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth of Functions, Performance Measurements, Sorting and Order Statistics - Shell Sort, Quick Sort, Merge Sort, Heap Sort, Comparison of Sorting Algorithms, Sorting in Linear Time.

Unit2

Unit 2: Advanced Data Structures

8 hrs

Red-Black Trees, B – Trees, Binomial Heaps, Fibonacci Heaps, Tries, Skip List

Unit3

Unit 3

8 hrs

Divide and Conquer with Examples Such as Sorting, Matrix Multiplication, Convex Hull and Searching. Greedy Methods with Examples Such as Optimal Reliability Allocation, Knapsack, Minimum Spanning Trees – Prim’s and Kruskal’s Algorithms, Single Source Shortest Paths - Dijkstra’s and Bellman Ford Algorithms.

Unit4

Unit 4

8 hrs

Dynamic Programming with Examples Such as Knapsack. All Pair Shortest Paths – Warshal’s and Floyd’s Algorithms, Resource Allocation Problem. Backtracking, Branch and Bound with Examples Such as Travelling Salesman Problem, Graph Coloring, n-Queen Problem, Hamiltonian Cycles and Sum of Subsets.

Unit5

Unit 5: Selected Topics

8 hrs

Algebraic Computation, Fast Fourier Transform, String Matching, Theory of NP Completeness, Approximation Algorithms and Randomized Algorithms

Course Outcomes (COs)5 outcomes

After completion of the course student will be able to:

  1. CO1Design new algorithms, prove them correct, and analyze their asymptotic and absolute runtime and memory demands.K4, K6
  2. CO2Find an algorithm to solve the problem (create) and prove that the algorithm solves the problem correctly (validate).K5, K6
  3. CO3Understand the mathematical criterion for deciding whether an algorithm is efficient, and know many practically important problems that do not admit any efficient algorithms.K2, K5
  4. CO4Apply classical sorting, searching, optimization and graph algorithms.K2, K4
  5. CO5Understand basic techniques for designing algorithms, including the techniques of recursion, divide-and-conquer, and greedy.K2, K3

Note: The AKTU syllabus PDF of some branches prints this subject with small differences in the books (Electronics & Computer). Please also check the official AKTU PDF of your branch, linked at the end of your semester page.

Text books

  1. Thomas H. Coreman, Charles E. Leiserson and Ronald L. Rivest, “Introduction to Algorithms”, Printice Hall of India.
  2. E. Horowitz & S Sahni, "Fundamentals of Computer Algorithms",
  3. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms” Pearson Education, 2008.
  4. LEE "Design & Analysis of Algorithms (POD)",McGraw Hill
  5. Richard E.Neapolitan "Foundations of Algorithms" Jones & Bartlett Learning
  6. Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
  7. Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Wiley, 2006.
  8. Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins, 1997
  9. Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Addison Wesley, 2011.
  10. Harsh Bhasin,”Algorithm Design and Analysis”,First Edition,Oxford University Press.
  11. Gilles Brassard and Paul Bratley,Algorithmics:Theory and Practice,Prentice Hall,1995.

Official AKTU syllabus

This subject is on page 7 of the original AKTU PDF.

Official AKTU syllabus PDF ↗