MCA C2002
Design and Analysis of Algorithms
Notes are on their way.
For now, use the syllabus outline to see what this subject covers.
Syllabus topics
Algorithms and structured programming, analysing algorithms, asymptotic behaviour of an algorithm, Order notati ons, time and space complexities (polynomial, logrithmic and exponential), average and worst case analysis, lower and upper bounds. [Q-1]
Notes will be added here.
Syllabus: supplied PDF, page 16.
Syllabus topics
Threaded trees, B -trees, Heaps and heapsort, sets and relations, Graphs, Hashing. Ba sic search & Traversal Techniques (Breadth first and Depth first traversals of Graphs). [Q-2]
Notes will be added here.
Syllabus: supplied PDF, page 16.
Syllabus topics
Divide and conquer (Mergesort, Quicksort, matrix multiplication). Greedy method: General method, knapsack problem, job sequencing with deadlines, minimum cost spanning trees). Dynamic programming (0/1 knapsack, travelling salesman problem). [Q-2]
Notes will be added here.
Syllabus: supplied PDF, page 16.
Syllabus topics
8 - Queens problem, Sum of Subsets, Graph coloring, 0/1 Knapsack. Branch & Bound (0/1 knapsack, Travelling salesman). [Q-2]
Notes will be added here.
Syllabus: supplied PDF, page 16.
Syllabus topics
Polynomial Time Approximation Schemes. Complexity: - NP-Hard and NP-complete Problems - Cook's theorem, NP completeness reductions. [Q-1]
Notes will be added here.
Syllabus: supplied PDF, page 16.
Check your university’s syllabus for the topics covered in your exams.