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

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

6 महीनेअवधि 5Chapters23टॉपिक

अभी पूछताछ करें

सिलेबस · पाठ्यक्रम

Download PDF

01Unit 1: Introduction and Complexity Analysis 5 टॉपिक

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 टॉपिक

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

03Unit 3: Greedy Method 5 टॉपिक

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

04Unit 4: Dynamic Programming 5 टॉपिक

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 टॉपिक

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

परिचय

आप यह कर पाएँगे

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

यह किसके लिए है

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

आपको क्या चाहिए

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

सवाल

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.