National Institute of Technology Calicut

Module I (7 Hours)

 

Generation of lexical analyzer using tools such as LEX. 

Module II (25 Hours)

Generation of parser using tools such as YACC. Creation of Symbol tables.

 

Module III (20 Hours)

 

Semantic Analysis and intermediate code generation.

 

Module IV (18 Hours)

 

Generation of target code.

References

4. Holub A. I., Compiler Design in C, Prentice Hall India

5. 
   Appel A.W., Modern Compiler Implementation in C, Cambridge University Press
   

CSM 581 SEMINAR

Pre-requisite: NIL

L	T	P	C
0	0	3	1

Each student is expected to present a seminar on a topic of current relevance in computer science and engineering – they have to refer papers from standard journals like ACM, IEEE, JPDC, IEE etc. – at least three cross references must be used – the seminar report must not be the reproduction of the original paper.

CSM 599 PROJECT

Pre-requisite: CSU 321 Software Engineering

Duration	1 Semester
Credits	15

The project is for the entire duration of the sixth semester. Each student is expected to develop a complete product. The design and development may include software and /or hardware. The project involves the design, development, testing, and installation of the product. The product should have user manuals. There will be regular evaluations of the progress of the work by the guide and the evaluation committee. A detailed Project Report is to be submitted at the end of the semester.

PART 2 : ELECTIVE COURSES

CSU 339 ADVANCED DATA STRUCTURES
Pre-requisite: CSU 203 Data Structures and Algorithms

L	T	P	C
3	0	0	3

Module I (10 hours)
Review of elementary data structures. Advanced Trees – Red Black Trees, AVL Trees, Optimal Binary Search Trees, Splay Trees.

 

Module II (10 hours)

B Trees, Tries, Binary Heaps, Priority Queues, Binomial Heaps, Fibonacci Heaps.
Module III (10 hours)

Disjoint set representation – Path compression algorithm – Graph algorithms, Connected components, topological sort, Minimum spanning tree, Algorithms of Kruskal and Prim,

Module IV (12 hours)
Single-source shortest paths – Dijkstra's algorithm, Bellman-Ford Algorithm. All-Pairs shortest paths – Floyd-Warshall algorithm, Johnson's algorithm for sparse graphs. Maximum Flow - Flow networks, Ford-Fulkerson Method.

 

References:

1. Cormen T.H., Leiserson C.E, and Rivest R.L., Introduction to Algorithms, Prentice Hall India, New Delhi, 1990.

2. Wirth N., Algorithms + Data Structures = Programs, Prentice Hall India, New Delhi, 1976.

3. Sartaj Sahni, Data Structures, Algorithms and Applications in C++, Universities Press, 2005.

CSU 358 COMMUNICATION AND INFORMATION THEORY
Pre-requisites: CSU 201 Discrete Computational Structures / MAG 501 Discrete Mathematics,

Knowledge of Probability Theory

L	T	P	C
3	0	0	3

Module I (10 Hours)

Entropy – Joint entropy and conditional entropy. Source Coding theorem – Shannon-Fano, Huffman Coding.

Mathematical properties of entropy function. Chain rules for entropy, relative entropy and mutual information. Efficiency of Shannon-Fano coding. Optimality of Huffman coding.
Module II (12 Hours)

Channel Models – Symmetric channels. Binary Symmetric Channel – Information – Channel Coding theorem – Review of associated mathematical background . Channel relationships. Uniform Channel. Converse of Shannon's theorem.

Module III (10 Hours)

Zero error cordes. Error Correcting Codes . Ideal observer decoding. Minimum distance decoding.

Maximum Likelihood decoding. Single Error Correction and Double Error Correction. Syndrome Decoding.
Module IV (10 Hours)

Linear Codes . Study of Repetition codes. Parity codes. Cyclic codes. Hamming code. Introduction to Golay code and Reed-Solomon codes. Establishing the bounds on a couple of these codes and the process of decoding them.

Reference:

5. 
   1. R. W. Hamming, Coding and Information Theory, Prentice Hall, 1986.
   
6. 
   2. T. Cover and J. Thomas, Elements of Information Theory, Wiley, 1991.
   
7. 
   3. P. Garret, The mathematics of coding theory, Pierson Education, 2005.
   

CSU 301 DESIGN AND ANALYSIS OF ALGORITHMS
Pre-requisite: CSU 203 Data Structures & Algorithms

L	T	P	C
3	0	0	3

Module I (10 hours)

Analysis: RAM model - cost estimation based on key operations - big Oh - big omega - little Oh - little omega and theta notations - recurrence analysis - master's theorem - solution to recurrence relations with full history, probabilistic analysis - linearity of expectations - worst and average case analysis of quick-sort - merge-sort - heap-sort - 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 II (10 hours)

Design: 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 - travelling salesman problem - matroids and theoretical foundations of greedy algorithms
Module III (10 hours)

Complexity: complexity classes - P, NP, Co-NP, NP-Hard and NP-complete problems - cook's theorem (proof not expected) - 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 IV (12 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 
Text Books:

1. 
   Cormen T.H., Leiserson C.E, Rivest R.L. and Stein C, Introduction to Algorithms, Prentice Hall India,
   

New Delhi, 2004, Modules I, II and III.

2. 
   Motwani R. & Raghavan P., Randomized Algorithms, Cambridge University Press, Module IV
   

References:

1. 
   Anany Levitin, Introduction to the Design & Analysis of Algorithms, Pearson Education. 2003
   
2. 
   Basse S., Computer Algorithms: Introduction to Design And Analysis, Addison Wesley.
   
3. 
   Manber U., Introduction to Algorithms: A Creative Approach, Addison Wesley
   
4. 
   Aho A. V., Hopcroft J. E. & Ullman J. D., The Design And Analysis of Computer Algorithms, Addison Wesley