# UG Courses

**B. Tech in Computer Science and Engineering**

**CSL105 Discrete Mathematical Structures, 4 (3-1-0)**

Prerequisites: Nil

Fundamental structures using sets. Functions (surjections, injections, inverses, composition); relations (reflexivity, symmetry, transitivity, equivalence relations); sets (union, intersection, complements, Cartesian products, power sets); pigeonhole principle; cardinality and countability. Syntax and semantics of logic: Propositional logic: logical connectives; truth tables; normal forms (conjunctive and disjunctive); validity. First-order logic; limitations of predicate logic, universal and existential quantification; modus ponens and modus tollens. Elementary Proof techniques: Notions of implication, converse, inverse, contrapositive, negation, and contradiction; the structure of formal proofs; direct proofs; proof by counterexample; proof by contraposition; proof by contradiction; mathematical induction; strong induction; recursive mathematical definitions; well orderings. Basics of counting: Counting arguments; pigeonhole principle; permutations and combinations; inclusion-exclusion, recurrence relations, generating functions. Elementary Graph Theory.

**CSL201 Data Structures, 5 (3-0-4)**

Prerequisites: Introduction to Computing.

Revision of notions of time and space complexity, and trade-offs in the design of data structures. Introduction to object-oriented programming through stacks, queues and linked lists. Dictionaries; skip-lists, hashing, analysis of collision resolution techniques. Trees, traversals, binary search trees. Balanced BSTs, tries, priority queues and binary heaps. Object oriented implementation and building libraries. Applications to discrete event simulation. Sorting: merge, quick, radix, selection and heap sort, Graphs: Breadth first search and connected components. Depth first search in directed and undirected graphs. Union-find data structure and applications. Directed acyclic graphs; topological sort.

**CSL202 Programming Paradigms and Pragmatics, 5 (3-0-4)**

Prerequisites: Data Structures

Notions of syntax and semantics of programming languages; introduction to operational and mathematical semantics of declarative (functional and logic) and imperative languages. Exposure to different programming language paradigms. Data abstractions and control constructs; block-structure and scope, principles of abstraction, qualification and correspondence; parameter passing mechanisms; runtime structure and operating environment; practical and implementation issues in run-time systems and environment; abstract machines; features of functional and imperative languages. The untyped and simply-typed Lambda calculus, type systems for programming languages including simple types and polymorphism; objects; classes and inheritance in object-oriented languages.

**CSP203 Software Systems Laboratory, 2 (0-0-4)**

Prerequisites: Data Structures.

Programming exercises and projects using software tools. IDEs, spreadsheets, configuration management, make, version control, documentation tools, literate programming (noweb); scientific document type-setting software (LaTeX), XML, scripting languages and tools (Perl, awk, etc). Booting systems, and installation and compression tools. Archiving and creation of libraries. Security and encryption software. Application software development tools. Simulation tools, Sockets and RPCs, pthreads. Numerical packages. Using query languages and data bases. Validation, testing and verification tools and techniques.

**CSL211 Computer Architecture, 5 (3-1-2)**

Prerequisites: Introduction to Computing; and Principles of Electrical Engineering

Suggested additional background: Digital Electronic Circuits.

Subsystems of a computer; Instructions and their formats; Assembly programming; Performance metrics; Performance comparison; Information representation; Integer and floating point arithmetic; Processor data-path design; Control unit design; Microprogramming; Performance improvement with pipelining; Memory organization - cache and virtual memory; input/output organization, interrupts and DMA.

**CSL333 Operating Systems, 4 (3-0-4)**

Prerequisites: Data Structures, and Computer Architecture

Overview: functions of Operating Systems, layered architecture basic concepts; interrupt architecture, system calls and notion of process and threads; synchronization and protection issues; scheduling; memory management including virtual memory and paging techniques; input-output architecture and device management; file systems; distributed file systems. Case studies of Unix, Windows NT. Design and implementation of small operating systems.

**CSL343 Computer Networks, 4.5 (3-0-3)**

Prerequisites: Data Structures

Suggested additional background: Signals and Systems, and Operating Systems

Fundamentals of Digital Communications, including channel capacity, error rates, multiplexing, framing and synchronization. Broadcast network and multi-access protocols, including CSMA/CD. Data link protocols, network protocols including routing and congestion control, IP protocol. Transport protocol including TCP. Network application services and protocols including email, www, DNS. Network security and management.

**CSL355 Logic and Computability, 4 (3-1-0)**

Prerequisites: Discrete Mathematical Structures

Suggested additional background: Logic for Computer Science

