Course Structure and Syllabi of Dual Degree (MTech+PhD) programme offered by the department of Computer Science and Engineering

 

 

 

Semester 1

 

CS201 Data Structures 3-0-0 6

CS210 Data Structures Lab 0-0-3 3

CS202 Discrete Mathematics 4-0-0 8

CS322M Digital Logic and Computer Architecture 3-0-0 6

CS241 System Software Lab 0-0-3 3

 

Total 9-0-6 24

 

Semester 2

 

CS203 Formal Languages and Automata 3-0-0 6

CS204 Algorithms 3-0-0 6

CS350M Computer Systems 3-0-0 6

CS244 Systems Programming Lab 0-1-3 5

CS XXX Elective 3-0-0 6

 

Total 12-0-3 29

 

 

Semester 3

 

CS441M Software Engineering 3-0-0 6

CS XXX Elective 3-0-0 6

CS XXX Elective 3-0-0 6

CS XXX Elective 3-0-0 6

 

                                                                                                    Total 12-0-0 24

 

 

 

 

CS 201             Data Structures            (3-0-0-6)

 

Pre-requisite: CS 101 or equivalent

 

Performance of algorithms: space and time complexity, asymptotics; Fundamental Data structures: linked lists, arrays, matrices, stacks, queues, binary trees, tree traversals; Algorithms for sorting and searching: linear search, binary search, insertion-sort, selection sort, bubble-sort, quicksort, mergesort, heapsort, shellsort; Priority Queues: lists, heaps, binomial heaps, Fibonacci heaps; Graphs: representations, depth first search, breadth first search; Hashing: separate chaining, linear probing, quadratic probing; Search Trees: binary search trees, red-black trees, AVL trees, splay trees, B-trees; Strings: suffix arrays, tries; Randomized data structures: skip lists.

Texts:

 

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

2. M. A. Weiss, Data Structures and Problem Solving Using Java, Addison-Wesley, 1997.

 

References:

 

1. A. M .Tannenbaum, Y Langsam and M J Augenstein, Data Structures Using C++, Prentice Hall India, 1996.

2.A .H. Aho, J. E. Hopcroft and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1987.

3.R. Sedgewick, Algorithms in C++ Parts 1-4, 3rd Ed., Pearson Education, 1998.

4.R. Sedgewick, Algorithms in C++ Part 5, 3rd Edn., Pearson Education, 2002.

 

CS 210             Data Structures Laboratory                     (0-0-3-3)

 

Programming Laboratory will be set in consonance with the material covered in CS201. All programming assignments are to be in object oriented programming languages like C++ or Java.

 

References:

 

1.J Gosling, B Joy, G L Steele and G Bracha, The Java Language Specification, 2nd Ed., Addison-Wesley, 2000.

2.B Stroustrup, The C++ Programming Language, 3rd Ed., Addison-Wesley Longman Reading MA, 1997.

3.S B Lippman, C++ Primer,  2nd Ed.,  Addison-Wesley, 1991.

4.T Budd, C++ for Java Programmers, Addison Wesley, 1999.

5.M C Daconta, Java for C/C++ programmers, John Wiley & Sons, 1996.

 

 

CS 202               Discrete Mathematics             (4-0-0-8)

 

Set theory: sets, relations, functions, countability; Logic: formulae, interpretations, methods of proof, soundness and completeness in propositional and predicate logic; Number theory: division algorithm, Euclid's algorithm, fundamental theorem of arithmetic, Chinese remainder theorem, special numbers like Catalan, Fibonacci, harmonic and Stirling; Combinatorics: permutations, combinations, partitions,  recurrences, generating functions; Graph Theory: paths, connectivity, subgraphs, isomorphism, trees, complete graphs, bipartite graphs, matchings, colourability, planarity, digraphs; Algebraic Structures: semigroups, groups, subgroups, homomorphisms, rings, integral domains, fields, lattices and boolean algebras.

 

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.J. P. Tremblay and R. P. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997.

 

 

CS 322M              Digital Logic and Computer Architecture          (3-0-0-6)

 

