Course Structure and Syllabi for MTech in Computer Science and Engineering

 

 

Semester - 1

 

 

 

Semester - 2

 

Course Code

Course Title

L-T-P-C

 

Course Code

Course Title

L-T-P-C

CS512

Data Structures and Algorithms

3-0-0-6

 

CS 515

Theory of Computation

3-0-0-6

CS514

Mathematics for Computer Science

4-0-0-8

 

XX xxx

Elective – 2

3-0-0-6*

CS 548

Computer Systems

3-0-0-6

 

XX xxx

Elective – 3

3-0-0-6*

XX xxx

Elective – 1

3-0-0-6*

 

XX xxx

Elective – 4

3-0-0-6*

CS 513

Programming Lab

0-0-3-3

 

CS 558

Systems Lab

0-0-3-3

 

Total

13-0-3-29*

 

 

Total

12-0-3-27*

 

 

Semester - 3

 

 

 

Semester - 4

 

Course Code

Course Title

L-T-P-C

 

Course Code

Course Title

L-T-P-C

CS 698

Thesis

0-0-0-24

 

CS 699

Thesis

0-0-0-24

 

Total

0-0-0-24

 

 

Total

0-0-0-24

* Indicates minimum required credits. .

 

CS 512             Data Structures and Algorithms          (3-0-0-6)

 

Performance of algorithms: space and time complexity, asymptotics; Design techniques: the greedy method, divide-and-conquer, dynamic programming; Sorting and searching; Graph Algorithms; Priority Queues: lists, heaps, binomial heaps, Fibonacci heaps; Hashing; Search Trees: binary search trees, red-black trees, AVL trees, splay trees, B-trees; The disjoint set union problem; String matching; Strings: suffix arrays, tries; Randomized data structures: skip lists; A selection of advanced topics.

 

Texts:

1.     T H Cormen, C E Leiserson, R L Rivest and C Stein, Introduction to Algorithms, MIT Press, 2001.

2.     J.Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.

 

References:

1.     A. Aho, J E Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

2.     S Sahni, Data Structures, Algorithms and Applications in C++, McGraw-Hill, 2001.

3.     M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons, 2001.

 

 

CS 513             Programming Lab                                           (0-0-3-3)

 

Experiments would be designed to provide hands-on experience in programming data structures and algorithms, to learn a few systems programming tools, and scripting.

 

References:

1.     T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, 2001.

2.     J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005,

  1. M. A. Weiss, Data Structures and Algorithm Analysis in C++, Addison-Wesley, 2007

 

 

CS 514             Mathematics for Computer Science     (4-0-0-8)

Review of sets, functions, relations; Logic: formulae, interpretations, methods of proof in propositional and predicate logic; Number theory: division algorithm, Euclid's algorithm, fundamental theorem of arithmetic, Chinese remainder theorem; Combinatorics: permutations, combinations, partitions,  recurrences, generating functions; Graph Theory: isomorphism, complete graphs, bipartite graphs, matchings, colourability, planarity; Algebraic Structures: semigroups, groups, subgroups, homomorphisms, rings, integral domains, fields, lattices and boolean algebras; Linear algebra: system of linear equations, matrices, vector spaces, linear transformations, Eigen vectors, diagonalization; Probability: conditional probability, random variables, probability distributions, Markov's inequality,  Chebyshev and Chernoff Bounds.

Texts:

1.C. L. Liu, Elements of Discrete Mathematics, 2nd Ed., Tata McGraw-Hill, 2000.

2.R. C. Penner, Discrete Mathematics: Proof Techniques and Mathematical Structures, World Scientific, 1999.

 

References:

1.R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd Ed., Addison-Wesley, 1994.

2.K. H. Rosen, Discrete Mathematics & its Applications, 6th Ed.,  Tata McGraw-Hill, 2007.

3.J. L. Hein, Discrete Structures, Logic, and Computability, 3rd Ed., Jones and Bartlett, 2010.

4.N. Deo, Graph Theory, Prentice Hall of India, 1974.

5.S. Lipschutz and M. L. Lipson, Schaum's Outline of Theory and Problems of Discrete Mathematics, 2nd Ed., Tata McGraw-Hill, 1999.

6.K. S. Trivedi, Probability & Statistics With Reliability, Queuing And Computer Science Applications, Prentice Hall of India, 1994.

7.M. Mitzenmacher and E. Upfal, Probability and Computing- Randomized Algorithms and Probabilistic Analysis, Cambridge University Press,2005.

8.S. Lang, Introduction to Linear Algebra, Springer, 2008.

 

 

CS 515 Theory of Computation                       (3-0-0-6)

Automata and Languages: finite automata and regular expressions, pushdown automata and context-free grammars, pumping lemmas and closure proprties of regular and context-free languages, non-context-free languages; Computability theory: the Church-Turing thesis, Hilbert's problem, decidability, halting problem, reducibility; Complexity theory: time and space complexity, Classes P, NP, NP-complete, PSPACE, and PSPACE-complete; Intractability: hierarchy theorem, Relativization, Circuit complexity.

 

Texts:

1.     M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.

2.     H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981.

 

References:

1.     J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.

2.     S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

3.     C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994.

4.     D. C. Kozen, Theory of Computation, Springer, 2006.

5.     D. S. Garey and G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.

 

 

CS 548                         Computer Systems       (3-0-0-6)

 

Review of concepts of operating systems: Processes, threads, interprocess communication, scheduling, memory management. Review of concepts of computer networks: link layer protocols, local area networks (Ethernet and variants), interconnecting networks with IP, routing, transport layer protocols. Advanced concepts of distributed networked systems: Virtualization, distributed file systems, mass storage systems, recovery and fault tolerance, content networking including multimedia delivery.

 

Texts/References:

 

1.     A. Silberschatz, P. B. Galvin and G. Gagne, Operating System Concepts, 7th Ed, John Wiley and Sons, 2004.

2.     J. Kurose and K. W. Ross, Computer Networking: A Top down approach, 3rd Ed, Pearson India, 2004.

3.     M. Singhal and N. Shivratri, Advanced Concepts in Operating Systems, McGraw Hill, 1994.

4.     A. S. Tanenbaum and Van Steen, Distributed Systems: Principles and Paradigms, Prentice Hall India, 2007.

 

 

CS 558                         Computer Systems Lab                        (0-0-3-3)

 

Experiments would be designed to provide hands-on experience in computer systems, to learn unix system calls, posix threads, operating system concepts, network programming and simulations.

 

Texts/References:

 

1.     W. R. Stevens, UNIX Network Programming, Volume 1: Networking APIs: Sockets and XTI, Prentice Hall, 1998.

2.     W. R. Stevens, UNIX Network Programming, Volume 2: Interprocess Communications, Prentice Hall, 1999.

3.     W. R. Stevens, Advanced Programming in the UNIX Environment, Addison Wesley, 1992.