## Distributed Systems

**Course Code: **CSE 3201

**Year:** 3 **Semester:** 2 **Credits:** 3

**Description:**

**Introduction:** Basic strategies of Algorithm design, Time and space analysis of algorithms, Average, best and worst case analysis and analysis techniques, different notations.

**Divide and conquer:** Linear/Binary search, sorting methods strassen’s matrix multiplication method.

**Greedy method:** Activity selection, Huffman coding, Knapsack problem, job scheduling with deadlines, spanning trees, prim and kruskal’s algorithms, single-source shortest paths.

**Dynamic programming:** multistage graphs, travelling salesman problem, All pairs shortest paths. Matrix chain multiplication, longest common subsequences and optional polygon triangulation problems.

**Backtracking:** 8 queens problem, sum of subsets, graph colouring problem, Hamilton cycles.

**Graph ****algorithms:** depth first search, breadth first search, strongly connected, cut-set algorithms.

**Network flow ****algorithms:** Max flow, min cut algorithms, sink-source.

**Branch and bound:** Lest cost search, 15-puzzle problem, Knapsack problem, Travelling salesman problem.

**NP vs. P:** The spaces P and NP, the NP-complete problems, Cook’s theorem, NP-Hard problems.

**References:**

1. H Cormen, E. Leiserson and L. Rives : Introduction to Algorithms

2. E. Horowitz and S. Sahni : Fundamentals of Computer Algorithms.

3. Goodman : Introduction to Design and Analysis of Algorithms

4. Robert Sedgewick : Algorithms.