Boolean Algebra; Minimisation and realisation of switching circuits; Basic building blocks of combinational circuits: Multiplexer, De-multiplexer, Encoder, Decoder, Adder, Subtracter; Design of synchronous sequential circuits: Flip-flops, Registers, Counters, Finite State Machines, State tables and diagrams, Excitation functions of memory elements. Instruction sets with various addressing modes; Memory organisation: ROM, Cache, Main Memory; CPU design: ALU, Control unit design: hardwired and microprogrammed; I/O transfer: Program controlled, Interrupt controlled and DMA.

Texts:

 

1. M. Morris Mano, Digital Design, 3/e, Pearson Education, 2007.

2. William Stallings, Computer Organization and Architecture: Designing for Performance, 8/e,Pearson Education India. 2010.

 

References:

 

1. A. P. Malvino, D. K. Leach and G. Saha, Digital Principles and Applications, 6/e, McGraw Hill, 2006.

2. V. C. Hamacher, Z. G. Vranesic and S. G. Zaky, Computer Organization, 5/e, McGraw Hill, 2002.

3. D. A. Patterson and J. L. Hennessy, Computer Organization and Design, 3/e, Morgan Kaufmann, 2006.

4. Barry B. Brey, The INTEL Microprocessors, 8/e, Prentice Hall, 2008.

 

CS 241             System Software Laboratory               (0-0-3-3)

 

Overview of Unix system, commands and utilities; Basic Linux administration and installation: grub, rpm, yum, disk partitioning; Basic Linux utilities, logging, backup, authentication; Internet mail system: send mail, elm, mail administration; Program Maintenance: make, sccs, debugging with gdb and ddd; Archiving: shar, tar; Shell use: redirection, .cshrc, environment variables; Regular Expression parsing: grep, egrep, sed, awk; Shell programming: bash; Scripting Languages like Perl, Python, Java Script; Database Driven Web Site: PHP and MySQL;

 

References:

 

1.E. Nemeth, G. Snyder and T. R. Hein, Linux Administration Handbook, Prentice Hall PTR, 2002.

2.L. Wall, T. Christainsen and J. Orwant, Programming PERL, 3rd  Ed., O’Reilly, 1999.

3.D. Curry, UNIX Systems Programming for SVR4, O’Reilly, 1996.

4.S. Kochan and P. Wood, Unix Shell programming, 3rd Ed., SAMS, 2003.

5.S. Das, Unix System V.4 Concepts and Applications, 3rd Ed., Tata Mcgraw-Hill, 2003.

6.A. Rubini and J. Corbet, Linux Device Drivers, 2nd Ed., O’Reilly, 2001.

7.D. Flanagan, Javascript: The Definitive Guide, 5th Ed., O'Reilly, 2006.

8.D. Gosselin, PHP Programming with MySQL, Course Technology, 2006.

 

 

CS 203             Formal Languages and Automata Theory         (3-0-0-6)

 

Pre-requisite:  CS 202 or equivalent.

 

Alphabets, languages, grammars; Finite automata: regular languages, regular expressions; Context-free languages: pushdown automata, DCFLs; Context sensitive languages: linear bounded automata; Turing machines: recursively enumerable languages; Operations on formal languages and their properties; Chomsky hierarchy; Decision questions on languages.

 

Texts:

 

1. J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd Ed., Pearson Education, 2000.

 

References:

 

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, Pearson Education Asia, 2001.

3. D. C. Kozen, Automata and Computability, Springer-Verlag, 1997.

 

 

 

CS 204             Algorithms                   (3-0-0-6)

 

Pre-requisite: CS201 plus CS202 or equivalent.

 

Models of Computation: space and time complexity measures, lower and upper bounds; Design techniques: the greedy method, divide-and-conquer, dynamic programming, backtracking, branch and bound; Lower bound for sorting; Selection; Graph Algorithms: connectivity, strong connectivity, biconnectivity, topological sort, shortest paths, minimum spanning trees, network flow; The disjoint set union problem; String matching; NP-completeness; Introduction to approximate algorithms and Randomized algorithms.

 

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 350M                       COMPUTER SYSTEMS           (3 0 0 6)

 

Pre-requisite: CS 206M, CS 322M

 