Myhill-Nerode Theorem, introduction to non-determinism, Context free grammars, Pushdown automata, equivalence and applications. Turing machines, Recursive and Recursively enumerable sets, non-determinism, RAMs and equivalence, Universal Turing Machines, undecidability, Rice's theorems for RE sets, Post machines, Basics of Recursive function theory. Equivalence, Church's thesis, computational complexity, space and time complexity of Turing Machines, Relationships, Savage's theorem, Complexity classes, Complete problems, NP-completeness, Cook-Levin theorem.

**CSL356 Analysis and Design of Algorithms, 4 (3-1-0)**

Prerequisites: Discrete Mathematical Structures, and Data Structures

RAM model and complexity; O(log n) bit model, integer sorting and string sorting. Review of fundamental data structures; Red-black trees, mergeable heaps, interval trees. Fundamental design methodologies and their implementations; Search Techniques, Dynamic Programming, Greedy algorithms, Divide-and-Conquer, Randomised techniques. Algorithms for set manipulations, their implementations and applications; Union-Find Randomized data structures; Skip lists, Universal Hash functions, Graph Algorithms with implementation issues; Depth-First Search and its applications, minimum Spanning Trees and Shortest Paths. Convex hulls, sorting, Selection Matrix multiplication, pattern matching, integer and polynomial arithmetic, FFT, introduction to the theory of lower bounds, NP-Completeness and Reductions. Approximation algorithms.

**ELECTIVE COURSES**

**CSL311 Introduction to Database Systems, 4 (3-0-2)**

Prerequisites: Data Structures.

The world of Database Systems. The E-R Model, The three database models, Representation and Evaluation of Relationship. The Relational Database Model, Functional Dependencies, Multi-valued and join dependency, Normalization theory, Concurrency Control in Relational Databases. Object-oriented Data Models.

**CSL312 Artificial Intelligence, 4 (3-0-2)**** **

Prerequisites: Data Structures.

Problem solving, search techniques, control strategies, game playing (mini-max), reasoning, knowledge representation through predicate logic, rule-based systems, semantic nets, frames, conceptual dependency formalism. Planning. Handling uncertainty: Bayesian Networks, Dempster-Shafer theory, certainty factors, Fuzzy logic, Learning through Neural nets -- Back propagation, radial basis functions, Neural computational models - Hopfield Nets, Bolzman machines. PROLOG programming.

**CSL313 Logic for Computer Science, 4 (3-0-2)**

Prerequisites: Discrete Mathematical Structures

Review of the principle of mathematical induction; the principle of structural induction; review of Boolean algebras; Syntax of propositional formulas; Truth and the semantics of propositional logic; Notions of satisfiability, validity, inconsistency; Deduction systems for propositional logic; Soundness and Completeness of deduction systems; First order logic (FOL): syntax and semantics; Proof theory for FOL; introduction to model theory; completeness and compactness theorems; First order theories. Introduction to modal logics. Programming exercises will include representation and evaluation; conversion to normal-forms; tautology checking; proof normalization; resolution; unification; Skolemization, conversion to Horn-clauses; binary-decision diagrams.

**CSL314 Numerical and Scientific Computing, 5 (3-1-2)**

Prerequisites: Introduction to Computing, Linear Algebra

Introduction to Scientific Computing (floating point arithmetic). Review of matrices and linear systems, Linear Least Squares, Eigenvalue Problems. Review of Singular value decomposition. Direct methods: Gauss, Cholesky and Householder’s methods, Matrix iterative methods: Jacobi, Gauss-Siedel and relaxation methods, conjugate gradient methods and its pre-conditioning, Computation of Eigenvalues and Eigenvectors: Jacobi, Givens, Householder, QR and inverse methods. Nonlinear Equations. Optimization, interpolation, Numerical integration and Differentiation, Initial and Boundary Value Problems for Ordinary Differential Equations. Partial Differential Equations, Fast Fourier Transform. Throughout the course implementation of the various methods and their comparisons with professionally written software such as LINPAC, ITPACK, EISPACK, LAPACK, SPARSE PACK will be emphasized with the understanding of various data structures, storage schemes etc. Existence and uniqueness, sensitivity and condition, convergence and error analysis will be part of every topic.

**CSL315 Compiler Design, 4 (3-0-2)**

Prerequisites: Programming Paradigms and Pragmatics

Suggested additional background: Logic and Computability.

Compilers and translators; lexical and syntactic analysis, top-down and bottom up parsing techniques; internal form of source programs; semantic analysis, symbol tables, error detection and recovery, code generation and optimization. Data flow and control flow analysis. Type checking and static analysis. Algorithms and implementation techniques for type-checking, code generation and optimization. Students will design and implement translators, static analysis, type-checking and optimization.

**CSL316 Software Engineering, 4 (3-0-2)**

Prerequisites: Data Structures, Programming Paradigms and Pragmatics.

Concepts and techniques relevant to production of large software systems: Structured programming,

