Design and Analysis of Algorithms (B.Sc Computer Science)

Algorithm complexity, divide and conquer, greedy methods, dynamic programming, backtracking and graph algorithms.

6 MonthsDuration 5Chapters23Topics

Enquire now

Syllabus · पाठ्यक्रम

Download PDF

01Unit 1: Introduction and Complexity Analysis 5 topics

Algorithm and its specification
Asymptotic notations: Big-O, Omega, Theta
Best, average and worst case
Recurrence relations: substitution and recursion tree
Master theorem

02Unit 2: Divide and Conquer 4 topics

Binary search
Merge sort and quick sort
Finding maximum and minimum
Strassen's matrix multiplication

03Unit 3: Greedy Method 5 topics

Fractional knapsack
Job sequencing with deadlines
Huffman coding
Minimum spanning tree: Prim and Kruskal
Dijkstra's shortest path

04Unit 4: Dynamic Programming 5 topics

Principle of optimality
0/1 knapsack
Longest common subsequence
Matrix chain multiplication
Floyd-Warshall and Bellman-Ford

05Unit 5: Backtracking, Branch and Bound, NP 4 topics

N-queens and sum of subsets
Graph colouring
Branch and bound: travelling salesman
P, NP, NP-hard and NP-complete

About

You will be able to

Analyse algorithms using asymptotic notations and solve recurrences with the master theorem
Apply divide and conquer to searching, sorting and matrix multiplication
Solve problems such as knapsack, job sequencing, Huffman coding, MST and shortest paths with greedy methods
Solve 0/1 knapsack, LCS, matrix chain multiplication and all-pairs shortest paths with dynamic programming
Apply backtracking and branch and bound and explain P, NP and NP-complete classes

Who it is for

B.Sc Computer Science students of Semester 6 (UP State Universities NEP 2020 common minimum syllabus)
Students preparing for MCA entrance, GATE and coding interviews

What you need

B.Sc Computer Science Semesters 1-5, especially Data Structures
Basic discrete mathematics

Questions

Which syllabus does this course follow?

It follows the UP State Universities NEP 2020 common minimum syllabus for B.Sc Computer Science, Semester 6. Where your own university's syllabus differs, the centre follows your university's syllabus and question pattern.

Is coding required in this paper?

The paper is mainly analysis and tracing on paper; writing the algorithms in C or Python is encouraged for practice.

Is there a test after the course?

Yes. Unit-wise multiple-choice tests and a final exam paper are included for semester exam practice.