Analysis of Algorithms (English)

Unit 1. Introduction: Objective, scope and outcome of the course.

Unit 2. Background: Review of Algorithm, Complexity Order Notations:definitions and calculating complexity.Divide And Conquer Method: Binary Search, Merge Sort, Quick sort and Strassen 's matrix multiplication algorithms .

Unit 3. Greedy Method: Knapsack Problem , Job Sequencing, Optimal Merge Patterns and Minimal Spanning Trees. Dynamic Programming: Matrix Chain Multiplication. Longest Common Subsequence and 0/1 Knapsack Problem.

Unit 4. Branch And Bound: Traveling Salesman Problem and Lower Bound Theory. Backtracking Algorithms and queens problem.Pattern Matching Algorithms: Naïve and Rabin Karp string matching algorithms, KMP Matcher and Boyer Moo re Algorithms.

Unit 5. Assignment Problem. Randomized Algorithms- Las Vegas algorithms, Monte Carlo algorithms, randomized algorithm for Min -Cut, randomized algorithm for 2- SAT. Problem definition of Multicommodity flow, Flow shop scheduling and Network capacity assignment problems.

Unit 6. Problem Classes Np, Np-Hard And Np-Complete: Definitions of P, NP-Hard and NP-Complete Problems . Decision Problems. Cook's Theorem . Proving NP-Complete Problems – Satisfiability problem and Vertex Cover Problem . Approximation Algorithms for Vertex Cover and Set Cover Problem.