Introduction to structure and organization of computer systems, operating systems, and networks; Processes and threads and their scheduling, synchronization, deadlocks in concurrent processes; Memory management basics, demand paging and virtual memory implementation; File system design and implementation. Basics of digital communication, digital transmission of data, modulation; Multiplexing; Data link control with sliding window protocols, error control; Local area networks, Ethernet, wireless networks; Concepts of switched networks; Internet addressing and routing algorithms; Transport protocols, UDP, TCP, flow control, congestion control; Application layer protocols such as DNS, SSL, Web.

 

Texts:

 

1. A. Silberschatz, P. B. Galvin and G. Gagne, Operating System Concepts, 8th Ed, Wiley India, 2009.

2. A. S. Tanenbaum, Computer Networks, 4th Ed, Pearson India, 2003.

 

References:

 

1. L. L. Peterson and B. S. Davie, Computer Networks: A Systems Approach, 4th Ed, Elsevier India,2007.

2. W. Stallings, Data and Computer Communications, 8th Ed, Pearson India, 2007.

3. W. Stallings, Operating Systems: Internals and Design Principles, 6th Ed, Pearson India, 2009.

 

 

CS 244 System Programming Laboratory              (0-1-3-5)

 

Assembly Language Programming: Basic concepts of computer organization, instruction and data representation; Linux Assembly language; Assembly Language Programming and Simulation using X86; C-Macro; Linker and Loader: Design of Linkers and Loaders in C-Compile and go loader, Absolute Loaders, Relocating Loaders, Direct Linking Loaders.

 

Documentation and Presentation: Document writing and Slides using LaTex; Windows administration: Managing the server operating system, file, and directory services, Software distribution and updates, Profiling and monitoring assigned servers, Security and Troubleshooting; Unix system calls like Fork, Join, Quit.

 

References:

 

1.A.S. Tanenbaum, Structured Computer Organization, Prentice Hall, 1999.

2.R. Britton, MIPS Assembly Language Programming, Prentice Hall, 2003.

3.J. J. Donovan, Systems Programming, 45th Reprint, Tata Mc-Graw-Hill, 1991

4.D. M. Dhamdhere, Systems Programming And Operating Systems, 2nd Revised Ed., Tata Mc-Graw-Hill, 2008.

5.J. Levine, Linkers and Loaders, Morgan Kauffman, 1999.

6.L. Lamport, LaTeX: A Document Preparation System, 2nd Ed., Addison-Wesley Series, 1994.

7.B. Kauler, Windows assembly language & Systems Programming: 16- and 32-Bit Low-Level Programming for the PC and Windows, 2nd Ed., CMP Books; August 1997

 

 

CS 441M                       Software Engineering      (3-0-0-6)

 

Introduction: software engineering principles, life cycle; Requirement specification: styles, operational and descriptive; Design: a brief concept on objects, data abstraction, inheritance, polymorphism, data encapsulation, software design using functional and object oriented approaches, architectural, component-level and user interface design; Brief introduction on database system (specially SQL, MySQL); Verification: testing, validation; Software reuse: design patterns; Software management; Software Modelling: UML

 

Texts:

 

1. R S Pressman, Software Engineering: A Practitioner's Approach, 7/e, McGraw-Hill, 2010.

2. I Sommerville, Software Engineering, 5/e, Addison-Wesley, 2000.

 

References:

 

1. T C Lethbridge and Robert Laganière, Object Oriented Software Engineering, Tata McGraw-Hill, 2004.

2. Jacobson Ivar, Magnus Christerson, Patrik Jonsson and Gunnar Overgaard, Object Oriented Software Engineering, Addison Wesley, 1992.

3. Jacobson Ivar, Grady Booch and James Rumbaugh, Unified Software Development Process, Addison Wesley, 1999.

4. S Bennett, S McRobb and R Farmer, Object Oriented Systems Analysis and Design Using UML, 2/e, Tata McGraw-Hill, 2004.

5. E Gamma, R Helm, R Johnson and J M Vlissides, Design Patterns: Elements of Reusable Object Oriented Software, Addison Wesley, 1994.