MSc (Mathematics and Computing) Programme:Design and Analysis of Algorithms
Master
In Patiala
Description
-
Type
Master
-
Location
Patiala
Facilities
Location
Start date
Start date
Reviews
Course programme
Semester I
Real Analysis – I
Linear Algebra
Complex Analysis
Fundamentals of Computer Science and C Programming
Discrete Mathematical Structure
Differential Equations
Semester II
Real Analysis –II
Advanced Abstract Algebra
Computer Oriented Numerical Methods
Data Structures
Data Based Management Systems
Operating Systems
Semester III
Topology
Computer Based Optimization Techniques
Computer Networks
Mechanics
Seminar
Semester IV
Functional Analysis
Dissertation
Design and Analysis of Algorithms
Introduction to Models of Computation: Growth Function, Summations, Recurrences – substitution, iteration, overview of Data Structures-stacks, queues, trees, heaps, hashing, sets and graphs. Algorithm Definition, Analyzing algorithms, order arithmetic, time and space complexity.
Divide and Conquer: general method, binary search, merge sort, quick sort, selection problem, median, and order statistics.
Greedy method: Job Sequencing, Knapsack problem, optimal merge patterns, minimum spanning trees.
Dynamic Programming: Use of table instead of recursion, all pair shortest path, 0/1 knapsack, optimal binary search tree, traveling salesperson problem.
Graphs: Traversals, Topological sorting, minimum spanning tree, single source shortest paths, Dijkstra and Bellman ford algorithms, all – pair shortest paths, maximum flow problem. code optimization.
Backtracking: 8 queens problem, sum of subsets, graph coloring, Knapsack problem.
Matrix Algorithms: Strassen’s algorithm, Transpose of a matrix, Matrix Inversion,
Advanced Algorithm Technique: P, NP, NP- Hard and NP-complete, deterministic and non deterministic polynomial time algorithm approximation, algorithm for some NP complete problems. Introduction to Parallel Algorithms (CRCW, EREW algorithms)
Laboratory Work
MSc (Mathematics and Computing) Programme:Design and Analysis of Algorithms