MASTER OF TECHNOLOGY ( M.TECH.) IN COMPUTER SCIENCE
1 SCOPE
The Master of Technology in Computer Science course is offered in Kolkata.
The course is designed to provide a balanced mixture of theoretical and
professional training in Computer Science and Technology so that the students,
on successful completion of the course, may take up
either
(a) a professional career in the technology of software for computer
systems or specialised application areas
or
(b) an academic career for further study and research in the
fundamental and applied aspects of Computer Science and Technology and
related disciplines.
2 DURATION
The duration of the course is two years inclusive of the period of
practical training at the first year of the course and the period of work
on dissertation at the end of the second year.
3 ELIGIBILITY
A candidate seeking admission to this course should
(a) have knowledge of mathematics at the graduate level, and
(b) possess any one of the following minimum academic qualifications:
a Master's degree in Mathematics
/ Statistics / Physics / Electronics / Computer Science / Computer
Applications (MCA)/ Business Administration (MBA)
or
a Bachelor's degree in Engineering/Technology, or any other qualification
considered equivalent (such as AMIE, GRAD-IETE).
4 COURSE STRUCTURE
The Master of Technology in Computer Science course is conducted in
two years which is divided into four semesters. A student is required to
take six courses in each semester, making up a total of twenty four courses
of which two are accounted for by the dissertation work to be done during
the third and fourth semesters. In addition, a student has to undergo a
compulsory practical training of about eight weeks, after successful completion
of course work in the first and second semesters, in research institutes
or in public/private sector organizations under the guidance of an assigned
supervisor in the respective institutes/organizations. Further, a student
may undergo an extra non-credit course, at most one per semester, either
recommended by the faculty or in his/her own interest.
The courses for study in various semesters are as follows :
FIRST YEAR
Semester - I
1.0 Introduction
to Computer Programming (Half-semester non-credit course).
1.1 and 1.2 Two from the following List A of courses as advised
by the faculty depending on the background of the student.
List A
1.3 Programming
Techniques and Data Structures.
1.4 Programming
in an Assembly Language and Systems Programming (Assemblers, Microprocessors
and Loaders).
1.5 Discrete
Mathematics -II : Combinatorics, Graph Theory and Logic.
1.6 Numerical Analysis.
Semester - II
2.1 File Structures
and File Processing.
2.2 Principles of Programming
Languages.
2.3 Design and Analysis of
Algorithms.
2.4 Computer Architecture.
2.5 Operating Systems.
2.6 Theory of Automata,
Languages, Computability and Complexity.
SECOND YEAR
Semester - III
3.1 Compiler Construction.
3.2 Database Management Systems.
3.3 Software Engineering.
3.4 and 3.5 Two from the following List B of courses as advised
by the faculty depending on the background of the student. List
B
Semester - IV
4.1 to 4.5 Five electives to be selected from the
List C of courses given below.
List C
The teachers' committee determines the subjects to be offered in any particular semester and the combination that a particular student may take up.
Dissertation:
A student is required to work for a dissertation on a topic assigned/approved
by the teachers' committee under the supervision of a suitable faculty
member. This work should be started at the beginning of the third semester
and be completed along with the courses of the fourth semester. The dissertation
should be submitted within two weeks of completion of all examinations
for the courses in the fourth semester which may be relaxed on the recommendations
of the teachers' committee. The work for a dissertation should be substantial
and relate to some important problem in an area of Computer Science or
related topics and should have substantial theoretical or practical significance.
A critical review of recent advances in an area of Computer Science or
related topics with some contribution by the student is also acceptable
as a dissertation.
The dissertation may be evaluated by a committee consisting of the
supervisor and an external expert. The student has to defend his/her dissertation
in an open seminar.
The dissertation is considered to be equivalent to two credit courses.
A student is required to submit seven copies of the dissertation.
The Dean's Office will make arrangements for preparing the typescript
and mimeographing seven copies free of costs to the student only if the
length of the dissertation does not exceed 60 pages and the manuscript
is submitted by the prescribed date. If additional copies are requested
by the student, or the length of the dissertation exceeds 60 pages, arrangements
will have to be made by the student at his/her own cost.
5 NON-CREDIT COURSE
A student may also have to undergo an extra non-credit course in some
semesters on the advice of the faculty in a subject in which he/she may
be deficient and/or which may be a pre-requisite (or co-requisite) for
a course to be taken by him/her in subsequent (or the same) semester. For
any such non-credit course recommended by the faculty, the student has
to secure a composite score of at least 35% to be eligible for the award
of the M.Tech. degree in Computer Science and the score obtained will be
recorded in the marks-sheet.
However, a student may also undergo an extra course in his/her own
interest in any semester but he/she must take the tests for the course
and the composite score obtained will be recorded in the marks-sheet though
this will not be taken into account for awarding the degree. A student
will be allowed to undergo at most one extra course per semester whether
or not it is recommended by the faculty.
6 METHOD OF
EXAMINATION AND AWARD OF DEGREE
For each course there are assignments, periodical examinations/class
tests and semestral examination; the scores in these are combined in suitable
ratios as decided by the teachers' committee to obtain a composite score
in the course. A student will be allowed to take a semestral examination
if he/she attends at least 75% of all classes in the semester and his/her
character and conduct are satisfactory. For any semestral examination a
student will be declared to have passed the examination if he/she
i) does not obtain a composite score of less than 25% in any
course;
ii) does not obtain a composite score of less than 45% in more
than one credit course;
iii) does not obtain less than 50% in the programming / software
assignments for each course where there are such
assignments;
iv) does not obtain a composite score of less than 35% in any
non credit course recommended by the teachers' committee; and
v) secures at least 45 in an overall average percentage of composite
scores in the credit courses.
A student admitted to the first year of the course is allowed to attend
the second semester of the course if he/she passes the first semestral
examinations, otherwise he/she has to discontinue the course. A student
who passes the second semestral examination will be allowed to go in for
practical training, otherwise he/she has to discontinue the course. A student
who completes the practical training satisfactorily as certified by the
supervisor is promoted to the second year of the course, otherwise, he/she
has to discontinue the course. A student promoted to the second year of
the course will be allowed to attend the fourth semester of the course
if he/she passes the third semestral examinations and his/her progress
in dissertation work is satisfactory as assessed by an internal committee;
otherwise the teachers' committee, at its discretion, may allow him/her
to take supplementary examinations/additional assignments. A student who
submits his/her dissertation within the prescribed time limit and passes
the fourth semestral examinations and does not obtain less than 45% in
dissertation will be declared to have completed the fourth semester of
the course; otherwise the teachers' committee, at its discretion, may allow
him/her to take supplementary examinations/additional assignments. If a
student fails to meet the attendance requirements or any of the requirements
for passing a semestral examination due to personal illness or extreme
family emergency, which is promptly reported to the Dean of Studies in
writing, the teachers' committee, at its discretion, may waive the attendance
requirements and may allow the student to take supplementary examination
or additional assignments. If even after the supplementary examination
referred to in the preceding paragraph the student fails in the first or
the second semestral examinations, he/she has to discontinue the course;
however, if he/she fails in the third or the fourth semestral examination
even after supplementary examinations, then at the discretion of the teachers'
committee, he/she may be allowed to repeat the second year of the course
without stipend. A student who has successfully completed the fourth semester
of the course is said to have passed the M.Tech. in Computer Science degree
examination and is placed in the
i) first class
with Honours if the student secures an overall average percentage
score of at least 75 in the twenty four courses,
ii) first class
if the student secures an overall average percentage score of at least
60 but less than 75, in the twenty four courses,
iii)second class
if the student fails to secure first class with Honours or first class.
A student passing the M.Tech. (C.S.) degree examination is given a
certificate of M.Tech. (C.S.) degree and a marks-sheet mentioning
i) the twenty four
credit courses taken and the composite percentage score in each course,
ii) the non-credit courses taken
and the composite percentage score in each such course, and
iii)the class in which the student
is placed.
7 ATTENDANCE AND CONDUCT
A student will be allowed to take a semestral examination if he/she
attends at least 75% of all classes in the semester and his/her character
and conduct are satisfactory.
8 DEPOSIT
Each student will have to make a refundable deposit of Rs.1000/- (Rupees
one thousand only) as caution money for use of departmental equipment and
facilities. The deposit is refundable after deduction of cost of damage
or loss, if any, on termination of the course.
9 STIPEND AND CONTINGENCY
GRANT
All students other than those sponsored by the employers are awarded
full stipend at the time of admission initially for the first semester
only. The present rate of stipend is Rs. 1800/- (Rupees one thousand eight
hundred only) per month. The students (other than those sponsored by the
employers) are also eligible to receive a contingency grant of Rs. 3000/-
(Rupees three thousand only) per year as reimbursement of cost of text
books and supplementary text books, photostat copies of required academic
materials, a scientific calculator and other required accessories for the
practical classes. All such expenditure should first be approved by the
respective class teacher. The payment of stipend and the reimbursement
of contingency grant will, however, be governed by the following terms
and conditions:
9.1 The contingency grant sanctioned will be treated as a limit
and the"student"concerned"will be reimbursed the actual expenditure incurred
by him/her on the admissible items within the limit. The grant is not to
be paid as an outright payment.
9.2 The books and non--consumable items purchased or acquired
out of the contingency grant allowed will be the property of the Institute
and the student will have to return them at the end of the course.
9.3 It will be obligatory for every student concerned to undertake
8 to 10 hours (per week) of work related to teaching and research activities
as assigned to him/her by the Institute. This could include tutorials,
laboratory classes, development activities undertaken by faculty members,
maintenance and operation of computers and other facilities, assistance
in Library etc.
9.4 Wherever Government of India/University Grants Commission/
Council of Scientific and Industrial Research/Industry sponsored projects
are undertaken, the services of the students may be used for providing
assistance in projects funded by these agencies. In that event, a portion
of stipend amount i.e., Rs.800/- per month, for the time being may be charged
to the project funds for the duration a student is engaged on such a project.
9.5 The Institute will work out specific programmes of work and
maintain the record of each student.
9.6 If however a student fails to secure a first class or equivalent
in any semester, his/her stipend and contingency grant will be reduced
to Rs.1000/- and Rs. 750/- respectively in the following semester.
9.7 A student shall be required to give an undertaking to the effect
that he/she would not leave the course midway or appear in any competitive
examination, etc., not related to engineering and technology, in order
to be eligible to receive this stipend.
9.8 During the course of studies, the student shall not receive
any emoluments, salary, stipend, etc. from any other source.
9.9 Suitable hostel type accommodation may be provided wherever
available.
9.10 No House Rent Allowance (HRA) is admissible to the M. Tech.
students.
10 CLASS TEACHER
One of the instructors in a class will be designated as the class-teacher
of the class. All students are required to meet their respective class-teachers
periodically to get their academic performances reviewed, and to discuss
any academic problems, if necessary.
11 ISI LIBRARY RULES
Students are allowed to use the reading-room facilities in the library
and are allowed access to the stacks. They have to pay Rs. 250/- as security
deposit in order to avail of the borrowing facility. At most four books
can be borrowed at a time.
Any book from the Text Book Library (TBL) may be issued to a student
only for overnight or week-end provided at least two copies of that book
are left in the TBL; only one book will be issued at a time to a student.
Fine
will be charged if any book is not returned by the due date stamped
on the issue-slip. The library rules and other details are posted in the
library.
12 PRACTICAL TRAINING A
student who passes the second semester examinations will be allowed to
go in for practical training. The practical training may be organized anywhere
in India in research institutes or in public/private sector organizations.
It is generally not possible to arrange training at a computer centre of
the trainee's choice. The duration of the training is about eight weeks.
During the period of training the student is placed under the control of
an assigned supervisor belonging to the organization where training is
arranged. A student who completes the practical training satisfactorily,
as certified by the supervisor, is promoted to the second year of the course.
A student during the training period will receive his/her usual monthly
stipend from the institute. Those placed in Kolkata for practical training
will not receive any other allowance. Others will be paid an additional
monthly allowance at the following rates :
(i) Rs.150/- (Rupees one hundred fifty) for those placed in the
suburbs of Kolkata,
(ii) Rs. 200/- (Rupees two hundred) for those placed outside
of Kolkata and its suburbs, but offered accommodation in the ISI hostel
or the hostel of the organization where they are placed , and
(iii) Rs. 250/- ( Rupees two hundred fifty ) for those placed outside
of Kolkata and its suburbs, but not offered accommodation as above.
(iv) For travel from Kolkata to the city where the students are placed,
and back , the students will be reimbursed second class to and fro train
fare with sleeper charges, an allowance of Rs. 20.00 per head for every
24 hours or part thereof during the train journey, and incidental expenditure
to cover cost of road travel/coolies to the extent of Rs. 15.00 each way
for the whole trip.
13 SYLLABI For each course the following information, when relevant, are given: (a) topics, (b) pre-requisites/co-requisites (PR/CR), if any, (if a compulsory course is PR/CR for another course, then it is not mentioned), (c) the number of lectures and tutorials, if any, per week, (d) the percentage weights for theory and programming/software assignments, if any, relevant to the course, (e) notes giving supplementary information, if any, that may be relevant to the course, and (f) a list of recommended books.
1.0 Introduction
to Computer Programming
(half-semester
non-credit course)
(a) A standard
introductory course in computer programming using a high level programming
language, preferably, FORTRAN 77.
(c) Three lectures
and one two-hour tutorial per week.
(d) 50% for
theory and 50% for programming assignments.
(e) This course
is recommended for all those having no such prior background as may be
established by a test in the beginning of the first semester. For candidates
successful in this test, the score obtained will be considered for passing
the first semestral examination. For others, the score obtained in a test
at the end of this course will be considered for passing the first semestral
examination.
(f) References
:
1.1 and 1.2 Two from the courses A1 -- A4.
A1: Switching Theory
and Logic Design
(a) Fundamentals
of Boolean Algebra, switching algebra and switching functions, applications
to logic design, minimization of Boolean functions, Logic design with TTL,
MOS and CMOS networks, Programmable logic arrays, multi-output circuit
synthesis, decomposition, unateness and symmetry of Boolean functions,
fan out free functions, Reed-Muller-Canonical expressions, Boolean differential
calculus, applications to reliable logic design and fault detection. Finite
state model for sequential machines, state minimization, decomposition,
regular expressions, synchronous, asynchronous and linear sequential machines,
structure of sequential machines. Fault detection experiments and linear
sequential machines. Special features of VLSI logic design.
(c) Three
lectures and one tutorial per week.
(f) References
:
A2: Computer Organization
(a) Introduction:
Evolution of computers. Basic Building Blocks for Design-Logic gates,
Multiplexer, De-multiplexer, Decoders, Encoders, General
purpose logic arrays, Registers, Counters. Processor Design: Information
representation, Number formats, Instruction sets, Fixed-point addition,
Subtraction, Multiplication, Division, Floating-point arithmetic, ALU Design.
Control
Design: Instruction sequencing, Instruction interpretation, Hardware
control, Microprogrammed Control. Memory Organization : Random access
and serial access memories, Virtual memory, Memory hierarchies. Memory-
interleaving, Cache memories, Associative memories. System Organization
: I/O devices, Programmed I/O, DMA and interrupts, I/O processors, CPU-I/O
interaction, Local and long distance communication, Interconnection structure,
Bus control.
(c) Three
lectures and one tutorial per week.
(f) References
:
A3: Discrete Mathematics-I
: Algebraic Structures
(a) Sets, Operations on sets, Cartesian product, relations, equivalence
relations and classes, partitions, functions, natural numbers, inductions
and inductive definitions and proofs, cardinality of set, finite, infinite,
countable and uncountable sets, diagonalisation argument. Binary operation,
groupoid, semi--group and monoids; groups- subgroups, co--sets, Lagrange's
theorem, Cyclic group, order of a group and an element, Generator of a
group, normal subgroup and quotient groups, homomorphism and isomorphism,
permutation group, direct product. Rings, sub--rings, ideals and quotient
rings, homomorphism and isomorphism, integral domains and fields, field
of fractions, Euclidian domain and unique factorization domain, Poly. rings
over UFD. Lattices and Boolean algebras, and applications. Vector spaces
and linear transformation, basis and dimension, matrices and linear transformation,
rank and nullity, determinants and characteristic polynomials, Eigen values,
eigenvector, similarity, Symmetric and unitary matrices. Fixed extensions
- finite dimensional, algebraic and transcendental, Splitting field of
a polynomial, existence and uniqueness of finite fields, Coding theory,
cyclic codes.
(c) Four
lectures and one tutorial per week.
(f) References
:
A4: Probability and Statistics
(a) Introduction to probability, classical and axiomatic definitions of
probability and consequences, discrete probability space, conditional probability
and independence. Random variables and their distributions - Univariate
and bivariate discrete and continuous distributions, multivariate distributions.
Tchebychev's inequality, weak law of large numbers, central limit theorem
(statement). Introduction to statistics - collection and summarization
of data - random sampling - elements of decision theory, estimation and
tests of hypotheses; ANOVA and Regression.
(c) Four lectures and one tutorial per week.
(f) References :
1.3 Programming
Techniques and Data Structures (preferably using PASCAL)
(a) Pascal
language and structural programming. concepts Data structures -
formal definitions, operations, implementations and applications of basic
data structures; array, stack, queue, dequeue, priority queue, doubly linked
list, orthogonal list, binary tree-traversal algorithms, threaded binary
tree, generalized list. Binary search, Fibonacci search, binary search
tree, height balanced tree, heap, B-tree, B*-tree, digital search tree,
tree, hashing techniques.
(c) Three
lectures and one two-hour tutorial per week.
(d) 60%
for theory and 40% for programming assignments.
(f) References
:
1.4 Programming
in Assembly Language and Systems Programming
(Assemblers, Microprocessors and Loaders)
(a) Assembly
Language (for a specific system e.g. VAX-8650): why assembly language,
description of functional characteristics, addressing modes, data types,
instruction structure, registers, indexing, instruction set description,
macros, recursive macros, sub-routines, stacks, procedures, exception handling.
Assemblers - Overview of assembly process, processing of imperative, declarative
and assembler directive statements, relocation, linking and loading concepts;
one and two pass assembler; symbol table organization, program sections,
output forms. Macro-assembler - macro definitions and parameters, macro
call expansion, macro definition within a macro and macro call within a
macro, conditional assembly macro--processor. Loaders - review of loading,
linking and relocation, absolute, dynamic and direct loading schemes, program
linking schemes and resolution of external references, optional features
in loaders and linkage editors, overlay structures and dynamic loading.
(c) Three
lectures and one two-hour tutorial per week.
(d) 60%
for theory and 40% for programming assignments.
(f) References
:
1.5 Discrete
Mathematics-II: Combinatorics, Graph Theory and Logic
(a) Combinatorics
- quick review of permutations, combinations, Binomial theorem, Newton's
form of Binomial theorem, Multinominal theorem, Principle of inclusion
and exclusion. Asymptotic - Big O, Omega and Theta notations, basic facts,
comparison of and operations on asymptotic classes; Recurrence relations
- classification, summation method, recurrence relations arising in analysis
of recursive algorithms - extension to asymptotic solutions from solutions
for subsequences, Linear homogeneous relations - characteristic root method
- general solution for distinct and repeated roots, Non- homogeneous equation
- some important special cases, Generating functions - definition and examples
of ordinary generating functions, application to linear homogeneous recurrence
relations, computation of sums involving binomial coefficients, non-linear
recurrence relations, exponential gfs and probability gfs. Brief introduction
to Polya theory of counting of equivalence classes - statements of Burnside's
Lemma and Polya Theorem - an application.
Graph Theory - Graphs and digraphs, subgraphs, complement, isomorphism,
walks, paths and circuits, distance, connectedness and reachability, adjacency
matrix, Eulerian paths and circuits in graphs and digraphs, Hamiltonian
paths and circuits in graphs and tournaments, Trees, spanning trees, rooted
trees and binary trees, Planar graphs, Euler's formula, statement of Kuratowski's
theorem, dual of a planar graph, Independence number and clique number,
chromatic number, bipartite graphs, statement of 4-colour theorem, Dominating
set and Covering set.
Logic : Propositional Calculus - propositions and connective,
syntax; Semantics - truth assignments and truth tables, validity and satisfiability,
tautology, adequate set of connective; equivalence and normal forms; compactness
and resolution; formal deducibility - natural deduction system and axiom
system; soundness and completeness. Introduction to Predicate Calculus
- Syntax of first order language; semantics - structures and interpretations;
formal deducibility - first order theory - models of a first order theory
(definition only); validity, soundness, completeness, compactness (statement
only); resolution principle (outline).
(c) Four
lectures and one tutorial per week.
(f) References
:
1.6 Numerical Analysis:
(a) Error and
their propagation in numerical computation; concepts of convergence and
stability of an algorithm.
Solution of non-linear equations - iterative methods, acceleration
of convergence, Newton's method of polynomials, quotient difference algorithm.
Interpolation and approximation, interpolating polynomial and its construction.
Using Lagrangian method and methods of differences, iterated interpolation,
method of divided differences, inverse interpolation, Spline functions
and their uses.
Numerical integration - Newtonian and Gaussian quadrature methods,
integration formulae using finite differences, Romberg integration.
Matrix computation - numerical solutions of systems of linear equations,
computation of inverse and eigenvalues of a matrix. Solution of ordinary
differential equations.
(c) Three lectures
and one 2-hour tutorial per week.
(d) 60% for
theory and 40% for programming assignments.
(f) References
:
2.1 File
Structures and File Processing (preferably using COBOL)
(a) COBOL
Language.
Concepts of records and files, pinned/unpinned record etc. Heap file,
hashed file, indexed file, relative file, file with dense index, multi-level
indexed file, multi-key access file, inverted list, multi--list organization,
storage organization under HSAM, HISAM, HIDAM, HDAM (H = hierarchically,
I = indexed, D = direct, AM = access method). Management of files with
variable record length, need for file reorganization. Management of addition/deletion/overflow
under each of the above methods.
Different hashing methods (appropriate for disk files) and management
of collision. External file sorting techniques. Elementary concepts of
data base. Security of files.
(c) Three
lectures and one two-hour tutorial per week.
(d) 60%
for theory and 40% for programming assignment.
(f) References
:
2.2 Principles of
Programming Languages
Motivation for the study of programming languages; factors influencing
the evolution of programming languages - influence of architecture and
operating system, implementation methods, developments in programming methodology
and theoretical studies, desirable features and design issues. Language
processors, classification - imperative vs. applicative, etc.
Major concepts of imperative languages - data types - specification,
implementation and declaration of elementary and structured data types,
type checking and conversion, evolution of the data type concept - data
abstraction, encapsulation and information hiding, sub programmes, type
definitions, abstract data types, sequence - control : - implicit and explicit
sequence control within expressions and between statements, subprograms
sequence control, recursive subprograms, exceptions and exception handling,
co--routines, tasks and concurrent executions, data control - static and
dynamic scooping, local data and local referencing environments, shared
data and block structured languages, parameter transmission, sharing data
in concurrent environments, storage management - stack and heap, garbage
collection, simulation of a concurrent environment.
Formal Syntax and semantics - a brief introduction, Comparative evaluation
of selected high level languages, Functional programming and LISP, Lambda
calculus, Data Flow Languages, Object Oriented Languages.
(c) Three lectures and one two-hour tutorial per week.
(f) References :
2.3 Design and Analysis
of Algorithms
(a) Introduction
and basic concepts - complexity measures, worst and average case complexity
functions, problem complexity. Quick review of basic data structures, algorithm
design principles divide and conquer and recursive algorithms, greedy method,
dynamic programming, examples.
Sorting and selection problems - Finding maximum, and minimum,
Kth largest elements in order and sorting by selection, tournament and
heap sort method, lower bounds. Other sorting algorithms, radix sort, quick
sort, merge sort, selection of Kth largest element.
Searching and Set manipulation : Searching in static table -
binary search, path lengths in binary trees and applications, optimality
of binary search in worst-case and average-case, binary search trees, construction
of optimal weighted binary search tree, Searching in dynamic table - randomly
grown binary search trees, AVL and (a,b) trees.
Hashing - basic ingredients, Analysis of hashing with chaining
and with open addressing.
Union-Find Problem - tree representation of set, weighted union
and path compression - analysis and application.
Graph problems : Graph Searching - breadth first, depth first
and shortest first searches, topological sort, connected and biconnected
components, minimum spanning trees - Kruskal's and Prim's algorithms -
Johnson's implementation of Prim's algorithm using priority queue data
structures.
Algebraic problems : Evaluation of polynomials with or without
preprocessing, lower bound results (without proof). Winograd's and Strassen's
matrix multiplication algorithms and applications to related problems,
lower bound results (without proof).
NP - completeness : Informal concepts of deterministic and non--deterministic
algorithms - P and NP, NP--completeness, statement of Cook's theorem, Some
NP-complete and NP-hard problems, Approximation algorithms.
(c) Four lectures
and one tutorial per week.
(d) 80% for
theory and 20% for programming assignments.
(e) At least
one assignment involving implementation of several algorithms of same asymptotic
complexity for a problem and their empirical comparisons.
(f) References
:
2.4 Computer Architecture
(a) Introduction
: Difference between architecture and organization, General features of
von Neumann architecture. Study of architecture of a typical von Neumann
machine. Criticism of von Neumann architecture and requirements for an
improved architecture. Architecture of a stack machine. Language directed
architecture. Object oriented architecture, Parallel and pipeline computers.
Data Flow architecture.
(c) Three lectures
and one tutorial per week.
(f) References
:
2.5 Operating System
(a) Introduction:
Concepts of batch-processing, multi-programming, time-sharing, real-time
operations, Resource manager view, Process view and Hierarchical view of
an OS.
Memory Management: Partitioning, Paging, Demand-paging, Page
Replacement Algorithms, Segmentation and Demand-paging, Cache or buffered
memory management.
Processor Management: CPU Scheduling - Non-preemptive and Preemptive
scheduling algorithms, Performance analysis of multiprogramming, Multiprocessing
and Interactive systems. Process Synchronization - Concurrent processes,
Precedence graphs, Critical Section Problem - Software and Hardware solutions
for n processes, Semaphores, Classical process coordination problems, inter
process communication, Conditional critical region, Monitor constructs,
Concurrent languages, Deadlock - Characterization, Prevention, Avoidance,
Detection and Recovery.
Device Management: Scheduling algorithms, Spooling.
Protection: Policies and mechanisms, Domain of protection, Access
matrix and its implementation, Dynamic protection, Security. A case study
- Unix.
(c) Three lectures and one tutorial per week.
(f) References :
2.6 Theory
of Automata, Languages, Computability and Complexity
(a) Regular
languages and Finite-state Automata - Recognition of a language by
an automation, regular sets, regular expressions, finite automata, equivalence
of det and nondet finite automata, minimization of finite automata, Algorithm
for equivalence of finite automata, Pumping lemma and its use in proving
non-regularity. Closure properties of regular sets, Algebraic characterization
of regular sets, Myhill-Nerode theorem and its uses.
Context-free languages and the languages recognized by pushdown
automata : CFG and PDA, CFL's which are not regular, closure properties
of CFLs, Properties of grammer, emptiness, ambiguity, LL, LR undecidable
problems (eg. equivalence of ambiguity) about CFL.
Computability : Turing machines (TM) and its variants, other
models of computation, Computable functions, Languages (Sets) - Elementary
properties, Universal TMs, Halting Problem, Recursive functions and sets,
Recursively enumerable sets (Elementary properties); Arithmetization (Goedelization)
of TM's, Kleene's normal form theorem. Equivalence of recursive functions
and computable functions.
Elements of Complexity Theory : Space complexity, Time complexity,
Complexity of RAM program, Simulation of RAM by TM and its complexity,
PTIME, NP, P-space etc., Polynomial Time reducibility etc. NP-completeness
concepts, Coole's Theorem, some standard NP-complete problems.
(c) Four lectures and one tutorial per week.
(f) References :
3.1 Compiler Construction
(a) Introduction
to Compiler, Phases and passes, Bootstrapping, Finite state machines and
regular expressions and their applications to lexical analysis, Implementation
of lexical analyzers, lexical-analyzer generator. LEX-compiler, Formal
grammars and their application to syntax analysis, BNF notation, ambiguity,
LL(k) and LR(k) grammar, bottom-up and top-down parsers, Operator precedence,
Simple precedence, Recursive descent and Predictive parsers, LR(k) parsers,
Parse table generation, YACC.
Syntax directed translation: quadruples, triples, 3 address
code, code generation for standard constructs with top-down and bottom-up
parsers, translation of procedure calls, record structuring. Code optimization:
Loop optimization, DAG analysis, Loop identification by flow dominance,
Depth-first search, Reducible flow graphs, Legal code motion, induction
variables, Data flow analysis, u-d and d-u chains, Copy propagation, Elimination
of global sub--expressions, Constant folding, Code hoisting, forward and
backward data flow equations, Inter procedural data flow analysis. Code
generation: Problems in code generation, Code generator, Register assignment
and allocation problems, Usage count, Code generation from DAG, Peephole
optimization. Symbol table: Data Structure and management, Runtime storage
administration, Error detection and recovery, Lexical, Syntactic and semantic
errors, Case studies with real life compilers.
(c) Three
lectures and one two-hour tutorial per week.
(d) 60%
for theory and 40% for programming assignments.
(f) References
:
3.2 Database Management
Systems
(a) Introduction
: Purpose of Database Systems, Data abstraction and modelling, Instances
and schemes, Database Manager, Database users and their interactions, Data
Definition and manipulation language, Data dictionary, Overall system structure.
Entity-Relationship
Model: Entities and entity sets, Relationships and relationship sets,
Mapping constraints, E-R diagram, Primary keys, Strong and weak entities,
Reducing E-R diagram to tables, trees or graphs, Generalization and Specialization,
Aggregation, E-R language.
Files and Data-structure Revisited: Sequential file organization,
buffer management, mapping tables, trees or graphs to files, ISAM file,
Use of B-tree and B*-tree for indexing, Hashing and Hash functions.
Relational Model}: Structure of a relational database, operations on relations,
Relational Algebra, Tuple and Domain relational calculus, Salient features
of a query language.
Hierarchical Model: Information Management System (IMS), Database
description and tree-structure diagram, DL/1 language, Data retrieval and
update facility, Limitations of hierarchical systems, Virtual records.
Network Model: Database task group (DBTG) model, Data- structure
diagram, Record and Set constructs, Record retrieval and update facility,
Set processing facility, Example of an actual network database implementation
(DMS), Importance of network database
Normalization in Relational System: Pitfalls in RDBMS, Importance
of normalization, Functional, multi valued and join dependencies, 1NF to
5NF, Limitations of RDBMS.
Description of an actual RDBMS and its Query language: Involves
extensive practice in computer centre to get an idea of an actual implementation.
Query Optimization: Importance of query processing, Equivalence
of queries, Cost estimation for processing a query, general strategies,
bi-relational and multi-relational join algorithms, algebraic manipulations.
Failure and Crash Recovery in DBMS: Failure classification,
Transactions, Log maintenance, Check point implementation, Shadow paging,
Example of an actual implementation.
Security and Integrity: Security and Integrity violations and
constraints, Authorization and views, Encryption, Example of an actual
implementation.
Special Topics (subject to the availability of time): Structure
of a Database machine, Distributed Database, Present trends in Database
technology.
(c) Three lectures and one two-hour tutorial per week.
(d) 60% for theory and 40% for programming assignments.
(e) Two to three assignments are to be given.
(f) References :
3.3 Software Engineering
(a) Part
1 - Software Engineering Concepts: Introduction: Software project
planning (basic concepts of life cycle model, milestone, cost models, successive
versions model, project structure, team structures), Requirements Analysis
(Specifications, Algebraic axioms, Regular expressions, Decision tables,
Event tables, Transition tables, FS mechanism, Petri Nets), Software Design
- Architectural and detailed design (Abstraction, Information hiding, Modularity,
Concurrency etc., coupling and cohesion, data flow diagrams, structure
charts, Pseudo code, stepwise refinement, top-down and bottom-up programming
etc.); Test plan, Implementation issues (structured coding, recursion,
documentation guidelines), modern programming language features (type less,
strong type and pseudo strong type checking, user-defined data types, data
encapsulation, generic facilities, concurrency mechanism), program verification
and validation (unit testing, integration testing, acceptance testing,
formal verification), Software maintenance - (Source code metrics -Halstead's
effort equation, cyclomatic metric), Reliability and software quality assurance,
Software cost estimation ( Delphi, COCOMO etc.).
Part 2: Team-based term project.
(c) Three lectures and one two-hour tutorial per week.
(d) 50% for theory and 50% for project.
(e) The project will be done in a group of 4 to 5.
(f) References :
3.4 -- 3.5 :Two courses from B1--B6.
B.1 Computer
Network and Distributed Computing
(a) Introduction:
User subnet and communication subnet, circuit switched and packet-switched
networks, Layered network architecture. Transmission Links and Procedures}:
Terrestrial, Radio, Satellite and Optical fiber links, Multiaccess communication
- FDM, TDM, CSMA, Multipoint link control - serial polling and hub polling,
Poll time analysis. Design and Analysis of Network Nodes: Node design
- different types of functions, Software and hardware interface, Processing
capacity estimation, Memory size estimation.
Topological Design: Multipoint connections among terminals and
concentrator, Minimum spanning tree - Chandy-Russell algorithm, Essau-William's
algorithm, Kruskal algorithm, Unified heuristic algorithm, Link and link
capacity assignment, network design algorithms - Add algorithm, Drop algorithm,
Distributed network design, Cut saturation algorithm.
Flow Control: Network congestion, Different techniques of flow
control, Flow deviation method, Distributed flow control, Isarithmic flow
control, Deadlocks.
Routing: Deterministic routing, Adaptive routing strategies
-centralized, distribute and hierarchical, Random routing.
Network Protocols: Concepts in Protocol Design, Network architectures
and protocols, CCITT recommendation X.25, Protocols in some existing networks.
(e) Three
lectures and one tutorial per week.
(f) References
:
B.2 Artificial
Intelligence and Expert Systems
(a) Introduction:
Cognitive Science and Perception Problems, AI and Production systems, Problem
solving Paradigm, Introduction to search techniques, Problem representations
through heuristics, Search spaces and problem representations, Problem-reduction
representations and AND/OR graphs.
Basic heuristic search procedures, Specialized search techniques,
Decomposable search strategies, Heuristics viewed as information provided
by simplified models.
Knowledge representation through propositional and predicate
logic, Rule-based deduction and Expert Systems, knowledge representation
through fuzzy logic, Knowledge representation through other types of logic
and some applications, MYCIN-A rule based system for infectious diseases
Search strategies in abduction, Knowledge Engineering, Inference Engines
and Expert System Shells, Logic Programming and Functional Programming
Languages for AI, Parallel architectures, artificial neutral network and
optical processing, Problem solving and plan generating system, Hierarchical
planning, STRIPS, Control strategies for STRIPS, Means-ends analysis and
GPS, Use of deduction systems to generate robot plans. The black board
approach. Structures representation of knowledge, Semantic nets,
Frames, Scripts, Matching, Natural Language Understanding, Image understanding
and computer vision, Speech understanding system, Industrial Applications
of AI and ES Learning.
(e) Four lectures
per week.
(f) References :
B.3 Computer Graphics
(a) Introduction to Computer Graphics: Various graphics display
devices, Graphics interactive devices.
Raster Scan Graphics: Line drawing algorithms, circle drawing
algorithms, Scan conversion, polygon filling, edge list algorithms, edge
fill algorithms, seed fill algorithms, halftoning.
Clipping: Two dimensional clipping, subdivision line-clipping
algorithms, line clipping for convex boundaries. Cyrus-Beck algorithm,
interior and exterior clipping, 3D graphics introduction, 3D clipping,
3D Cyrus-Beck algorithm, Sutherland- Hodgman algorithm, Weiler-Athertou
algorithm.
Hidden line and hidden surfaces: Floating horizon algorithm,
Roberts algorithm, Warnock algorithm, list priority algorithms, scan line
algorithms.
Curves and Surfaces: Bezier and B-Spline curves, surfaces, their
properties, curves and surface drawing algorithms.
Rendering: Illumination models, Gouraud shading, Phong shading,
transparency, shadows, texture.
(c) Three lectures and one two-hour tutorial per week.
(d) 50% for theory and 50% for projects.
(e) Additional facilities - (i) 4 graphics terminals (high quality), (ii)
2 Laser printers.
(f) References :
B.4 Cryptology and Data
Security
(a) Introduction
- basic concepts of Cryptology and data security, cryptographic systems,
private-key and public-key cryptosystems, digital signature.
Mathematical foundations - Information theoretic ideas, entropy
and equivocation, perfect secrecy and unicity distances, complexity theoretic
ideas - algorithm and problem complexities, NP - completeness, ciphers
based on computationally hard problems, Number theory - congruences residues,
complete set of residues, principle of modular arithmetic, fast exponentiation,
reduced set of residues, Euler's totient function, Fermat's theorem and
Euler's generalization, Euclid's algorithm extended to compute inverses
Chinese remainder theorem and applications, computing in Galois fields
discrete logarithm, quadratic residues, Legendre symbols, survey of factorization
and primality tests.
Encryption Algorithms - Transposition and substitution ciphers,
product ciphers DES and its analysis, exponentiation ciphers - Pohlig -
Hellman and RSA - schemes and their evaluation, Knapsack ciphers - Markle
- Hellman, Graham - Shamir and Shamir - Signature only Knapsack, a breakable
NP - complete Knapsack, evaluation of these systems, Fast algorithms for
discrete logarithm in GF(p), security of cryptosystems and problems of
factorization and primality, Crypt analysis, breaking Knapsacks, Shamir
attack and Lenstra -- Lenstra - Lovarz algorithm. Cryptographic techniques
- block and stream ciphers, one-way ciphers, Key management and threshold
schemes, Access control - matrix model and control mechanisms, hierarchies,
authorization lists, capabilities, verifiably secure systems, Information
flow control - lattice model, flow-control mechanism, Inference control
in statistical database, Question of existence of computationally secure
cryptosystem and complexity theory.
(c) Three
lectures and one tutorial per week.
(d) 80%
for theory and 20% for assignments.
(f) References
:
B.5 Topics
in Algorithmic Graph Theory and Discrete Optimization
(a) Shortest path problems (SP) : Various versions of the SP problem.
Algorithms for single source SP problem characterization and presence of
SP, SP tree and its characterization, Ford's labeling method and its correctness
Labeling and Scanning method - efficient scanning orders topological order
for a cyclic networks, shortest-first search for non-negative network (Dijkstra),
BFS search for several networks and its analysis, All-pair shortest path
problem - Floyd's algorithm and its analysis.
Flows in Networks : Basic concepts, Maxflow-mincut Theorem,
Ford and Fulkerson's augmenting path method, Integrality theorem - Maximum
capacity augmentation and its analysis - Augmentation by blocking flows-Dinic's
algorithm-analysis of number of blocking steps for general and unit networks.
Finding blocking flows-Dinic's algorithm wave method, Malhotra - Kumar
- Maheshwari method, Sleator-Tarjan algorithms and their analyses.
Minimum cost-flow : Minimum cost-augmentation and its analysis.
Matching Problems: Basic concepts. Bipartite matchings and network
flows. Non-bipartite matching-basic concepts, Edmonds- Blossom shrinking
algorithm and its analysis.
Planarity and Graph Isomorphism: Review of basic results about
planarity. Polynomial algorithm for testing of planarity and applications.
Graph Isomorphism, Importance of the problem, Backtrack algorithm for general
graph Isomorphism problem and its complexity. Isomorphism complete problems,
polynomial time algorithm for planar graph isomorphism problem, Group theoretic
methods and graph isomorphism problem.
Selected hard discrete optimization problems : Review of NP
hardness for Traveling Salesman problem (TSP), Bin-packing
problem (BPP) Knapsack problem, Max clique (MC), Max independent set (MIS),
Chromatic number problems, Multiprocessor Scheduling problem, Exact algorithm
based on Dynamic programming, Branch and Bound, Back-tracking methods,
Polynomial time algorithm for MC, MIS, chromatic number problems for perfect
graphs. Approximation algorithms and their performance analysis,
Classification of NP--hard optimization problems with respect to
approximiability.
(c) Four lectures and one tutorial per week.
(d) 80% for theory and 20% for programming assignments.
(f) References :
B.6 Statistical
Computing, Simulation and Modelling
(a) Representation
of numbers, fixed-point and floating-point numbers, floating-point arithmetic,
computations of functions, polynomials, power series and continued fractions,
Forward and backward algorithms for computation of a continued fraction,
representation of a ratio of two power series by a continued fraction.
Interpolation - piece-wise interpolation, cubic spline interpolation.
Quadrature-Newton-Cote's and Gaussian quadrature formulae. Orthogonal polynomials-properties
of orthogonal polynomials.
Calculation of probabilities-normal, gamma and beta probabilities,
inverse probabilities.
Simulation-use of Monto-Carlo techniques for computation of integrals.
Generation of random numbers in the computer, its properties. Generation
of normal, exponential and other deviates. Application of simulation, techniques
for solving queuing problems. Clustering methods, agglomerative and divisive
clustering techniques, tree, partition, and overlapping clustering methods-dendrograms,
single, complete and average linkage methods, K-means algorithm, Rao's
method of clustering of type 1 and 2, block clustering D-perfect clustering
methods for forming overlapping clusters - an application of this method
for forming examination schedule.
Stepwise regression methods - forward and inverse sweep operation,
F-to-enter and F-to-remove statistics. Principle component analysis.
(c) Three lectures
and one two-hour tutorial per week.
(d) 60% for
theory and 40% for programming assignments.
(f) References
:
4.1 to 4.5 :Five courses from C1--C26 .
C1. Topics
in Theory of Programming Languages and Methodology
(a) Introduction
to Semantics of Programming Languages: Syntax, semantics, and pragmatics:
the distinction, Abstract syntax and formal semantics, Assigning meanings
to programmes, Operational Semantics: compilers and interpreters, labelled
transition systems, Operational semantics for simple sequential language
with loop.
Denotational Semantics - basic idea - semantics given by structural
induction.
Foundations: domains continuous functions and fixed points,
semantics of a simple language, congruence between operational and denotational
semantics.
Axiomatic Semantics - Hoare-style axioms, weakest preconditions
and predicate transformers, Axiomatic semantics for simple language. Consistency
with respect to denotational or operational semantics. Elementary ideas
of soundness and relative completeness.
Semantic treatment of more complicated programming constructs
: Procedures - parameterless, recursion, methods of parameter passing,
Jumps (go to statement, breaks, etc.), Nondeterminism (e.g. Dijkstra's
guarded commands), Parallelism- treatment as nondeterministic interleaving
of actions, concurrent processes (e.g. CSP, CCS), coroutines, continuous
semantics, Relational semantics, elementary ideas of power domain semantics.
Reasoning about programs: Inductive proof techniques: structural
induction, well-founded induction, computational induction - Partial correctness
- Flow charts and inductive assertions, Hoare-style assertions, Weakest
preconditions. Total correctness of sequential programs - Proving
termination - examples of well-founded sets, weakest liberal preconditions,
- Fixed point properties of recursive programs, - Temporal Logic - continuously
operating programs - Dynamic Logic. The Development of correct programs,
Manipulating programs}: Equivalence of programs, Program transformations
and their correctness.
Other topics Program syntheses, Abstract data types, Algebraic
semantics, Viena Definition Methods for semantics, Mechanical verification
system (e.g. Boyer-Moore system, Standard verification system, etc.).
(b) CR: Course C4.
(c) Four lectures and one tutorial per week.
(f) References :
C2. Advanced
Topics in Design and Analysis of Algorithms
(a) String
Processing - string searching and pattern matching - Knuth - Morris - Pratt
algorithm and its analysis. Algebraic problems - Review of matrix multiplication
and recent results about asymptotically fast matrix multiplications related
problems - Boolean matrix multiplication - Transitive closure and Path
problems, FFT, Power series multiplication and division, Polynomial and
integer arithmetic, Lower bound theory - complexity of bilinear problems.
Parallel algorithms for selected algebraic, numeric and graph problems.
Probabilistic analysis of algorithms - review of mathematical methods -
generating function and combinatorial enumeration, asymptotic methods,
Trees and tree manipulation algorithms, Digital searching and sorting algorithms,
comparison based searching and sorting, dynamic hashing techniques, bucket
algorithms, heuristics for bin packing, network switching, geometric algorithms,
Knapsack, Travelling salesman problem etc.
(c) Four
lectures and one tutorial per week.
(f) References
:
C3: Advanced Topics
in Theory of Computation
(a) Context
sensitive Languages and Linear bounded automata. Recent developments in
Formal Language theory - a survey. Quick review of some basic results in
recursive function theory - (Rice's theorem, S-m-n theorem, Recursion theorem
etc.), Oracles and relativisation - basic facts, Reducibilities and Arithmetic
Hierarchy.
Structural Complexity Theory - review of basic concepts and results
about TM-based complexity theory - time and space bounded computations,
various resource bounded reducibilities, completeness, time and space hierarchies,
Non-uniform and probabilistic models, Polynomial time-hierarchy, Relativisation
results, One-way functions and complexity of cryptosystems, complexity
of Boolean functions, theory of parallel complexity of computation.
(c) Four
lectures and one tutorial per week.
(f) References
:
C4: Formal
Logic with Applications to Computer Science
(a) Review of basic concepts about syntax and semantics of predicate calculus,
Natural deduction and axiom system, Soundness and completeness, Compactness,
Lowenheim and Skolem theorem, Herbrand's theorem and resolution principles
with applications to mechanical theorem proving. Undecidability and Incompleteness
- Peano and Presburger arithmetics, incompleteness of first order number
theory, Model theoretic aspects of complexity theory.
Modal Logic - modal propositional and predicate calculi, Temporal and
Dynamic Logic - Applications to program correctness.
(c) Four
lectures and one tutorial per week.
(f) References
:
C5: Multidimensional
Searching and Computational Geometry
(a) Review of some advanced topics on dynamic unweighted and weighted trees:
Mergebable priority queue, amortized rebalancing cost and sorting presorted
files, Finger trees, Random (a,b) trees and fringe analysis, Dynamic weighted
trees. Self-organizing data structures and the amortized and average -
case analysis, D-trees. An application to multidimensional searching.
Multidimensional Searching: Dynamization - weighting and weighted dynamization,
Order decomposable problems, D-dimensional trees and Polygon trees, Range
trees and Multidimensional divide and conquer, Lower bounds, Partial Match
Retrieval in Minimum Space. The Spanning Bound. Computational Geometry:
Convex polygon - Convex hulls - Voronoi Diagrams and searching planar subdivisions.
Applications.The sweep paradigm - Intersection problems in the plane, Triangulation
- Application, Space Sweep Orthogonal object - plane sweep for Iso-oriented
objects - Divide and Conquer on Iso-oriented objects, Intersection problem
in higher-dimensional space - Geometric Transforms - Duality and Inversion.
(c) Three
lectures and one tutorial per week.
(f) References
:
C6: Advanced topics in Compiling
(a) Detailed theory of parsing, compiling and translating, Lex compiler,
compiler-compilers, Canonical and LALR parsers', General theory and applications
of LL(k) and LR(k) grammars. Syntax directed translation of array references,
procedure calls, declarations, record structures. Error detection and Recovery
Mechanisms.
More about data-flow analysis and code optimization. Applications of
interval orders, analysis of reducible flow graphs, Detection of global
common sub expressions, copy propagation, code-hoisting and very busy expressions,
Compilers for concurrent languages, Case studies.
(c) Three lectures and one tutorial per week.
(f) References :
C7: Advanced Topics
in Operating Systems
(a) Distributed
operating systems File systems - Arpanet FTP, Centralised approach,
Distributed approach - Event ordering and Synchronization - Distributed
mutual exclusion algorithms - Deadlock handling - Time stamp ordering -
Deadlock Detection - centralised, hierarchical and distributed approach
- Robustness - failure detection, General Byzantine problem, Election algorithms.
Deterministic models of processor scheduling : Task scheduling
- optimal scheduling for 2-processor system, optimal scheduling for tree-structured
precedence graph, scheduling of independent tasks. List scheduling, scheduling
to minimize flow time. Probabilistic models of sequencing : different
queuing models, performance evaluations of different servicing disciplines
and different storage models. Other current theoretical topics to be decided
by the faculty member. Design of a small prototype operating system (as
team assignment).
(c) Three lectures
and one tutorial per week.
(f) References :
C8: Advanced Database
Theory and Applications
(a) Schema
design - Data definition language and data dictionary, Schema and schema
language, Manipulation of schemas, Subschemas. Query optimization: Query
optimization revisited (as covered in paper 3.2), Composite indexing, Parallel
join algorithms, Nested query processing.
Distributed Database : Structure of Distributed Database System,
Tradeoffs in distribution, Design considerations, Distributed query processing,
Concurrency control, Deadlock handling, Security in Distributed Systems,
Recovery in Distributed Database. Semantic Data Model : E-R model
revisited, E-R language, semantic data model, implementation of a semantic
model on a relational database, example of an actual semantic model.
Statistical Data Model : Limitations of RDBMS in statistical
and numerical operations, basic concepts of statistical data model, use
of category numeric algebra, domain selection and domain specific operations,
row and column based operations, implementation of a statistical relational
model.
Object-oriented Database : Comparison of relational and network
models, a unified system, importance of non-atomic attributed and abstract
data types, objects, messages and encapsulation, classes and inheritance,
design of object- oriented database, object-oriented database in distributed
environment.
Image Database Systems : Needs for image information systems,
design considerations, image algebra, spatial data structures. compaction
and encoding of image data, image processing language, generalized icons,
image database design using icons. Database Machines : Architecture
and design requirements for a database machine, database on a data flow
system. A small project using one of the various database systems covered.
(c) Three lectures and one two-hour tutorial per week.
(f) References :
C9: Parallel
Processing: Architectures and Algorithms
(a) Introduction : Architectural classification, various terminologies,
parallelism in uniprocessor system, memory-interleaving. Pipelining and
vector processing - instruction and arithmetic pipelines, array processor,
examples. Multistage interconnection networks : permutation
capabilities, routing algorithm, equivalence, fault-tolerance.
Multiprocessor architectures : different aspects, case studies,
parallel algorithms - studies of different numeric, non--numeric and graph
algorithms along with their mappings on suitable architectures. Data flow
architecture
(c) Three lectures and one tutorial per week.
(f) References :
C10: Fault-Tolerant Computing
(a) Origin of fault-tolerant computing, reliability, maintainability, testability,
dependability. Faults, errors and fault - model (Stuck-at, bridging, physical,
component level). Design techniques for fault tolerance, triple-modular
redundancies, m-out-of-n codes, check sums, cyclic codes, Berger codes
etc. Fault-tolerant design of VLSI circuits and systems. Concepts of t-diagnosable
systems, self-checking, BIST, LSSD, etc. Testing and design for testability
- fault equivalence, dominance, checkpoints, test generation, D-Algorithm,
PODEM, FAN, Boolean difference, testability-analysis, fault-sampling, random
pattern testability, testability-directed test generation, Scan path, Syndrome
and Parity testing, Signature analysis, CMOS and PLA testing.
(c) Three lectures and one tutorial per week.
(f) References :
C11: VLSI Design and Algorithms
(a) Introduction to VLSI design, design styles and parameters, popular
technologies. Logic implementation with nMOS, CMOS, DCVS and PLA's Pass
transistor vs. ratio logic, transit time, clocking, scaling, PLA minimization,
folding, SIMPLIFY, ESPRESSO etc. Placement, layout, floor planning and
routing, gate array, standard cell, Language to describe function, structure
and geometry of VLSI design (like MAGIC).
Silicon compilation, design rule checking, expert systems for VLSI,
Symbolic layout and compaction, complexity of layout problems.
(c) Three lectures and one tutorial per week.
(f) References :
C12: Pattern
Recognition and Machine Learning
(a) What is Pattern Recognition and Machine Learning and overview of
different approaches. Statistical Pattern Recognition:
Bayesian classification, Sequential Methods including Wald's SPRT,
GSPRT, modified SPRT, compound SPRT, nearest neighbour classification,
linear classifications, linear and quadratic discriminant functions, parametric
and non-parametric estimation and supervised learning, non-supervised learning
and clustering techniques, feature selection and extraction, related algorithms,
applications.
Selected Topics from the following
1. Syntactic Pattern Recognition: Introduction to grammars and formal languages,
languages for pattern description and selection of pattern primitives,
syntax directed pattern analysis and recognition procedure.
Introductory remarks on stochastic languages for syntactic pattern
recognition, applications.
2. Fuzzy Set Theoretic Approaches in Pattern Recognition: Fuzzy sets and
operators, classification and clustering using Fuzzy sets, fuzzy distance
functions and fuzzy decisional algorithms.
3. Introduction to computational geometry and shape recognition.
4. Applications to speech recognition, image analysis, bio- medical and
other applications
(c) Three lectures and one tutorial per week.
(f) References :
C13: Image Processing
(a) Image: Image formation, imaging geometry, perspective and other
transformation, stereo imaging, elements of visual perception.
Digital Image: Sampling and quantization, serial and parallel
image processing systems.
Signal Processing: Fourier, Walsh-Hadamard, discrete cosine
and Hotelling transforms and their properties, Fileters, Correlators and
Convolvers.
Image enhancement: Contrast modification, Histogram specification,
smoothing, sharpening, frequency domain enhancement, pseudo-color image
enhancement.
Image Restoration: Unconstrained and constrained restoration,
Wiener filter, motion blur removal, geometric and radiometric correction.
Image data compression: Huffman and other codes transform compression,
predictive compression, two-tone image compression, block coding, run-length
coding, contour coding.
Segmentation techniques: Thresholding approaches. region growing,
relaxation, lines and edge detection approaches, edge linking, supervised
and unsupervised classification techniques, remotely sensed image analysis
and applications. Shape analysis: Gestalt principles, shape number,
moment Fourier and other shape descriptors, skeleton detection, Hough transforms,
topological and textural analysis, shape matching.
Practical applications: Fingerprint classification, signature
verification, text recognition, map understanding, biological cell classification.
(c) Three lectures and one tutorial per week.
(f) References :
C14: Computer Vision
(a) Introduction : Machine vision system and its task, image brightness
optics and lenses, sensing of monochrome and colour images, Binary and
gray level image, Human vision structure and neurovisual model.
Imaging geometry: Projections - perspective and orthographic,
co-ordinate transformations.
Early processing: Concept of primal sketch, Edge detection and
finding - differential operators and their discrete approximation. Properties
of different types of edge operators, effect of noise on local edge operators,
detection and localisation of edges, scale space.
Reflectance map and photometric stereo: Image brightness and
radiometry, image formation and surface reflectance under different source
conditions. Reflectance map and bidirectional reflectance distribution
function (B.R.D.F.), photometric stereo - recovering albedo and surface
orientation.
Range measurement and recovering scene geometry: Stereo (binocular)
technique - Epipolar line and plane, matching based on edge and feature,
introduction to photogrammatory, depth from texture gradient, focussing
etc. (monocular technique). Recovering surface from interpolation, different
range, finder (active) - laser range finder, strip lighting, etc.
Shape from Shading: Recovering shape from shading with linear
and rotationally symmetric reflectance map, reflectance map in general
case, singular point, characteristics curve, power series expansion of
reflectance map, relaxation and minimisation technique for solving reflectance
equation, occluding boundaries and stereographic projections, extended
Gaussian surface. Representation and analysis of polyhydral scene:
Understanding of line drawings, Gradient and dual space, generalised cylinder,
volumetric representation, edge and junction labelling - Waltz, Hoffman
- class and other techniques.
Motion field and optical flow: Motion field, optical flow -
smoothness, boundary conditions, solution of optical flow under constraint
conditions, discontinuities of optical flow.
Passive Navigation and structure from motions: Recovering motion
of the observer under different constraint conditions. Recovering of pure
translational motion and rotational motion, general motion and possible
recovering techniques. Understanding of motion from image sequence.
Labelling and recognition of scene objects: Model based recognition
system - Acronym, Model based recognition from sparse range data, 3 --
D model based vision system - special purpose automatic programming, architecture
for computer vision.
(b) PR : Image processing
(c) Three lectures and one two-hour tutorial per week.
(e) Facilities desirable
1. Display of gray level image
on Vax-8650
2. Laser printer with parallel
interface for Hard copy on Vax-8650
(f) References :
C15: Digital Signal Processing
(a) Introduction : Discrete-time signal and systems, various digital
filtering applications, background concepts of analog signal processing.
Difference Equations: Input-output n th order difference
equations, Unit - sample response, convolution sum, input-output stability,
block diagrams.
The Z-transform: Definition, properties - relationship - transform,
inverse transforms.
Transfer Functions: Poles and Zeros in Z-plane, sinusoidal response
(periodicity, bandwidth).
Continuous time signal analysis: Review of Fourier series and
Fourier transform for continuous time signals, signal sampling and data
conversion, interrelationships between Fourier, Laplace and Z-transforms.
Discrete signal analysis: Discrete Fourier Series (DFS) and
Transform (DFT) and properties, convolution of sequence, Fast Fourier Transform
(FFT) and its application in signal processing.
Digital Filter Design Technique : Filter specifications, design
of non-recursive and recursive filters, two-dimensional filters, space
and frequency domain design of FIR filters.
Filter Implementation Considerations : Quantization effects,
sensitivity analysis, hardware considerations.
Architectural support for signal-processing : VLSI Hardware,
Algorithms for signal processing functions, vector/array/systolic and neighbourhood
/ hypercube architectures for special purpose digital signal processing.
Application of concepts in signal processing to speech and image processing.
(c) Three lectures and one tutorial per week.
(f) References :
C16: Robotics
(a) Robot Anatomy, Arm Geometry, Direct and Inverse Kinematics Problem,
Arm Dynamics, D' Alembert Equations of Motion, Synthesis of elements
with movability constraints, manipulations - trajectory planning, joint-interpolated
trajectories. Feedback control - theory and analysis. Control of Robot
Manipulations - computed torque technique, sequence and adaptive control,
resolved motion control, Moluie Robots. Robot Sensing - Range and Proximity
and Higher-Level vision, Illumination techniques, Imaging Geometry, Segmentation
Recognition and Interpretation. Robot programming languages - characteristics
of Robot Level and Task level languages. Robot intelligence - state space
search, Robot learning, Robot Task planning, Knowledge Engineering.
(c) Three lectures and one tutorial per week.
(f) References :
C17: Data Analysis for
Remote Sensing
(a) Sources and characteristics of Remote Sensing data: Introduction to
Data sources, Earth resource satellite centres in the visible and infrared
regions, Characteristics of Landsat, APOT, TM, IRS, etc. Error correction
and registration: Generatic correction, radiometric correction, processing
of remotely sensed images: enhancement, edge detection, filtering etc.
Supervised classification techniques: Maximum likelihood classification,
Bayes' classification, minimum distance classifier, unsupervised classification
and cluster analysis: KMEANS, ISODATA etc. Feature reduction: Separability
measures for multivariate normal classes, separability measures for minimum
distance classification, feature reduction by data transformation, canonical
analysis, principal component analysis applications.
(c) Three lectures and one two-hour tutorial per week.
(f) References :
C18: Logic Programming
(a) Four styles of programming: procedural, functional, logic-oriented
and object-oriented; fundamentals of logic programming - a refresher on
mathematical logic, propositional calculus, predicate calculus, Horn Clauses
and basic inferencing with them, top-down and bottom-up Horn Clause proof
procedures. Resolution and unification, working principles of PROLOG. Non-
determinism in logic programming, structuring control flow in logic programs,
meta-level programming with PROLOG. Parallelization of logic program -
forms of parallelism in logic programs, parallel unification - some methods,
non-determinism and time-dependent execution, meta-level programming and
control flow in PROLOG. Implementation of PROLOG, concurrent PROLOG and
PARLOG, a case study approach, recent trends in logoc programming.
(c) Three lectures and one two-hour tutorial per week.
(f) References :
C19: Advanced
topics in Numerical Analysis
(a) Selected advanced topics in analysis of numerical methods for serial
and parallel computers from the following areas: Matrix computation and
eigenvalue problems, System of non-linear equations, Ordinary and partial
differential equations.
(c) Three lectures and one tutorial per week.
(f) References :
C20: Statistical Methods
(a) Review of mathematical and statistical preliminaries: algebra of vectors
and matrices (including eigenvalues and eigenvectors), theory of distributions
(including normal distribution theory). Estimation: Likelihood and sufficiency,
maximum likelihood estimation, other techniques and concepts, testing of
hypothesis, multiple regression and correlations, principal component analysis,
factor analysis, discriminant analysis (including classification and variable
selection). Cluster analysis, analysis of directional data, elements of
time series analysis.
(c) Three lectures and one two-hour tutorial per week.
(f) References :
C21: Topics in
Operation Research Methods
(a) Introduction to OR: Origin of OR and its definitions, stages
of an OR project: (i) formulation of the problem, (ii) developing a model,
(iii) testing the adequacy of the model, (iv) deriving a solution and (v)
evaluation of the solution and implementation.
Simplex methods for linear programming - convex sets, extreme points
and convex polyhedral sets, simplex algorithm - its theory and computational
details , resolution of degeneracy. Duality theory, dual-simplex and primal-dual
algorithms. Transportation, assignment problems, sensitivity analysis,
replacement and maintenance models - replacement of items that deteriorate,
equipment that suddenly fail, chain of improving equipment, assuming (i)
same life for each member in the chain and (ii) increasing life equal to
that of deterioration only at infinity.
Replacement of items that fail stochastically - individual and common
preventive replacement policies, fault frequency analysis, repair time
and repair cost analysis, investment decision models.
Inventory control - demand forecasting: Moving average, single exponential
smoothing techniques, correction for trend, Brown double exponential smoothing,
Halt's method, Box-Jenkin's method taking into account seasonal variation
- control of forecasting errors. Inventory control problem: Concept of
inventory and various costs, EOQ formula.
Single period models: Single period models, Christmas tree and newspaper
boy problems - provisioning of spares with or without salvage.
Multiperiod models: (Q,r), (R,T), (nQ,r,T) models, comparison of different
models - evaluation of system consequences, construction of tables for
various measures of shortages either administratively set or to a minimize
total cost.
Inventory control project - carrying out an inventory control studies,
relevant cost to be considered, estimation of costs by imputation or otherwise,
coverage analysis, specifying measures of shortage - ABC analysis and selective
inventory management.
Queueing theory - introduction to waiting line model-steady state behaviour
of M/M/1 and M/M/R queues-problem of machine interference and use of finite
queueing tables-introduction to M/G/1, D/M/1, D/Fn/1 and G/M/1.
Sequencing models - two machines and n jobs (no passing) problems and
three machines and n job (no passing) problem, different routing, two-jobs
and n machines, n jobs and m machines, branch and bound algorithm - inadequacy
of existing models for real life problems, line balancing models. PERT/CPM:
Introduction to network analysis, definition of a project, job and events,
drawing of an arrow diagram, determination of critical path and calculation
of floats, Resource allocation and least cost planning, use of network
flow for least cost planning. Uncertain durations and PERT, PERT cost system
and installation of a network system.
(c) Three lectures and one tutorial per week.
(f) References :
C22: Optimisation Techniques
(a) Linear programming - a brief review of simplex method, duality theory,
revised simplex, dual-simplex and primal dual algorithms, bounded variable
algorithm and decomposition principle, on the complexity of simplex method,
polynomial time algorithms: Ellipsoidal and Karmakar's methods. Integer
programming - formulation of various industrial and business problems as
integer and mixed integer programming problems, unimodular matrices and
their applications to integer programming, cutting plane methods for pure
and mixed integer programming problems, Knap-sack, travelling salesman
and shortest route problems.
Non-linear programming - Fritz-John necessary conditions, constraint
qualification and Kuhn - Tucker necessary conditions, sufficiency of Kuhn-Tucker
necessary conditions and convex programming, linear complementary problem
(LCP) and Lemke's complementary private algorithm, compositive plus matrices
and Lenke's algorithm, quadratic programming problems, separable programming.
Dynamic Programming: Bellman's principle of optimality and recursive relationship
of dynamic programming for various optimisation problems.
(c) Three lectures and one tutorial per week.
(f) References :
C23: Management
Information Systems and Decision Support Systems
(a) Measures of information, properties of entropy, uniqueness theorem
for entropy, entropy of a compound probabilistic experiment and its properties,
need for weighted entropy, its properties, entropy based decision making
(in strategy selection), a communication model, need for controlled redundancy
in message communication.
Meaning of data and information, data life cycle, concepts of systems,
classification of systems, cybernetic system need for a general system
theory, organization as a system, rationale for system approach, subsystem
for MIS, steps in system development cycle, role of models in the design
of MIS, different classes of models and their attributes.
Tools for systems analysis and design - flow chart, gantt chart, decision
table etc. Exception principle, internal decision plan, variable processing
plan, mutual intervention plan, measurement of cost of data, cost and value
of information, formulation of value and cost models.
MIS design and implementation issues, identification of dominant and
principal trade-off performance criterion for the system, quantitative
modelling of systems. Definition and characteristics of DSS, MIS vs DSS,
planning and organizing for DSS, iterative design for DSS,
DSS architectures, state-space approach to DSS, problem reduction approach
to DSS, production system approach to DSS, case studies.
(c) Three lectures and one tutorial per week.
(f) References :
C24: Stochastic
Processes with Applications to Computer Science
(a) Introduction : definitions and examples, stationarity-weak and
strong, discrete time, continuous time, state-space - finite, countable
and uncountable, Markov-chains - with finite and countable state spaces
- classification of states, limit theorems, elements of renewal theory,
Markov processes - Poisson process, pure birth, pure death, birth and death
processes, branching processes, queueing processes - M/M/1, M/G/1, GI/M/I.
Selected applications to - analysis of algorithms, performance evaluation
and modelling of computer systems.
(c) Three lectures and one tutorial per week.
(f) References :
C25: Information and
Coding Theory
(a) Information measure-noiseless coding, construction of optimal codes,
discrete memoryless channel - channel capacity, fundamental theorem of
information theory, error-correcting codes - minimum distance principles,
Hamming bound, general binary code, group code, linear group code, convolution
encoding - algebraic structure, Gilbert bound, threshold decoding - threshold
decoding for block codes, cyclic binary codes-BCH codes, generalised BCH
code and decoding, optimum codes - information rate, high-rate volume bound,
Elias bound, asymptotic error bound.
Non-cyclic codes, residue codes, Reed-Muller codes, orthogonizable
codes-condition for complete orthogonalization, non-binary BCH codeds-non
binary coding, modulation scheme, weight functions.
(c) Three lectures and one tutorial per week.
(f) References :
C26: Selected topics in recent developments in computer science as suggested by the faculty
A. Fuzzy Logic and
Application (given in the academic year 1993-94)
Brief overview of crisp sets; the notion of fuzziness; what, why and
when to apply fuzzy set; operations on fuzzy sets (general, axiomatic framework
with several examples like Hamacher, Frank, Yager, Dubois -- Prade etc.
).
Crisp relation, fuzzy relation and their relevance to the theory of
approximate reasoning; Max-* composition of fuzzy relation; computation
of Max-* transitive closure of a fuzzy relation; fuzzy relational equation
and related issues; probability measures of fuzzy events; fuzzy expected
value.
Basics of approximate reasoning, use of approximate reasoning to design
fuzzy systems, different methods of rules aggregation and defuzzification.
These topics will be covered keeping in view some applications - may be,
for example, the inverted pendulum problem or some pattern recognition/image
processing/computer vision problems. The instructor will decide the areas
of applications to cover.
Fuzzy measures - belief, plausibility and their properties; Dempster's
rule of combination; consonant body of evidence - possibility, necessity.
Measures of uncertainty - axiomatic formulation of Hartley information,
Shannon's entropy, concepts of joint and conditional entropy, and their
properties; measures of nonspecificity; measures of dissonance and confusion;
fuzziness measures.
(f) References :
B. Neural Networks and Their Applications
I. Preliminaries
Introduction to neural networks. Threshold logic, basic logic element,
circuit realization, network complexity. Introduction to biological neural
network, significance of massive parallelism.
II.
Basic neural network models
Perceptron, analysis of perceptron convergence, limitations of perceptron
and motivation for MLP. Multilayered perceptron, learning algorithms, selection
of number of layers and modes in a network, recurrent networks. Hopfield
model, pattern retrieval process, optimization problem, convergence. Simulated
annealing, mean-field annealing. Boltzman machine, learning. Feature map,
learning vector quantization, LVQ1,LVQ2. Adaptive resonance theory, ART1,
ART2, ART3, ARTMAP
III. Applications
Some (2 to 3) of the following topics will be covered: Applications
of NN to optimization, image processing, computer vision, speech processing,
natural language processing, pattern recongnition, knowledge representation,
artificial intelligence etc.
IV. Additional
topics
(At the descretion of concerned instructor, some (at most 2) of the
following topics may be covered) Hardware realization, cellular neural
networks, neurofuzzy computing, RBF networks and any other recent developments.
V. Projects/Assignments
Each student will be required to develop one or several neural network
models and use them to some of the applications described in part III.
(f) References
: