0% found this document useful (0 votes)
20 views2 pages

Analysis of Algorithms

The document outlines the course CSC402: Analysis of Algorithms, which covers mathematical approaches, algorithmic strategies, and complexity analysis. Key topics include divide and conquer, greedy methods, dynamic programming, backtracking, and string matching algorithms, with specified modules and hours for each. Assessment consists of internal tests and an end-semester examination, with resources and textbooks provided for further study.

Uploaded by

avishkar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
20 views2 pages

Analysis of Algorithms

The document outlines the course CSC402: Analysis of Algorithms, which covers mathematical approaches, algorithmic strategies, and complexity analysis. Key topics include divide and conquer, greedy methods, dynamic programming, backtracking, and string matching algorithms, with specified modules and hours for each. Assessment consists of internal tests and an end-semester examination, with resources and textbooks provided for further study.

Uploaded by

avishkar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Course Code Course Name Credit

CSC402 Analysis of Algorithms 3

Prerequisite: Data structure concepts, Discrete structures


Course Objectives:
1 To provide mathematical approaches for Analysis of Algorithms
2 To understand and solve problems using various algorithmic approaches
3 To analyze algorithms using various methods

Course Outcomes: At the end of the course learner will be able to


1 Analyze the running time and space complexity of algorithms.
2 Describe, apply and analyze the complexity of divide and conquer strategy.
3 Describe, apply and analyze the complexity of greedy strategy.
4 Describe, apply and analyze the complexity of dynamic programming strategy.
5 Explain and apply backtracking, branch and bound.
6 Explain and apply string matching techniques.

Module Detailed Contents Hours


1 Introduction 8
1.1 Performance analysis, space, and time complexity Growth of function,
Big-Oh, Omega Theta notation Mathematical background for algorithm
analysis.
Complexity class: Definition of P, NP, NP-Hard, NP-Complete
Analysis of selection sort, insertion sort.
1.2 Recurrences: The substitution method, Recursion tree method, Master
method
2 Divide and Conquer Approach 6
2.1 General method, Merge sort, Quick sort, Finding minimum and
maximum algorithms and their Analysis, Analysis of Binary search.
3 Greedy Method Approach 6
3.1 General Method, Single source shortest path: Dijkstra Algorithm
Fractional Knapsack problem, Job sequencing with deadlines,
Minimum cost spanning trees: Kruskal and Prim’s algorithms
4 Dynamic Programming Approach 9
4.1 General Method, Multistage graphs, Single source shortest path:
Bellman Ford Algorithm
All pair shortest path: Floyd Warshall Algorithm, Assembly-line
scheduling Problem0/1 knapsack Problem, Travelling Salesperson
problem, Longest common subsequence
5 Backtracking and Branch and bound 6
5.1 General Method, Backtracking: N-queen problem, Sum of subsets,
Graph coloring
5.2 Branch and Bound: Travelling Salesperson Problem, 15 Puzzle problem
6 String Matching Algorithms 4
6.1 The Naïve string-matching algorithm, The Rabin Karp algorithm, The
Knuth-Morris-Pratt algorithm

Textbooks:
1 T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms”, 2nd
Edition, PHI Publication 2005.
2 Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms”
University Press.
References:
1 Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, “Algorithms”, Tata McGraw-
Hill Edition.
2 S. K. Basu, “Design Methods and Analysis of Algorithm”, PHI

Assessment:
Internal Assessment:
Assessment consists of two class tests of 20 marks each. The first class test is to be conducted
when approx. 40% syllabus is completed and second class test when additional 40% syllabus is
completed. Duration of each test shall be one hour.

End Semester Theory Examination:


1 Question paper will comprise of total six questions.
2 All question carries equal marks
3 Questions will be mixed in nature (for example supposed Q.2 has part (a) from module 3
then part (b) will be from any module other than module 3)
4 Only Four question need to be solved.
5 In question paper weightage of each module will be proportional to number of respective
lecture hours as mention in the syllabus.

Useful Links
1 https://nptel.ac.in/courses/106/106/106106131/
2 https://swayam.gov.in/nd1_noc19_cs47/preview
3 https://www.coursera.org/specializations/algorithms
4 https://www.mooc-list.com/tags/algorithms

You might also like