Sidho-Kanho-Birsha University
Syllabus & Course Curriculam
Syllabus (COMPUTER SCIENCE)
Course Type: MAJ-6
Semester: 5
Course Code: BCOSMAJ06C
Course Title: Design and Analysis of Algorithm
(L-P-Tu): 4-2-0
Credit: 6
Practical/Theory: Combined
Course Objective: 1. To understand the role, characteristics and need of algorithms. 2. To understand the classification
strategies of algorithms and recursive algorithms.
Learning Outcome: 1. Ability to analyze asymptotic runtime complexity of algorithms including formulating recurrence
relations. 2. Ability to understand and design algorithms using greedy strategy, divide and conquer approach, dynamic
programming, Demonstrate a familiarity with major algorithms and data structures.
Theory
Introduction:
Analysis of Algorithms: Insertion Sort, Merge Sort, Time and Space Complexity, Growth of Functions: Asymptotic
Notation, Recurrences: Substitution, Iteration, Master Method. (10 Lectures)
Divide and Conquer Algorithms:
General method, Quicksort, Randomized Algorithms, Applications-Analysis of Binary Search, Heap Sort, Matrix
Multiplication. (10 Lectures)
Greedy Algorithms:
Introduction to Greedy Strategies, Minimum Spanning Tree: Kruskal’s Algorithm, Prim’s Algorithm, Huffman
Coding. (8 Lectures)
Dynamic programming:
Principles Of Dynamic Programming, Memorization and Tabulation Techniques, Knapsack Problem, Matrix Chain
Multiplication, Longest Common Subsequence. ( 10 Lectures)
Graph Algorithms:
Graph Traversal: BFS And DFS, Topological Sort, Strongly Connected Components, Single-Source Shortest Paths:
The Bellman-Ford Algorithm, Dijkstra’s Algorithm, All-Pairs Shortest Paths: The Floyd-Warshall Algorithm. (12
Lectures)
Introduction to Complexity Theory:
Basic Concepts, Non-Deterministic Algorithms, NP-Hard And NP-Complete Classes, Cook‘s Theorem. (10 Lectures)
DESIGN AND ANALYSIS OF ALGORITHMS LAB
1. Write a program to perform Insertion Sort, Merge Sort, Quicksort, Heap Sort for the given list of integer values.
2. Write a program to find Maximum and Minimum of the given set of integer values.
3. Write a Program to perform Binary Search for a given set of integer values recursively and non-recursively.
8. Write a program to find solution for knapsack problem using greedy method.
9. Write a program to find minimum cost spanning tree using Prim’s Algorithm.
10. Write a program to find minimum cost spanning tree using Kruskal’s Algorithm.
11. Write a program to perform Single source shortest path problem for a given graph.
12. Write a program to find solution for job sequencing with deadlines problem.
13. Write a program for all pairs shortest path problem.
14. Write a program to solve N-QUEENS problem.
15. Write a program to solve Sum of subsets problem for a given set of distinct numbers.
Reading References:
1. T.H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms, PHI
2. Sarabasse & A.V. Gelder Computer Algorithm - Introduction to Design and Analysis, Pearson.
3. A. Aho, V. Alfred, J. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-
Wesley.
Basic Features
Undergraduate degree programmes of either 3 or 4-year duration, with multiple entry and exit points and re-entry options, with
appropriate certifications such as:
UG certificate after completing 1 year (2 semesters with 40 Credits + 1 Summer course of 4 credits) of study,
UG diploma after 2 years (4 semesters with 80 Credits + 1 Summer course of 4 credits) of study,
Bachelor’s degree after a 3-year (6 semesters with 120 credits) programme of study,
4-year bachelor’s degree (Honours) after eight semesters (with 170 Credits) programme of study.
4-year bachelor’s degree (Honours with Research) if the student completes a rigorous research project (of 12 Credits) in
their major area(s) of study in the 8th semester.
Note: The eligibility condition of doing the UG degree (Honours with Research) is- minimum75% marks to be obtained in the
first six semesters.
The students can make an exit after securing UG Certificate/ UG Diploma and are allowed to re-enter the degree
programme within three years and complete the degree programme within the stipulated maximum period of seven
years.
Powered By CityHub web solution
