MCA
MCA 1 SEM.
Introduction to Information Technology
Programming Based Numerical Analysis
Advanced Programming in ‘C’ Language
Data Structure with Algorithm
Digital Electronics
MCA 2 SEM.
Principles of Operating System
Object Oriented Programming with C++
Computer System Architecture
Web Technology
Discrete Mathematics
MCA 3 SEM.
Introduction to JAVA
Artificial Intelligence and Expert Systems
RDBMS
Theory of Computation
Computer Network
MCA 4 SEM.
Compiler Design
Software Engineering
Financial Accounting
Operation Research
Management Information System
MCA 5 SEM.
Soft Computing Techniques
Interactive Computer Graphics
Data Mining & Data Warehousing
Network Security
Analysis & Design of Algorithm
MCA 6 SEM.
Major Project ( Viva Voce)
Guru Ghasidas Vishwavidyalaya
Bilaspur Bilaspur Chhattisgarhhttp://www.ggu.ac.in
MCA 5 SEM.
Subject: Analysis & Design of Algorithm

UNIT - 1 Basic

Algorithm analysis, Analyzing algorithms, Worst - case and Average case Analysis, Asymptotic Notations, Recurrence substitution method, master method.


UNIT - 2 Design Methods

General Consideration, Algorithm design paradigms and representative problems.


UNIT - 3 Deterministic Algorithms

Divide and Conquer Binary search, Merge sort, Quick sort.
Greedy Method: Minimal spanning tree, Shortest Paths, Knapsack.
Dynamic Programming: Chained matrix multiplication, shortest paths, optimal search trees. Backtracking 8-queens problem, Graph colouring, Hamiltonian cycles.
Branch and Bound: 0/1 Knapsack problem, Traveling salesperson.


UNIT - 4 Non Deterministic Algorithms

Intractable Problems Basic concepts, Nondeterministic algorithms, NP Completeness, Cook's theorem, Examples of NP-Hard and NP-Complete problems, Problem reduction. Approximation Graph colouring, Task scheduling, Bin packing. Probabilistic Algorithms Numerical integration, Primality testing. Graph Algorithms, BFS, DFS and its applications.


UNIT - 5 Evaluation of Algorithm

Lower Bound Techniques, Comparison tree, Reduction, Adversary argument.


Jump to Top | Home Page