Department of Computer Science and Engineering

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

Number Theory: Review of groups and rings and vector spaces, Euclid's algorithm, Structure of the ring Z_n Algorithms for computation in the ring Z_n - modular inversion, exponentiation, Chinese remaindering.
Module 2 (10 (T) + 7(P) Hours)

Finite fields: Structure theory of finite fields - Factorization of polynomials over finite fields - Berlekamp's algorithm, Cantor Zassenhaus algorithm, Fourier Transform algorithm for finite fields.

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

Primality Testing: Solovay Strassen test, Miller Rabin test, Agrawal, Kayal Saxena algorithm.

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

Applications: Euclid's algorithm for rational polynomial approximation and decoding BCH and RS codes. Applications to public key cryptography.

References:

1. 
   V. Shoup, A computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005.
   
2. 
   H. Delfs and H. Knebl, Introduction to Cryptography, Springer, 1998.
   
3. 
   J. von zur Gathen, Modern Computer Algebra, Cambridge University Press, 2003.
   
4. 
   W. C. Huffman and V. Pless, Fundamentals of Error Correcting Codes, Cambridge University press, 2003.
   

CS4032 COMPUTER ARCHITECTURE

Pre-requisite: Nil

L	T	P	C
3	0	2	4

Total Hours: 70 Hrs  
Module 1 (8(T) + 7(P) Hours)

Fundamentals – Technology trend -performance measurement –Comparing and summarizing performance- quantitative principles of computer design –Amdahl’s law- instruction set architectures – memory addressing- –type and size operand - encoding an instruction set - role of compilers - case study – MIPS 64 architecture – Review of pipelining - MIPS architecture

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

Instruction level parallelism and its limits - dynamic scheduling –-dynamic hardware prediction - multiple issue processor – multiple issue with dynamic scheduling-hardware based speculation- limitation of ILP-Case study P6 micro-architecture Introduction to multicore processors,

Module 3 (16(T) + 12(P) Hours)

Multiprocessor and thread level parallelism- classification of parallel architecture-models of communication and memory architecture-Symmetric shared memory architecture-cache coherence protocols-distributed shared memory architecture-directory based cache coherence protocol- Memory consistency-relaxed consistency models multi threading- exploiting thread level parallelism multicore architecture, Memory hierarchy design - reducing cache misses and miss penalty, reducing hit time - main memory organization - virtual memory and its protection -. Memory issues in multicore processor based systems

 

Module 4 (8(T) + 2(P) Hours)

Storage Systems, Faults and reliability, Networks, Queuing, Design of storage systems – case studies

References

1. 
   Hennesy J. L. & Pattersen D. A., Andrea C. Arpaci-Dusseau, Computer Architecture: A Quantitative approach, 4/e, Morgan Kaufman, 2007.
   
2. 
   Pattersen D. A. & Hennesy J. L., Computer Organisation and Design: The Hardware/ Software Interface, 3/e, Harcourt Asia, 2006.
   

CS4033 DISTRIBUTED COMPUTING
Pre-requisite: CS2005 Data Structures and Algorithms

L	T	P	C
3	0	2	4

Total Hours: 70 Hrs  

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

Characteristics of Distributed Systems, Distributed systems Versus Parallel systems, Models of distributed systems, Happened Before and Potential Causality Model, Models based on States, Logical clocks, Vector clocks, Verifying clock algorithms, Direct dependency clocks.
Module 2 (10(T) + 7(P) Hours)

Mutual exclusion using Time stamps, Distributed Mutual Exclusion (DME) using timestamps, token and Quorums, Centralized and distributed algorithms, proofs of correctness and complexity analysis. Drinking philosophers problem, Dining philosophers problem under heavy and light load conditions. Implementation and performance evaluation of DME algorithms.

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

Leader election algorithms, Global state detection, Global predicates, Termination Detection, Control of distributed computation, disjunctive predicates. Performance evaluation of leader election algorithms on simulated environments.

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

Self stabilization, knowledge and common knowledge, Distributed consensus, Consensus under Asynchrony and Synchrony, Checkpointing for Recovery, R- Graphs

References:

1. 
   Vijay K. Garg., Elements of Distributed Computing, Wiley & Sons, 2002.
   
2. 
   Sukumar Ghosh, Distributed Systems An Algorithmic Approach, Chapman & Hall, CRC Computer and Information Science Series, 2006.
   
3. 
   Tanenbaum S, Distributed Operating Systems, Pearson Education, 2005.
   
4. 
   Coulouris G, Dollimore J. & Kindberg T., Distributed Systems Concepts and Design, 2/e, Addison Wesley 2004.
   
5. 
   Chow R. and Johnson T., Distributed Operating Systems and Algorithms, Addison Wesley, 2002.
   

CS4034 MIDDLEWARE TECHNOLOGIES
Pre-requisite: CS4033 Distributed Computing

L	T	P	C
3	0	2	4

Total Hours: 70 Hrs