Analysis Design Of Algorithm (CS-402)

Analysis Design Of Algorithm (CS-402)

Second Year CS-4th Semester.

Syllabus

UNIT 1

ALGORITHMS, DESIGNING-ALGORITHMS, ANALYZING-ALGORITHMS, ASYMPTOTIC-NOTATION, HEAP, AND SORT. INTRODUCTION TO DIVIDE AND CONQUER, ANALYSIS, DESIGNS, AND COMPARISON OF VARIOUS ALGORITHM BASED ON THIS TECHNIQUE, EXAMPLE BINARY-SEARCH, MERGE SORT, QUICK-SORT, STRASSEN’S MATRIX MULTIPLICATION.

UNIT 2

STUDY OF GREEDY- STRATEGY, EXAMPLES OF GREEDY- METHOD LIKE- HUFFMAN- CODING, OPTIMAL MERGE PATTERNS,  MINIMUM SPANNING TREES, KNAPSACK- PROBLEM, JOB- SEQUENCING WITH DEADLINES, SINGLE SOURCE SHORTEST PATH ALGORITHM.

UNIT 3

CONCEPT OF DYNAMIC- PROGRAMMING, PROBLEMS BASED ON THIS APPROACH SUCH AS 0/1 KNAPSACK, MULTISTAGE-GRAPH, FLOYD-WARSHALL ALGORITHM, RELIABILITY-DESIGN.

UNIT 4

BACKTRACKING CONCEPT AND ITS EXAMPLES LIKE 8 QUEEN’S PROBLEM, HAMILTONIAN CYCLE, GRAPH COLORING PROBLEMS ETC. INTRODUCTION TO BRANCH AND BOUND METHOD, EXAMPLE OF BRANCH AND BOUND METHOD LIKE TRAVELING SALESMEN PROBLEM ETC. MEANING OF LOWER- BOUND THEORY AND ITS USE IN SOLVING ALGEBRAIC- PROBLEM, INTRODUCTION TO PARALLEL- ALGORITHM.

UNIT 5

BINARY SEARCH TREES, HEIGHT BALANCED TREES, 2-3 TREES, B-trees, BASIC SEARCH AND TRAVERSAL FOR TREES AND GRAPH (IN ORDER, PRE-ORDER, POST-ORDER, DFS, BFS), NP-COMPLETENESS.