Algorithms and Complexity

Course Title: Algorithms and Complexity
Full Marks: 45+30
Course No: C.Sc. 540
Pass Marks: 22.5+15
Credit Hours = 3
Nature of the course: Theory +Lab

Course Description :

The course can be viewed as a continuation of Design and Analysis of Algorithms, and its goal is to cover basic algorithmic techniques that are not covered in the subject. In particular, we will discuss NP Completeness in detail, approximation algorithms for NP-hard problems, Randomized Algorithms, online algorithms, PRAM algorithms, Mesh Algorithms and Hypercube Algorithms. Course Objectives The purpose of this course is to present depth in optimization paradigms, Some advance algorithm design techniques and moderate level understanding in computational complexity theory.

Prerequisites:

Linear Algebra, Data Structure and algorithm, Basic Course in Algorithm design, Programming language.

Course Contents:

Unit 1: Advance Algorithm Analysis and Design Techniques 10 hr

1.1.Advanced Algorithm Analysis Techniques:

Amortized Analysis(Aggregate Analysis, Accounting Method, Potential method), Probabilistic Analysis, Las Vegas and Monte Carlo Algorithms.

1.2.Advance Algorithm Design Techniques:

Greedy Algorithms (Tree Vertex Splitting, Job Sequencing with deadlines), Dynamic Programming(Greedy vs Dynamic, String Editing, Optimal BST), backtracking(Sum of Subsets, Knapsack Problem), Randomized Algorithms(Identifying the repeated elements, Primality Testing, Karger’s algorithm)

Unit 2: Computational Complexity Theory 10 hr

2.1 Basic Concepts: Complexity Theory, Complexity Classes:

P, NP, NP-Hard and NP-Complete, Decision Problems and Language Recognition Problems

2.2 Problem Reduction:

Reduction, Polynomial time reduction, Cooks Theorem, Proving NP-Completeness: Formula Satisfiablity, 3SAT, CLIQUE, Vertex Cover, Hamiltonian Cycle, TSP, Subset Sum.

2.3 NP-Hard Code Generation Problems:

Code Generation with Common Sub expression, Implementing Parallel Assignment Instructions

2.4 Coping with NP-Completeness:

Performance ratios for approximation algorithms, Approximated Algorithms: Vertex Cover, TSP, Set Covering, Subset Sum

Unit 3: Online and PRAM Algorithms 12 hr

3.1 Online Algorithms:

Introduction, Ski Problem, Load Balancing, Paging and Caching:Last-in First-out (LIFO), Longest Forward Distance (LFD), Least Recently Used (LRU)

3.2 PRAM Algorithms:

Introduction, Computational Model, Fundamental techniques and Algorithms (Prefix Computation, List Ranking), Selection (Maximal Selection with n2 Processors, Finding Maximum Using n Processors), Merging (A Logarithmic Time Algorithm, Odd-Even Merge), Sorting(Odd-Even Merge Sort, Preparata’s Algorithm).

Unit 4: Mesh and Hypercube algorithms 13hr

4.1 Mesh Algorithms:

Computational Model, Packet Routing (Packet Routing on a Linear Array, A Greedy Algorithm for PPR on a Mesh), Fundamental Algorithms (Broadcasting, Prefix Computation, Data Concentration), Selection (Randomized Algorithm for n=p, Randomized Selection for n>p), Sorting (Sorting on a Linear Array, Sorting on a Mesh)

4.2 Hypercube Algorithms:

Computational Model (Hypercube, Butterfly Network,Embedding of other Networks, PPR Routing (Greedy algorithm, Randomized Algorithm), Fundamental Algorithms (Broadcasting, Prefix Computation, Data Concentration), Selection (Randomized Algorithm for n=p, Randomized Selection for n>p), Sorting(Odd-Even Merge Sort, Bitonic Sort)

Textbook:

1. Ellis Horowitz, Sartaj Sahni,Sanguthevar Rajasekaran, Computer Algorithms/C++, 2ndEdition, Universities Press, 2007

Reference Books:

1. H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, 2ndEdition, MIT Press, 2001
2. G. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice-Hall, 1996
   Outcomes and Assessment:
   Student should implement Algorithms described in class and should perform their Empirical Evaluation.