IIT Kharagpur Syllabus for Computer Science

Here I am looking for Indian Institute of Technology, IIT Kharagpur B.Tech in Computer Science & Engineering course detailed syllabus, will you please provide here???

[Kiran Chandar]

Indian Institute of Technology, IIT Kharagpur B.Tech in Computer Science & Engineering course detailed syllabus, here I am giving:

PROGRAMMING AND DATA STRUCTURES L-T-P: 3-1-0, Credit: 4

Introduction to digital computers; introduction to programming - variables, assignments; expressions; input/output; conditionals and branching; iteration; functions; recursion; arrays; introduction to pointers; structures; introduction to data-procedure encapsulation; dynamic allocation; linked structures; introduction to data structures - stacks and queues; time and space requirements.

SOFTWARE ENGINEERING L-T-P: 3-0-0, Credit: 3


Introduction, software life-cycle models, software requirements specification, formal requirements specification and verification - axiomatic and algebraic specifications, function-oriented software design, object-oriented design, UML, design patterns, user interface design, coding and unit testing, integration and systems testing, debugging techniques, software quality - SEI CMM and ISO-9001. Software reliability and fault-tolerance, software project planning, monitoring, and control, software maintenance, computer-aided software engineering (CASE), software reuse, component-based software development, extreme programming.

Development of requirements specification, function oriented design using SA/SD, object-oriented design using UML, test case design, implementation using Java and testing. Use of appropriate CASE tools and other tools such as configuration management tools, program analysis tools in the software life cycle.

References
1. Rajib Mall, Fundamentals of Software Engineering, Prentice Hall India.
2. Pankaj Jalote, An integrated approach to Software Engineering, Springer/Narosa.
3. Roger S. Pressman, Software Engineering: A practitioner's approach, McGraw Hill.
4. Ian Sommerville, Software Engineering, Addison-Wesley.


CS21001 DISCRETE STRUCTURES L-T-P: 3-1-0, Credit: 4
Propositional logic: Syntax, semantics, valid, satisfiable and unsatisfiable formulas, encoding and examining the validity of some logical arguments.
Proof techniques: forward proof, proof by contradiction, contrapositive proofs, proof of necessity and sufficiency.
Sets, relations and functions: Operations on sets, relations and functions, binary relations, partial ordering relations, equivalence relations, principles of mathematical induction.

Size of a set: Finite and infinite sets, countable and uncountable sets, Cantor's diagonal argument and the power set theorem, Schroeder-Bernstein theorem.

Introduction to counting: Basic counting techniques - inclusion and exclusion, pigeon-hole principle, permutation, combination, summations. Introduction to recurrence relation and generating function.
Algebraic structures and morphisms: Algebraic structures with one binary operation - semigroups, monoids and groups, congruence relation and quotient structures. Free and cyclic monoids and groups, permutation groups, substructures, normal subgroups. Algebraic structures with two binary operations - rings, integral domains and fields. Boolean algebra and Boolean ring.
Introduction to graphs: Graphs and their basic properties - degree, path, cycle, subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs, trees.

References
1. Kenneth H. Rosen, Discrete Mathematics and its Applications, Tata McGraw-Hill.
2. C. L. Liu, Elements of Discrete Mathematics, Tata McGraw-Hill.
3. Norman L. Biggs, Discrete Mathematics, Oxford University Press.
4. Kenneth Bogart, Clifford Stein and Robert L. Drysdale, Discrete Mathematics for Computer Science, Key College Publishing.
5. Thomas Koshy, Discrete Mathematics with Applications, Elsevier.
6. Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, Pearson Education, Asia.

CS21002 SWITCHING CIRCUITS AND LOGIC DESIGN L-T-P: 3-1-0, Credit: 4
Switching Circuits: Logic families: TTL, nMOS, CMOS, dynamic CMOS and pass transistor logic (PTL) circuits, inverters and other logic gates, area, power and delay characteristics, concepts of fan-in, fan-out and noise margin.

