1.
Department of Computer Science &
Information Technology
Course Description Form (CDF)
Course Information
Course Code: CS-09232 Course Title: Design and Analysis of Algorithms
Credit Hours: 3(3, 0) Lecture Hours/Week: 3
Lab Hours/Week: 0 Pre-Requisites:CS3xx-Data Structures &Algorithms
Course Objective
To understand the fundamentals of algorithms;
To analyze algorithm efficiency;
To apply algorithm design techniques;
To evaluate algorithms for correctness and optimality;
Course Content
This course is designed to provide a comprehensive understanding of the principles, design techniques, and
analysis of algorithms. Topics include: Introduction to Algorithms, Properties and Importance of Algorithms,
Time Complexity Analysis, Asymptotic Notations (Big O, Omega, Theta), Recursion and Recurrence
Relations, Master Theorem, Sorting and Searching Algorithms, Divide and Conquer, Greedy Algorithms,
Dynamic Programming, Graph Algorithms (DFS, BFS, Minimum Spanning Tree, Shortest Path), Heaps, Loop
Invariants, and Complexity Classes (P, NP, NP-Complete, NP-Hard). Students will apply these techniques to
solve computational problems and evaluate algorithms for correctness and efficiency.
Unit wise Major Topics:
No. of
Unit Topic Teaching
Hours
Introduction to Algorithms:
1 Overview of algorithms, their importance, and fundamental properties. 3
Discussion on time and space complexity and their significance.
2 Brute Force (BF) Technique: Designing Algorithms for Primality 3
Testing and Sorting problem and 0-1 Knapsack Problems
Analysis of Algorithms:
3 Computation of the running time of simple algorithms with practical examples. 10.5
RAM Model, Worst, Best & Average Case Behavior of Algorithms; Complexity
Classes, Asymptotic Notations: Big O, Omega and Theta Notations
Sorting Algorithms Analysis:
Detailed analysis of Insertion Sort, Bubble Sort, and Selection Sort algorithms,
including their working principles, time complexity, and performance evaluation
Solving Recurrence Relations: Substitution Method, Recurrence Tree Method,
Master Method and Time & Space Tradeoffs.
Divide and Conquer Approach
4 Merge Sort algorithm and its Analysis 3
Quick Sort Algorithm and Analysis
Quick Sort and Pivot Variation
5 Heaps: MaxHeapify, BuildMaxHeap, MinHeap and Heap Sort & Analysis 4.5
6 Correctness of Algorithms: Pre-conditions, Post-conditions, Loop Invariant, 3
Correctness of Iterative Loop Invariants solved with examples
1
Greedy Algorithms
7 Huffman Coding 6
Activity Selection Problem.
Dynamic Programing
Assembly Line Scheduling problem
Longest Common Subsequence Problem
Graphs & Trees
8 6
Terminologies related to Graph
Breath First Search
Depth First Search
Graph Shortest Path Algorithms
Shortest Path. Djikstra’s Algorithm
Shortest Path Bellman Ford Algorithm
Minimum Spanning Tree (MST)
9 3
Prim’s Algorithm
Kruskal’s Algorithm
Introduction to P, NP, NP -Complete set of problems
10 3
Mapping of CLOs and GAs
Blooms
Sr.# Unit # Course Learning Outcomes Taxonomy GA
Learning Level
Demonstrate an algorithmic approach to a given
CLO-1 1-2 problem. Understanding 2
Analyze the time complexity of iterative and recursive
CLO-2 3-5 algorithms Analyzing 3
Prove correctness of an algorithm using loop invariant
CLO-3 6 Evaluating 3
Apply appropriate algorithmic design techniques to
CLO-4 7-9 solve computational problems Applying 3
Explain the concept of various complexity classes
CLO-5 10 with examples Understanding 2
CLO Assessment Mechanism
Assessment
CLO-1 CLO-2 CLO-3 CLO-4 CLO-5
Tools
Quizzes Quiz 1 Quiz 2 Quiz 3 Quiz 4
Assignment-1
Assignments Assignment-2 Assignment-3&4
Mid Term Mid Term Mid Term
Exam - -
Exam Exam
Final Term
Final Term Exam CLO-3, CLO-4, CLO-5
Exam
2
Text and Reference Books
Textbook:
1. Introduction to algorithm 3rd edition.
Reference Book:
Introduction to algorithm 3rd edition T.H Cormen & other.