# MSc (Mathematics and Computing) Programme:Design and Analysis of Algorithms

Thapar UniversityPrice on request

Price on request

Free

£ 359 - (Rs 30,933) £ 341 - (Rs 29,382)

VAT incl.

£ 295 - (Rs 25,418)

+ VAT

## Important information

- Master
- Patiala

Starts | Location |
---|---|

On request |
PatialaThapar University P.O Box 32, 147004, Punjab, India See map |

## 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