Requirements specification and analysis . Top-down design and development, Information hiding, abstraction, modularity, object-oriented techniques. Separate compilation, configuration management, program libraries Design patterns, UML Documentation, validation, Quality assurance, safety, Testing and test case generation, Software metrics, Cost analysis and estimation, manpower and time management. Organization and management of large software design projects. Constraints and triggers, Disk Storage, Disk and Memory Organization for Relational Operators, Representing Data Elements, Index Structures, Query execution, Query Compilation, Query Optimization, Coping with System Failures, Concurrency Control, Transaction Management, Representation of Date.

**CSL317 Computer Graphics, 4 (3-0-2)**

Prerequisites: Data Structures

Graphics pipeline; Graphics hardware: Display devices, input devices; Raster Graphics; line and circle drawing algorithms; Windowing and 2D/3D clipping. Cohen and Sutherland line clipping, Cyrus Beck clipping method; 2D and 3D Geometrical Transformations: scaling, translation, rotation, reflection; Viewing Transformations: parallel and perspective projection; Curves and Surfaces: cubic splines, Bezier curves, B-splines, Parametric surfaces. Surface of revolution Sweep surfaces, Fractal curves and surfaces; Hidden line / surface removal methods; illuminations model; shading: Gouraud, Phong; Introduction to Ray-tracing; Animation; Programming practices with standard graphics libraries like openGL.

**CSL319 Architecture of High Performance Computers, 4 (3-0-2)**

Prerequisites: Computer Architecture; Operating Systems.

Classification of parallel computing structures, instruction level parallelism - static and dynamic pipelining, improving branch performance, superscalar and VLIW processors; High performance memory system; Shared memory multiprocessors and cache coherence; Multiprocessor interconnection networks; Performance modeling; issues in programming multiprocessors; Data parallel architectures.

**CSL401 Advanced Algorithms, 4 (3-0-0)**

Prerequisites: Analysis and Design of Algorithms.

Advanced data structures: self-adjustment, persistence and multi-dimensional trees. Randomized algorithms: Use of probabilistic inequalities in analysis, Geometric algorithms; Point location, Convex hulls and Voronoi diagrams. Arrangements applications using examples, Graph algorithms; Matching and Flows. Approximation algorithms; Use of Linear programming and primal dual, local search heuristics. Parallel algorithms; Basic techniques for sorting, searching merging, list ranking in PRAMs, and interconnection networks.

**CSL402 Digital Image Analysis, 4 (3-0-2)**

Prerequisites: Data Structures; Signals and Systems.

Digital Image Fundamentals; Image Enhancement in Spatial Domain; Gray Level Transformation, Histogram Processing, Spatial Filters; Image Transforms; Fourier Transform and their properties, Fast Fourier Transform, Other Transforms; Image Enhancement in Frequency Domain; Colour Image Processing; Image warping and restoration; Image Compression; Image Segmentation; edge detection, Hough transform, region based segmentation; Morphological operators; Representation and Description; Features based matching and Bayes classification; Introduction to some computer vision techniques; Imaging geometry, shape from shading, optical flow; Laboratory exercises will emphasize development and evaluation of image processing methods.

**CSL404 Computer Vision, 4 (3-0-2)**

Camera models, Calibration, multi-views projective geometry and invariants. Edge/feature extraction, correspondence and tracking, 3D structure/motion estimation. Object recognition, Scene and activity interpretation.

**CSL405 Complexity Theory, 3 (3-0-0)**

Prerequisites: Logic and Computability, Analysis and Design of Algorithms.

Turing machines and non-determinism, models of computation like RAM and pointer machines. Relations between complexity classes. Time-space tradeoffs for some fundamental problems. Reductions and completeness, Randomized complexity classes, Boolean circuit complexity. Cryptography and one-way functions. Polynomial hierarchy, P-space completeness, Interactive proofs and Hardness of approximation, Parallel complexity classes.

**CSL406 Advanced Computer Networks, 4 (3-0-0)**

Prerequisites: Computer Networks.

Flow and Congestion Control; Window and Rate Based Schemes, Decbit, TCP. ATM, ABR, hop-by-hop schemes, Quality of Service: in ATM, IETF integrated services model, Differentiated Services Model. Flow identification, Packet Classifiers and Filters. Scheduling. Network Management: ASN, SNMP, CMIP. Issues in the management of large networks. Multicast: IGMP, PIM, DVMRP, Mobility: Mobile IP.

**CSL468 Special Topics in Computer Science, 2 (2-0-0)**

The objective is to learn material that is normally not part of regularly offered courses. A course outline along with details of the work to be performed are to be submitted by the course instructor to the head of the department for approval based on the recommendation of the department curriculum committee. The course outline to mention the subtitle to appear in the transcripts.