Switching theory: Boolean algebra, logic gates, and switching functions, truth tables and switching expressions, minimization of completely and incompletely specified switching functions, Karnaugh map and Quine-McCluskey method, multiple output minimization, representation and manipulation of functions using BDD's, two-level and multi-level logic circuit synthesis.

Combinational logic circuits: Realization of Boolean functions using NAND/NOR gates, Decoders, multiplexers. logic design using ROMs, PLAs and FPGAs. Case studies.

Sequential circuits: Clocks, flip-flops, latches, counters and shift registers, finite-state machine model, synthesis of synchronous sequential circuits, minimization and state assignment, asynchronous sequential circuit synthesis.

ASM charts: Representation of sequential circuits using ASM charts, synthesis of output and next state functions, data path control path partition-based design.

CS29002 Switching Laboratory
L-T-P: 0-0-3, Credit: 2

Pulse Circuits: Bistable, astable and monostable MVs and Schmitt Triggers using transistors, OP Amps and 555 timers.
TTL and CMOS Gates: Study the characteristics of TTL and MOS gates.
Combinational logic circuits: Design and implementation of combinational circuits such as ALU and 7-segment LED display driver.
Sequential Circuits: Design of sequence generators and detectors, counters, design of ASMs such as, traffic light controllers, lift controllers, etc.

References
1. H. Taub and D. Schilling, Digital Integrated Electronics, McGraw-Hill .
2. Z. Kohavi, Switching and Finite Automata Theory, Tata McGraw-Hill.
3. Randy H. Katz and Gaetano Borriello, Contemporary Logic Design, Prentice Hall of India.
4. Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, Tata McGraw-Hill.

CS21003 ALGORITHMS I L-T-P: 3-1-0, Credit: 4
Asymptotic notations and their significance, introduction to RAM model of computation, complexity analysis of algorithms, worst case and average case.
Basic introduction to algorithmic paradigms like divide and conquer, recursion, greedy, etc.
Searching: binary search trees, balanced binary search trees, AVL trees and red-black trees, B-trees, skip lists, hashing. Priority queues, heaps, Interval trees, tries.
Order statistics.

Sorting: comparison based sorting - quick sort, heap sort, merge sort: worst and average case analysis. Decision tree model and (worst case) lower bound on sorting. Sorting in linear time - radix sort, bucket sort, counting sort, etc.
String matching

Graph Algorithms: BFS, DFS, connected components, topological sort, minimum spanning trees, shortest paths - single source and all pairs.
CS29003 Algorithms Laboratory

L-T-P: 0-0-3, Credit: 2
The laboratory component will emphasize two areas:
Implementation of algorithms covered in class: This will involve running the algorithms under varying input sets and measuring running times, use of different data structures for the same algorithm (wherever applicable) to see its effect on time and space, comparison of different algorithms for the same problem etc.

Design of Algorithms: This will involve design and implementation of algorithms for problems not covered in class but related to topics covered in class.
The exact set of algorithms to design and implement is to be decided by the instructor. In addition, there will be at least one significantly large design project involving some real world application. An efficient design of the project should require the use of multiple data structures and a combination of different algorithms/techniques.

References
1. T. H. Cormen, C. L. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press.
2. J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley.
3. Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins.
4. A. Gibbons, Algorithmic Graph Theory, Cambridge University Press.
5. Michael T. Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley.
6. R. Sedgewick, Algorithms in C (Parts 1-5), Addison Wesley.
7. M. H. Alsuwaiyel, Algorithm Design Techniques and Analysis, World Scientific.
8. Gilles Brassard and Paul Bratley, Algorithmics : theory and practice, Prentice-Hall.
9. Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley.
10. Sara Baase and Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley.

CS21004 FORMAL LANGUAGES AND AUTOMATA THEORY L-T-P: 3-1-0, Credit: 4
Introduction: Alphabet, languages and grammars, productions and derivation, Chomsky hierarchy of languages.

Regular languages and finite automata: Regular expressions and languages, deterministic finite automata (DFA) and equivalence with regular expressions, nondeterministic finite automata (NFA) and equivalence with DFA, regular grammars and equivalence with finite automata, properties of regular languages, pumping lemma for regular languages, minimization of finite automata.

