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.