Computer Science and Engineering - Knol Books - Catalogue
IIT Kanpur
CS 201: Discrete Mathematics
Structure: 3-0-0-0 Academic Load=9 Weightage=3
Course Contents:
Notion of proof: proof by counter-example, the contrapositive, proof by contradiction, inductive proofs.Algebra: Motivation of algebraic structures; review of basic group theory with emphasis to finite groups: subgroups and group homomorphism, Lagrange's theorem. Commutative rings, ideals. Finite fields and their elementary properties. Some CS applications (e.g., RSA, error correcting codes).
Combinatorics: Basic counting techniques, pigeon-hole principle, recurrence relations, generating functions, Polya's counting theorem. Basics of graph theory. Introduction to probabilistic method in combinatorics.
Formal logic: Propositional logic: proof system, semantics, completeness, compactness. Length of proofs, polynomial size proofs, efficiency of proof systems. First order logic: models, proof system, compactness. Examples of formal proofs in, say, number theory or group theory. Some advanced topics. E.g., CS application of logic, introduction to modal and temporal logics, Or, formal number theory including incompleteness theorem, Or, elements of proof theory including cut elimination, Or zero-one law for first order logic.
CS 210: Data Structures and Algorithms
Structure: 3-0-0-0 Academic Load=9 Weightage=3
Prerequisite: ESC 101
Course Contents:
Order Analysis: Objectives of time analysis of algorithms; Big-oh and Theta notations.Elementary Data Structures: Arrays, Linked lists, Stacks (example: expression evaluation), and Queues. Binary search trees. Red-Black trees. Hash tables.
Sorting and Divide and Conquer Strategy: Merge-sort; D-and-C with Matrix Multiplication as another example. Quick-sort with average case analysis. Heaps and heap-sort. Lower bound on comparison-based sorting and Counting sort. Radix sort.
B-trees.
Dynamic Programming: methodology and examples (Fibonacci numbers, matrix sequence multiplication, longest common subsequence, convex polygon triangulation).
Greedy Method: Methodology, examples (lecture scheduling, process scheduling) and comparison with DP (more examples to come later in graph algorithms).
Graph Algorithms: Basics of graphs and their representations. BFS. DFS. Topological sorting. Minimum spanning trees (Kruskal and Prim's algorithms and brief discussions of disjoint set and Fibonacci heap data structures). Shortest Paths (Dijkstra, Bellman-Ford, Floyd-Warshall).
Data Structures - Knol Book
Algorithms - Design, Analysis & Improvement and Applications - Knol BookCS 220: Introduction to Computer Organisation
Structure: 3-0-2-0 Academic Load=12 Weightage=4
Prerequisite: ESC 102
Course Contents:
Introduction: Overview of basic digital building blocks; truth tables; basic structure of a digital computer.Number representation: Integer - unsigned, signed (sign magnitude, 1's complement, 2's complement, r's complement); Characters - ASCII coding, other coding schemes; Real numbers - fixed and floating point, IEEE754 representation.
Assembly language programming for some processor.
Basic building blocks for the ALU: Adder, Subtractor, Shifter, Multiplication and division circuits.
CPU Subblock: Datapath - ALU, Registers, CPU buses; Control path - microprogramming (only the idea), hardwired logic; External interface.
Memory Subblock: Memory organization; Technology - ROM, RAM, EPROM, Flash, etc. Cache; Cache coherence protocol for uniprocessor (simple).
I/O Subblock: I/O techniques - interrupts, polling, DMA; Synchronous vs. Asynchronous I/O; Controllers.
Peripherals: Disk drives; Printers - impact, dot matrix, ink jet, laser; Plotters; Keyboards; Monitors.
Advanced Concepts: Pipelining; Introduction to Advanced Processors.
Computer Architecture & Organization - Knol Book
CS 315: Principles of Data Base Systems
Course Contents:
Overview of file organisation techniques: sequential, direct, indexed, hashed, inverted, B-trees.Data models: relational, network, hierarchical.
Relational model: algebra, calculus, normal forms. Implementation of query languages, security and protection of data recovery methods.
Concurrent operations on data bases, introduction to distributed data base systems, case studies.
Books and References:
R. El. Masri and S. B. Navathe. Fundamentals of Data Base Systems , Benjamin Cummings, 1989.H. F. Korth and A. Silberschatz. Database Concepts , 2nd Edition, Mcgraw Hill, 1991.
J. D. Ullman. Principles of Database and Knowledge Base Systems , Vol. I & II, Computer Science Press, 1988.
Database Management Systems (DBMS) - Knol Book
CS 330: Operating Systems
Course Contents:
Introduction.
Process management: process synchronization and mutual exclusion, two process solution and Dekker's algorithm, semaphores, examples (producer-consumer, readers-writer, dining philosophers, etc.).
CPU scheduling: multiprogramming and time sharing, scheduling approaches (SJF, FIFO, round robin, etc.).
Input/Output: device controllers and device drivers, disks, other devices.
Memory management: with and without swapping, virtual memory - paging and segmentation, page replacement algorithms, implementation.
File systems: FS services, disk space management, directory and data structure.
Deadlocks: modeling, detection and recovery, prevention and avoidance.
Example Systems: Unix, MSDOS.
Books and References:
J. Peterson, A. Silberschatz, and P. Galvin. Operating System Concepts , Addison Wesley, 3rd Edition, 1989.M. J. Bach. Design of the Unix Operating System , Prentice Hall of India, 1986.
A. Silberschatz and P. Galvin. Operating System Concepts , Addison Wesley, 4th Edition, 1994.
CS 335: Principles of Compiler Design
Course Contents:
Compiler structure: analysis-synthesis model of compilation, various phases of a compiler, tool based approach to compiler construction.Lexical analysis: interface with input, parser and symbol table, token, lexeme and patterns. Difficulties in lexical analysis. Error reporting. Implementation. Regular definition, Transition diagrams, LEX.
Syntax analysis: CFGs, ambiguity, associativity, precedence, top down parsing, recursive descent parsing, transformation on the grammars, predictive parsing, bottom up parsing, operator precedence grammars, LR parsers (SLR, LALR, LR), YACC.
Syntax directed definitions: inherited and synthesized attributes, dependency graph, evaluation order, bottom up and top down evaluation of attributes, L- and S-attributed definitions.
Type checking: type system, type expressions, structural and name equivalence of types, type conversion, overloaded functions and operators, polymorphic functions.
Run time system: storage organization, activation tree, activation record, parameter passing, symbol table, dynamic storage allocation.
Intermediate code generation: intermediate representations, translation of declarations, assignments, control flow, boolean expressions and procedure calls. Implementation issues.
Code generation and instruction selection: issues, basic blocks and flow graphs, register allocation, code generation, dag representation of programs, code generation from dags, peep hole optimization, code generator generators, specifications of machine.
Books and References:
A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools , Addison-Wesley, 1988.C. Fischer and R. LeBlanc. Crafting a Compiler , Benjamin Cummings, 1991.
C. Fischer and R. LeBlanc. Crafting a Compiler in C , Benjamin Cummings.
A. C. Holub. Compiler Design in C , Prentice-Hall Inc., 1993.
Appel. Modern Compiler Implementation in C: Basic Design , Cambridge Press.
Appel. Modern Compiler Implementation in Java: Basic Design , Cambridge Press.
Fraser and Hanson. A Retargetable C Compiler: Design and Implementation , Addison-Wesley.
Dhamdhere. Compiler Construction , McMillan India.
Holmes. Object Oriented Compiler Construction , Prentice Hall.
Holmes. Building your own Compiler with C++ , Prentice Hall.
Wirth. Compiler Construction , Addison-Wesley.
Wilhelm and Maurer. Compiler Design , Addison-Wesley.
Any other book on Compilers: check central library
Reference to Programming Languages: search central library.
You may look at comp.compilers newsgroup from time to time: http://www.iecc.com/compiler .
CS 340: Theory of Computation
Course Contents:
Models of computation -- classification, properties and equivalences.Regular languages models: finite state machines (deterministic and non-deterministic), regular grammars, regular expressions, equivalence of deterministic and non-deterministic machines and of the three models. Properties: closure, decidability, minimality of automata, iteration theorems.
Recursive and recursively enumerable sets models: turing machines, grammars, recursive functions, their equivalence. Church's thesis. Properties: closure, decidability, undecidablity/non-computability, notion of reductions.
Context-free languages models: grammars (including different normal forms), pushdown automata, and their equivalence. Properties: closure, iteration theorems, parsing.
Books and References:
C. Papadimitrou and C. L. Lewis. Elements of Theory of Computation , Prentice-Hall, 1981.J.E. Hopcroft and J.D. Ullman. Introduction to Antomata Theory, Languages of Computations , Addison-Wesley, 1979. (Indian edition available from Narosa.)
CS 345: Algorithms II
Structure: 3-0-2-0 Academic Load=12 Weightage=4
Prerequisite: CS 201, CS 210
Course Contents:
Max Flows: Max Flows (Ford-Fulkerson and bipartite matching).Linear Algebra: LUP decomposition, inverting matrices.
Fast Fourier Transform. Polynomial multiplication, integer multiplication and division.
Number-theoretic Algorithms: GCD, Modulo arithmetic, Chinese remaindering, RSA.
Linear Programming: formulation, simplex, primal-dual.
Geometric algorithms: convex hull, closest pair, intersection of line segments, polygon triangulation.
Randomized Algorithms: identity testing, primality and min-cut.
Approximation Algorithms: max-cut, tsp, vertex-cover etc.
Backtracking.
Other topics: these may include string matching, parallel algorithms, amortized analysis, etc.
Books and References:
Cormen, Leiserson, and Rivest. Algorithms , MIT Press, 1990.A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms , Addison Wesley, 1974.
E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms , Galgotia, 1991.
CS 350: Principles of Programming Languages
Course Contents:
The basic thrust of this course will be on learning the distinctive techniques in the different paradigms and what semantic and compiling issues come up in the various languages considered.Imperative Languages: block structure, scope rules, parameter passing, constructs like coroutines, tasks etc.
Functional programming: functions, recursion, macros, user-defined control constructs, higher order constructs, types, data abstraction, polymorphism, semantics, implementation issues.
Declarative programming: declarative programming, Horn clauses, procedural interprettation of Horn clauses, SLD-resolution including unification, the logical variable, implementation issues: abstract machines and compiling to abstract machines.
Object-oriented programming: objects and programming with objects, classes and instances, hierarchies and inheritance, encapsulation, semantics of OO languages and implementation issues.
Books and References:
D. A. Watt. Programming Languages and Paradigms , Prentice-Hall, 1990.J. LLoyd. Foundations of Logic Programming , Springer Verlag, 1984.
M. Hennessey. The Semantics of Programming Languages , John Wiley, 1990.
Luca Cardelli and P. Wegner. On Understanding Types, Data Abstraction and Polymorphism , Computing Surveys, 17(4), pp 471, 1985.
C. Reade. Elements of Functional Programming , Addison Wesley, 1989.
L. C. Paulson. ML for Working Programmer , Cambridge University Press, 1991.
B. Stroustrup. The C++ Programming Language , Addison Wesley.
Computer Programs and Programming Languages - Knol Book
CS 355: Programming Tools and Techniques
Course Contents:
Software mangement tools such as SCCS and make; Programming tools such as Perl, Tcl/Tk; Proramming in the windows environment; Document preparation systems such as tex and metafont; Programming pearls.CS 360: Introduction to Computer Graphics and Simulation
Course Contents:
Introduction to Picture Synthesis and Analysis. Conceptual Framework of an Interactive Graphical Simulation System.
Graphics hardware. Basic Raster Graphics Algorithms. Introduction to Simple Raster Graphics Package (SRGP).
Graphics Entities. Geometric Transformations. Object hierarchy. Segmentation. Interaction Techniques.
Geometric Modeling in 3-D. Viewing in 3-D. Concept of Synthetic Camera.
Dialogue Design. Graphics User Interfaces. Windowing Systems.
Graphical Modeling of Discrete events. Simulation of Discrete Event Displays. Animation Techniques. Basic Rules for Animation. Graphical Simulation of continuous motion. Role of Virtual Reality in Graphical Simulation.
Books and References:
James D. Foley, Andries VanDam, Feiner Steven K. and Hughes John F. Computer Graphics: Principle and Practice, Addison-Wesley Publishing House.Foley and VanDam. Fundamentals of Interactive Computer Graphics, Addison-Wesley.
Rogers D. F. Procedural Elements of Computer Graphics, McGraw Hill.
Dennis Harris. Computer Graphics and Applications,
Hearn and Baker. Computer Graphics, Prentice Hall of India.
CS 365: Artificial Intelligence
Course Contents:
Introduction to AI. Agents and environments. Problem solving by search; uninformed search, informed ("heuristic") search, constrained satisfaction problems, adversarial search, Knowledge representation and reasoning; rule based representations, logical formalisms, frames or object oriented systems, network based approaches and mixed representations. Theorem-proving. Knowledge bases and expert systems. Overview of LISP and PROLOG. Reasoning in uncertain environments. Planning communication and multiagent systems. Learning. Vision. Natural Language Processing.Books and References:
Charniak and Mcdermott. Introduction to Artificial Intelligence , Addison-Wesley, 1985.Ginsburg. Essentials of Artificial Intelligence , Morgan Kaufmann, 1993.
Winston. Artificial Intelligence , 3rd Edition, Addison Wesley, 1992.
CS 422: Computer Architecture
Course Contents:
Introduction: Overview of Computer Architecture, Performance evaluation of processors, pipelining, super-pipelines, Advanced pipelines, static and dynamic scheduling, instruction-level parallelism, loop unrolling, VLIW and Super scalar processors, Vector processing and array processing.Memory: bandwith issues, memory organization, cache coherence, Symmetric multiprocessors (SMP), NUMA-MPs, Massively parallel processors, Cache coherence protocols, Interconnection networks, I/O processing, multiprocessing, multiplexing, Examples of contemporary architectures, RAS (Reliability, Availability, Scalability) features.
Computer Architecture & Organization - Knol Book
Computer Architecture - IIT Video Lectures
CS 425: Computer Networks
Course Contents:
Introduction, history and development of computer networks, networks topologies.Physical Layer: theoretical basis, transmission media, analog transmission, digital transmission, switching.
MAC layer: Aloha protocols, local area networks -- Ethernet, token ring, FDDI. Data link layer: sliding window protocols.
Network layer: routing algorithms, congestion control algorithms, internetwroking -- bridges and routers.
Transport layer. Session, presentation, and application Layers. Use of TCP/IP protocol suite as running example.
Introduction to X.25, ISO protocols.
Books and References:
A. S. Tannenbaum. Computer Networks , 2nd Edition, Prentice-Hall, 1988.D. E. Comer. Internetworking with TCP-IP: Principles, Protocols and Architecture , Vol I, 2nd Edition, Prentice Hall, 1991.
D. E. Comer and D. L. Stevens. Internetworking with TCP-IP: Design, Implementation, and Internals , Vol II, Prentice Hall, 1990.
D. Bertsekas and R. Gallagar. Data Networks , 2nd Edition, Prentice Hall, 1992.
W. R. Stevens. UNIX Network Programming , Prentice Hall, 1990.
CS 455: Software Engineering
Course Contents:
This course will cover the techniques for development of software systems, commonly referred to as Software Engineering. It is intended to give the students both knowledge about, and practical experience in, the design and development of production quality software. The software engineering techniques taught in the class will be applied on a substantial team project.
Course topics will be as follows: Software development life cycle; Process models; Requirements; Specifications; Software design; Structured programming and implementation; Testing; Verification and validation; Software Metrics; Software Project management.
Books and References:
Pankaj Jalote. An Integrated Approach to Software Engineering , 2nd edition, Narosa Publishing House.S. L. Pfleeger. Software Engineering , MacMillan Publishing Company, 1987.
Roger Pressman. Software Engineering: A Practitioner's Approach , 4th edition, McGraw-Hill Publishing.
Ghazzi.
Software Engineering, Testing and Project Management - Knol Book