Context-free languages and pushdown automata: Context-free grammars (CFG) and languages (CFL), Chomsky and Greibach normal forms, nondeterministic pushdown automata (PDA) and equivalence with CFG, parse trees, ambiguity in CFG, pumping lemma for context-free languages, deterministic pushdown automata, closure properties of CFLs.

Context-sensitive languages: Context-sensitive grammars (CSG) and languages, linear bounded automata and equivalence with CSG.

Turing machines: The basic model for Turing machines (TM), Turing-recognizable (recursively enumerable) and Turing-decidable (recursive) languages and their closure properties, variants of Turing machines, nondeterministic TMs and equivalence with deterministic TMs, unrestricted grammars and equivalence with Turing machines, TMs as enumerators.
Undecidability: Church-Turing thesis, universal Turing machine, the universal and diagonalization languages, reduction between languages and Rice's theorem, undecidable problems about languages.

References
1. Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia.
2. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education Asia.
3. Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer.
4. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.
5. John Martin, Introduction to Languages and The Theory of Computation, Tata McGraw Hill.

CS30002 OPERATING SYSTEMS L-T-P: 3-0-0, Credit: 3

Evolution of Operating Systems, Structural overview, Concept of process and Process synchronization, Process Management and Scheduling, Hardware requirements: protection, context switching, privileged mode; Threads and their Management; Tools and Constructs for Concurrency, Detection and Prevention of deadlocks, Dynamic Resource Allocation, Design of IO systems, File Management, Memory Management: paging, virtual memory management, Distributed and Multiprocessor Systems, Case Studies

CS39002 Operating Systems Laboratory
L-T-P: 0-0-3, Credit: 2
Familiarization with UNIX system calls for process management and inter-process communication; Experiments on process scheduling and other operating system tasks through simulation/implementation under a simulated environment (like Nachos).

References
1. Avi Silberschatz, Peter Galvin, Greg Gagne, Operating System Concepts, Wiley Asia Student Edition.
2. William Stallings, Operating Systems: Internals and Design Principles, Prentice Hall of India.
3. D. M. Dhamdhere, Operating Systems: A Concept-Based Approach, Tata McGraw-Hill.
4. Charles Crowley, Operating System: A Design-oriented Approach, Irwin Publishing.
5. Gary J. Nutt, Operating Systems: A Modern Perspective, Addison-Wesley.
6. Maurice Bach, Design of the Unix Operating Systems, Prentice-Hall of India.
7. Daniel P. Bovet, Marco Cesati, Understanding the Linux Kernel, O'Reilly and Associates.

CS30003 COMPILERS L-T-P: 3-0-0, Credit: 3
The aim is to learn how to design and implement a compiler and also to study the underlying theories. The main emphasis is for the imperative languages.

Introduction: Phases of compilation and overview.
Lexical Analysis (scanner): Regular language, finite automata, regular expression, from regular expression to finite automata, scanner generator (lex,flex).

Syntax Analysis (Parser): Context-free language and grammar, push-down automata, LL(1) grammar and top-down parsing, operator grammar, LR(O), SLR(1), LR(1), LALR(1) grammars and bottom-up parsing, ambiguity and LR parsing, LALR(1) parser generator (yacc,bison)

Semantic Analysis: Attribute grammar, syntax directed definition, evaluation and flow of attribute in a syntax tree.
Symbol Table: Its structure, symbol attributes and management.
Run-time environment: Procedure activation, parameter passing, value return, memory allocation, and scope.

Intermediate Code Generation: Translation of different language features, different types of intermediate forms.

Code Improvement (optimization): Analysis: control-flow, data-flow dependence etc.; Code improvement local optimization, global optimization, loop optimization, peep-hole optimization etc. Architecture dependent code improvement: instruction scheduling (for pipeline), loop optimization (for cache memory) etc.
Register allocation and target code generation

Advanced topics: Type systems, data abstraction, compilation of object oriented features and non-imperative programming languages.


For detailed syllabus, here is attachment;’