Department of Computer Science and Engineering

Module 1 (10 (T) + 7(P) Hours)

Analysis: RAM model - big Oh - big Omega – Asymptotic Analysis, recurrence relations, probabilistic analysis - linearity of expectations - worst and average case analysis of sorting algorithms, binary search - hashing algorithms - lower bound proofs for the above problems - amortized analysis - aggregate - accounting and potential methods - analysis of Knuth-Morris-Pratt algorithm - amortized weight balanced trees

 

Module 2 (10 (T) + 7(P) Hours)

Problem Solving, Classical Algorithm paradigms,: divide and conquer - Strassen's algorithm, O(n) median finding algorithm - dynamic programming - matrix chain multiplication - optimal polygon triangulation - optimal binary search trees - Floyd-Warshall algorithm - CYK algorithm - greedy - Huffman coding - Knapsack, Kruskal's and Prim's algorithms for MST - backtracking - branch and bound - traveling salesman problem - matroids and theoretical foundations of greedy algorithms
Module 3 (10 (T) + 7(P) Hours)

Complexity: complexity classes - P, NP, Co-NP, NP-Hard and NP-complete problems - cook's theorem- NP-completeness reductions for clique - vertex cover - subset sum - hamiltonian cycle - TSP - integer programming - approximation algorithms - vertex cover - TSP - set covering and subset sum

 

Module 4 (12 (T) + 7(P) Hours)

Probabilistic algorithms: pseudo random number generation methods - Monte Carlo algorithms - probabilistic counting - verifying matrix multiplication - primality testing - Miller Rabin test - integer factorization - Pollard’s rho heuristic - amplification of stochastic advantage - applications to cryptography - interactive proof systems - les vegas algorithms - randomized selection and sorting - randomized solution for eight queen problem - universal hashing - Dixon’s integer factorization algorithm 
References:

1. 
   Cormen T.H., Leiserson C.E, Rivest R.L. and Stein C, Introduction to Algorithms, Prentice Hall India, 3/e, 2010
   
2. 
   Motwani R and Raghavan P., Randomized Algorithms, Cambridge University Press, 2001.
   
3. 
   Anany Levitin, Introduction to the Design & Analysis of Algorithms, Pearson Education. 2003
   
4. 
   Basse S., Computer Algorithms: Introduction to Design And Analysis, Addison Wesley, 2000.
   
5. 
   Manber U., Introduction to Algorithms: A Creative Approach, Addison Wesley, 2006.
   
6. 
   Aho A. V., Hopcroft J. E. & Ullman J. D., The Design And Analysis of Computer Algorithms, Addison Wesley, 2003.
   

CS4051 CODING THEORY

Pre-requisite: Nil

L	T	P	C
3	0	2	4

Total Hours: 70 Hrs  

Module 1 (10 (T) + 7(P) Hours)

Linear Codes: Review of linear algebra - Linear codes and syndrome decoding. Generator and parity check matrices. Hamming geometry and code performance. Hamming codes. Error correction and concept of hamming distance.
Module 2 (10 (T) + 7(P) Hours)

Cyclic codes: BCH codes, Reed-Solomon codes – Polynomial time decoding. Shift register encoders for cyclic codes. Cyclic hamming codes. Decoding BCH – key equation and algorithms. Berlekamp's Iterative decoding Algorithm.

Module 3 (10 (T) + 7(P) Hours)

Convolutional codes : Viterbi decoding. Concept of forward error correction. State diagram, trellises.

Concept of space time codes. Space Time Trellis codes. Path enumerators and proof of error bounds.

Applications to wireless communication.

Module 4 (12 (T) + 7(P) Hours)

Codes on Graphs: Concept of girth and minimum distance in graph theoretic codes. Expander Graphs and Codes – linear time decoding. Basic expander based construction of list decodable codes. Sipser Spielman algorithm. Bounding results.

References:

1. 
   R. Johannesson and K. Sh. Zigangirov, Fundamentals of Convolutional Coding, Wiley-IEEE Press, 1999.
   
2. 
   W. C. Huffman and V. Pless, Fundamentals of error correcting codes, Cambridge University Press, 2003.
   
3. 
   van Lint J. H. An Introduction to Coding Theory, 2/e, Springer-Verlag, 1992.
   
4. 
   R.J. McEliece, The Theory of Information and Coding, Addison Wesley, 1997.
   

CS4052 LOGIC FOR COMPUTER SCIENCE

Pre-requisite: Nil

L	T	P	C
3	0	2	4

Total Hours: 70 Hrs  

Module 1 (10 (T) + 7(P) Hours)

Propositional logic, syntax of propositional logic, semantics of propositional logic, truth tables and tautologies, tableaus, soundness theorem, finished sets, completeness theorem.
Module 2 (10 (T) + 7(P) Hours)

Predicate logic, syntax of predicate logic, free and bound variables, semantics of predicate logic, graphs, tableaus, soundness theorem, finished sets, completeness theorem, equivalence relations, order relations, set theory.

Module 3 (10 (T) + 7(P) Hours)

Linear time Temporal Logic(LTL), syntax of LTL, semantics of LTL, Buchi Automata, Buchi recognizable languages and their properties, Automata theoretic methods, Vardi-Wolper Construction, Satisfiability problem of LTL, Model checking problem of LTL.

Module 4 (12 (T) + 7(P) Hours)

Software Verification: Introduction to Tools used for software verification - SPIN and SMV, Method of verification by the tools.

References:

1. 
   Jerome Keisler and H. Joel Robbin, Mathematical Logic and Computability, McGraw-Hill, 1996.
   
2. 
   Papadimitriou. C. H., Computational Complexity, Addison Wesley, 1994.
   
3. 
   Gallier, J. H., Logic for Computer Science: Foundations of Automatic Theorem Proving, Harper and Row, 1986.
   

CS3091 COMPILER LABORATORY

Pre-requisite: Nil

L	T	P	C
1	0	3	3

Total Hours: 56 Hrs  
Theory (14 Hours) Practical (42 Hours)