Department of Computer Science & Information Systems

PhD Qualifying Syllabus

The Department lays special emphasis on research work in various areas of specialization that include:

  • Artificial Intelligence, Machine Learning and Data Mining
  • Computer Architecture, Embedded Systems & Robotics
  • Data Warehousing Databases Advanced Databases
  • High Performance Computing and Distributed Systems
  • Image Processing & Multimedia
  • Networking and Mobile Computing
  • Algorithms & Theoretical Computer Science
  • Software Engineering, Software Architecture and Testing
Research Area 1: Artificial Intelligence, Machine Learning & Data Mining

Data Mining

Need for data mining, Preprocessing: Dimensionality reduction, Missing values, Normalization & standardization, Noise and outlier detection, Data smoothening Classification: Decision tree, K-nearest neighbors, Naive Bayesian classifiers, Rule based classifiers, Support vector machine, Underfitting/overfitting, Ensemble classifiers, Classification evaluation and model selection. Association rule mining, Frequent item set mining, Apriori and its optimizations, FPgrowth , Efficient Rule generation, Other measures (lift, interest etc), correlation, Hierarchybased Frequent item set mining, Clustering Type of clustering Partitioning clustering k-means, k-mediod (PAM) algorithms, Hierarchical clustering algorithms, Agglomerative algorithms--s-link, complete link, average link etc, Divisive algorithms, Density based clustering, DBSCAN, OPTICS algorithms, Grid based Clustering, Cluster evaluation.

Machine Learning

Introduction Polynomial Curve Fitting, Overfitting/underfitting & Regularization, Curse of Dimensionality.Some Useful Concepts MAP Hypothesis, Minimum Description Length (MDL) principle, Expectation Maximization (EM) Algorithm, Bias-variance decomposition, Lagrange Multipliers Mixture of Gaussians, PCA & SVD. Linear Models for Regression, Linear Basis Function Models. Linear Models for Classification, Discriminant Functions (binary & multiple classes), least square, Fisher's Linear Discriminant, Perceptron Algorithm, Probabilistic Generative Classifiers, Naive Bayes Classifier, robabilistic Discriminative Classifiers, Logistic Regression, Probit Regression. Non-linear Models, Decision Tress, Ensemble Classifiers, ANN, Instance-based Learning, K-NN, Case-based Reasoning. Support Vector Machines, Graphical Models, Bayesian Belief Networks, Hidden Markov Models .Unsuprevised Learning K-means, Mixture Models Reinforcement Learning, Q Learning, Non-deterministic rewards & actions, Temporal difference learning, Generalization

Artificial Intelligence

Problem Solving by Searching

Uninformed and informed search techniques including breadth first search, depth first search, depth limited search, iterative deepening search, Avoiding repeated states. Heuristics based searches including Greedy best first search, A* search, memory bounded heuristic search. Local search algorithms and problem solving including Hill climbing, Simulated annealing, local beam search, genetic algorithms etc. Adversarial search, alpha beta pruning, games problems.

Knowledge and Reasoning

Knowledge based agents, Propositional logic, syntax and semantics, equivalence, validity and satisfiability, forward and backward chaining, resolution. First order logic (FOL), syntax and semantics of FOL, Representation of real world domain using propositional and first order logic, Unification and lifting, quantifiers, Inference rules, conjunctive normal form for FOL, resolution for FOL. Reasoning systems for categories, semantic networks, description logic.

Uncertain knowledge and Reasoning

Uncertainty representation, basic probability notation, Inference using joint probability distribution table, Bayes' rule and its applications. Bayesian Networks: representation and semantics, inference in Bayesian Networks, Alternatives for Uncertain Reasoning: Rule Based Methods, Dempster-Shafer Theory, Fuzzy sets, Fuzzy Logic.


Inductive Learning, Decision trees, Ensemble learning, knowledge in learning, explanation based learning, statistical learning, learning with complete data, Maximum-likelihood parameter learning, Naive Bayes models, Gaussian Mixture Models, hidden Markov models, Instance based learning, Nearest neighbour models, kernel models, Kernel machines, Neural Networks models for learning, reinforcement learning.

Problem Solving by Searching

Uninformed and informed search techniques including breadth first search, depth first search, depth limited search, iterative deepening search, Avoiding repeated states. Heuristics based searches including Greedy best first search, A* search, memory bounded heuristic search. Local search algorithms and problem solving including Hill climbing, Simulated annealing, local beam search, genetic algorithms etc. Adversarial search, alpha beta pruning, games problems.

Research Area 2: Computer Architecture, Embedded Systems & Robotics

Computer Architecture

Computer Organization vs. Computer Architecture, Structure and Functions of various components of a computer system, Top level view of computer function, Instruction fetch and execution, Interrupts and I/O functions, Computer Memory System Overview, Memory hierarchy, Cache Memory Organization and Design, Performance measurement of two level memory system, I/O Modules and Organization, I/O Techniques, Arithmetic and Logic Unit, Data Representation- Integer & Floating Point Representation (IEEE-754) and Arithmetic Operations, Instruction Set characteristics and functions, Intel’s x86 ISA, Instruction Addressing Modes, Intel’s x86 Addressing Modes and Instruction Formats, Processor Organization, RISC and CISC Architectures, Instruction-level parallelism and Superscalar Processors and Design Issues, P-4 Super Scalar Pipeline, Micro Operations, Design Concepts, Hardwired and Micro-Programmed Control Design Issues, Micro Instruction Sequencing Methods.

Embedded Systems & Robotics - Introduction to Embedded Systems, Real Time Embedded Systems, Embedded system components, embedded processors and memory structures, Programming and Software for Embedded Processors, Peripheral Interface Controller (PIC) family of processors, ARM Processor, Embedded Systems I/O, and Networking, Sensing and Sensors, Robotic Vision, Mobility, Statics and Dynamics, Robot Kinematics, Human Robot Interaction.

Research Area 3: Data Warehousing, Databases & Advanced Databases

Data Warehousing

Introduction to Data Warehousing
Present Business Scenario, Operational and Informational Systems, What is a Data Warehouse? Applications of Data Warehouse, Problems with Data Warehousing

Data Warehouse Components, Processes & Architecture Source Systems, Data Staging Area, Presentation Server, Data Marts, Operational Data Store (ODS), Metadata, Information Delivery, Basic Processes of a Data Warehouse

Data Warehouse Design
Dimensional Modeling Basics, Facts, Dimensions, & Star Schemas, Snowflake & Starflake Schemas, Design Steps, ER modeling vs. Dimensional modeling, Surrogate Keys, Changing Dimensions, Conformed Dimensions, Factless Fact Tables, Minidimensions & Outriggers, Role-playing Dimensions, Multi-valued Dimensions

Extraction, Transformation, & Loading (ETL)
Data Extraction, Data Transformation, Data Loading, ETL Data Structures, ETL Tools: Build or Buy?

Online Analytical Processing (OLAP)
Need for OLAP, Features & Functions, ROLAP, MOLAP, HOLAP, & DOLAP,OLAP Implementation, OLAP Tools

Performance Enhancing Techniques
Partitioning, Aggregation, Materialization of Views, Bitmap Indexes

SQL Features for DW CUBE Operator, Roll-up Operator Top-N Queries, Window Queries, Real-Time Data Warehousing

Advanced Databases

Multidimensional Indexing: kD tree, Quad Tree, Partitioned Hash Indexes, R-tree

Query Opitmization: Heuristic optimization, Cost Based Optimization, Hybrid Approach, System-R Approach, View Materialization, Role of Metadata in Query Optimization

Distributed Database: Motivation & complexities, Homogeneous & Heterogeneous Distributed Databases, Distributed Data Storage, Data Fragmentation, Data Replication, Fragmentation & Replication, Data Transparency, Distributed Query Processing

Advanced Topics:NoSQL, Big Table, Big Data Management

Database Systems

Introduction to Database Systems
Objectives/Motivation, Evolution of Database Systems, Overview of a DBMS, Advantages of a DBMS, Database System Architecture

Data Modeling: Overview of Data Modeling, Entity-Relationship (ER) Modeling, Enhanced ER (EER) Modeling

Understanding Relational Model: Relational Model Concepts, Relation as a Mathematical Model, ER, EER to Relational model

Database Design through Functional Dependencies & Normalization: Functional Dependencies, Normal Forms: 1NF, 2NF, 3NF, BCNF, Criterion for Good Database Design, Multi-valued dependencies: 4NF

Query Language: Relational Algebra, SQL

Indexing: Indexing Structures, Primary & Secondary Indexes, Tree-structured Indexes, Hashbased Indexes, Bitmap Indexes

Query Processing: Introduction to Operator Evaluation, Algorithms for Relational Operators, Materialized and Pipelined Evaluation

Transaction management: Concurrency Control & Crash Recovery: Transaction Management Overview, Serial Schedule & Serializability, Conflict Serializability, View Serializability, Testing for Serializability, Recoverability & Cascadeless Schedules, Concurrency Control, Locking, Time-stamping, Crash Recovery, Log-Based, Shadow Paging

Software Engineering

Software Engineering Concepts and Methodologies; Software Requirements Analysis and Specification, Software Architecture, Detailed Design; Techniques of Design; Object Oriented Design, UML, Estimation; Software Project Planning, Integration & Validation; Software Quality Assurance; Software Maintenance; Automated Tools in Software Engineering.

Research Area 4: High Performance Computing & Distributed Systems

Parallel & High Performance Computing

  • General understanding
    Shared Memory & Distributed Memory Systems, Concurrency & Multi-threaded systems and Multi-processor systems
  • Multicore-systems
    Multi-core computing - homogeneous and heterogeneous, NUMA, and GPGPU computing;
  • Concurrency
    Shared Data and Shared Memory Data Structures; Mutual Exclusion and solutions (for multi-processor systems)
  • High Performance Systems and Solutions; Scaling Models and Techniques; Development Models; High Performance Environments
    Interconnects, Mapping, Scheduling, and Load Balancing.

Distributed Systems

  • Processes
    Threads; Virtualization; Client-server structure; code migration;
  • Communication
    RPC, Message & Stream Oriented Communication; Multicast communication;
  • Naming
    Flat, structured and attribute based naming; DHT; DNS; LDAP;
  • Synchronization
    Logical clocks; Mutual exclusion algorithms; Election Algorithms;
  • Caching, Consistency and Replication
    Distributed Caches, Data centric consistency models; client-centric consistency models; replica management; consistency protocols;
  • Fault Tolerance
    Failure models; Process resilience: agreement in faulty systems; failure detection; reliable client-server communication; reliable multicasting;
  • Distributed File Systems
    Architecture; communication; naming; synchronization; consistency & replication; fault tolerance;
Research Area 5: Image Processing & Multimedia

Introduction, Multimedia Authoring and Multimedia Data Representations

Introduction to Multimedia What is Multimedia / Components of Multimedia / Multimedia and Hypermedia / World Wide Web (HTTP, HTML, XML, SMIL) / Overview of Multimedia Software Tools (for Music Sequencing and Notation, Digital Audio, Graphics and Image Editing, Video Editing, Animation, Multimedia Authoring

Multimedia Authoring and Tools Multimedia Authoring (Metaphors, Production, Presentation, Automatic Authoring) / Some Useful Editing and Authoring Tools / Virtual Reality Manipulation Language

Graphics and Image Data Representations Graphics/Image Data Types (1-Bit Images, 8-Bit Gray-Level Images, Image Data Types, 24-Bit Color Images, 8-Bit Color Images, Color Lookup Tables) / Popular File Formats (GIF, JPEG, PNG, TIFF, EXIF, Graphics Animation Files, PS, PDF, Windows WMF & BMP, PAINT, PICT, PPM)

Color in Image and Video Color Science (Light and Spectra, Human Vision, Spectral Sensitivity of the Eye, Image Formation, Camera Systems, Gamma Correction, ColorMatching Functions, CIE Chromaticity Diagram, Color Monitor Specifications, Out-of-Gamut Colors, White-Point Correction, XYZ to RGB Transform, Transform with Gamma Correction, L*a*b* (CIELAB) Color Model, More Color-Coordinate Schemes, Munsell Color Naming System) / Color Models in Images (RGB, CMY, CMYK, Transformation from one model other, Printer Gamuts) / Color Models in Video (Video Color Transforms, YUV Color Model, YIQ Color Model, YCbCr Color Model) Fundamental Concepts in Video Types of Video Signals, Analog Video (NTSC, PAL, SECAM) / Digital Video (Chroma Subsampling, CCIR Standards for Digital Video, High Definition TV)

Basics of Digital Audio Overview of Physics of sound / Digitization of Sound / Musical Instrument Digital Interface / Quantization and Transmission of Audio

Multimedia Data Compression

Lossless Compression Algorithms Introduction, Basics of Information Theory, Run-Length Coding, Variable-Length Coding, Shannon–Fano Algorithm, Huffman Coding / Adaptive Huffman Coding / Dictionary-Based Coding / Arithmetic Coding / Lossless Image Compression / Differential Coding of Images / Lossless JPEG Lossy Compression Algorithms Distortion Measures / The Rate-Distortion Theory / Quantization / Uniform Scalar Quantization / Non-uniform Scalar Quantization / Vector Quantization / Transform Coding / Discrete Cosine Transform / Karhunen–Loeve Transform / Wavelet-Based Coding / Continuous Wavelet Transform / Discrete Wavelet Transform / Wavelet Packets / Embedded Zero-tree of Wavelet Coefficients / The Zerotree Data Structure / Successive Approximation Quantization / EZW Example / Set Partitioning in Hierarchical Trees

Image Compression Standards The JPEG Standard / main steps of JPEG / JPEG Modes / JPEG Bitstream / The JPEG2000 Standard / Main Steps of JPEG2000 Image Compression / Regionof-Interest Coding / Comparison of JPEG and JPEG2000 Performance / The JPEG-LS Standard / Prediction / Context Determination / Residual Coding / Near-Lossless Mode / Bilevel Image Compression Standards JBIG and JBIG2 Basic Video Compression Techniques and Video Coding Video Compression Based on Motion Compensation / Search for Motion Vectors ( Sequential, 2D Logarithmic, and Hierarchical search) / Standards H.261 and H.263 / Overview of MPEG-1, 2, 4, 7, and 21

Audio Compression Techniques Basic Compression Techniques / G.726 ADPCM / MPEG Audio Compression / Psychoacoustics / MPEG Audio Coding

Multimedia System Architecture

Media and Streams, Multimedia System Architecture Media Types / Media Classification / Continuous Media / Discrete Media / Time-dependent Media / Time-independent media / Transmission Modes / Notion of Logical Data Unit

Storage Media for Multimedia Overview of magnetic storage / Optical Storage (CD-ROM, CD-WORM, CD-RW, DVD)

Multimedia Operating Systems Real-time requirements / Resource Management / Process Management / File System & Disk Scheduling Algorithms / Architecture

Multimedia communication systems Transport subsystems / QoS / Resource Management & the trends

Multimedia Database Management Systems Characteristics / Data Analysis / Data Structure / Operations

Multimedia Application Architecture

Overview of Multimedia Document, Hypertext & MHEG Document Architecture / Hypertext / Relations expressed by links / MHEG

Overview of Multimedia User Interface Characteristics / User friendliness / User Interface through Video and Sound Multimedia Application Architecture Multimedia Food Chain / Media Preparation / Media Composition / Media Integration / Media Communication / Media Consumption / Overview of Virtual Reality Systems

Advanced Topics

Synchronization Notion of synchronization / Presentation Requirements / Reference Model & Specification Content-Based Retrieval in Digital Libraries How Should We Retrieve Images? / Current Image Search Systems / Relevance Feedback / Quantifying Results / Querying on Videos / Querying on Other Formats / Outlook for Content-Based Retrieval

Multimedia Network Communications and Applications Quality of Multimedia Data Transmission / Multimedia over IP / Multimedia over ATM Networks / Transport of MPEG-4 / Media- on-Demand (MOD)

Image Processing & Computer Vision

Introduction, Mathematical and Physical Background

Introduction Motivation / why is Computer Vision Difficult? / Image Representation and Image Analysis Tasks The Image, its Representations and Properties Image Representations, a Few Concepts / Image Digitization / Sampling / Quantization / Digital Image Properties / Metric and Topological Properties of Digital Images / Histograms / Entropy / Visual Perception of the Image / Image Quality / Noise in Images / Color Images / Physics of Color / Color Perceived by Humans / Color Spaces / Palette Images / Color Constancy / Cameras: An Overview / Photosensitive Sensors / A Monochromatic Camera / A Color Camera

The Image, its Mathematical and Physical Background Overview / Linearity / The Dirac Distribution and Convolution / Linear Integral Transforms / Images as Linear Systems / Introduction to Linear Integral Transforms / 1D Fourier Transform / 2D Fourier Transform / Sampling and the Shannon Constraint / Discrete Cosine Transform / Wavelet Transform / Eigen-Analysis / Singular Value Decomposition / Principle Component Analysis / Other Orthogonal Image Transforms / Images as Stochastic Processes / Image Formation Physics / Images as Radiometric Measurements / Image Capture and Geometric Optics / Lens Aberrations and Radial Distortion / Image Capture from a Radiometric Point of View / Surface Reflectance

Data Structures for Image Analysis Levels of Image Data Representation / Traditional Image Data Structures / Matrices / Chains / Topological Data Structures / Relational Structures / Hierarchical Data Structures / Pyramids / Quadtrees / Other Pyramidal Structures

Image Pre-processing, Segmentation and Mathematical Morphology)

Image Pre-Processing Pixel Brightness Transformations / Position-Dependent Brightness Correction / Gray-Scale Transformation / Geometric Transformations / Pixel Co-ordinate Transformations / Brightness Interpolation / Local Pre-Processing / Image Smoothing / Edge Detectors / Zero-Crossings of the Second Derivative / Scale in Image Processing / Canny Edge Detection / Parametric Edge Models / Edges in Multi-Spectral Images / Local Detection by Local Pre-Processing Operators / Detection of Corners (Interest Points) / Detection of Maximally Stable Extremal Regions / Image Restoration / Degradations That are Easy to Restore / Inverse Filtration / Wiener Filtration

Segmentation Thresholding / Threshold Detection Methods / Optimal Thresholding / MultiSpectral Thresholding / Edge Based Segmentation / Edge Image Thresholding / Edge Relaxation / Border Tracing / Border Detection as graph Searching / Border Detection as Dynamic Programming / Hough Transforms / Border Detection Using Border Location Information / Region Construction from Borders / Region Based Segmentation / Region Merging / Region Splitting / Splitting and Merging / Watershed Segmentation / Region Growing Post-Processing / Matching / Matching Criteria / Control Strategies of Matching / Evaluation Issues in Segmentation / Supervised Evaluation / Unsupervised Evaluation

Mathematical Morphology Basic Morphological Concepts / Four Morphological Principles / Binary Dilation and Erosion / Hit or Miss Transformation / Opening and Closing / Gray-Scale Dilation and Erosion / Top Surface, Umbra, and Gray-Scale Dilation and Erosion / Umbra Homeomorphism Theorem, Properties of Erosion and Dilation, Opening and Closing / Top Hat Transformation / Skeletons and Object Marking / Homotopic Transformations / Skeleton, Maximal Ball / Thinning, Thickening, and Homotopic Skeleton / Quench Function, Ultimate Erosion / Ultimate Erosion and Distance Functions / Geodesic Transformations / Morphological Reconstruction / Granulometry / Morphological Segmentation and Watersheds / Particles Segmentation, Marking, and Watersheds / Binary Morphological Segmentation / Gray-Scale Segmentation, Watersheds

Shape Description, Object Recognition and Image Understanding

Shape Representation and Description Region Identification / Contour-Based Shape Representation and Description / Chain Codes / Simple Geometric Border Representation / Fourier Transforms of Boundaries / Boundary Description using Segment Sequences / B-Spline Representation/Other Contour-Based Shape Description Approaches / Shape Invariants / Region-Based Shape Representation and Description / Simple Scalar Region Descriptors / Moments / Convex Hull / Graph Representation Based on Region Skeleton / Region Decomposition / Region Neighborhood Graphs / Shape Classes

Object Recognition Knowledge Representation / Statistical Pattern Recognition / Classification Principles / Classifier Setting / Classifier Learning / Support Vector Machines / Cluster Analysis / Neural Nets / Feed-Forward Networks / Unsupervised Learning / Hopefield Neural Nets / Syntactic Pattern Recognition / Grammars and Languages / Syntactic Analysis, Syntactic Classifier / Syntactic Classifier Learning, Grammar Inference / Recognition as Graph Matching / Isomorphism of Graphs and Sub-Graphs / Similarity of Graphs / Optimization Techniques in Recognition / Genetic Algorithms / Simulated Annealing / Fuzzy Systems / Fuzzy Sets and Fuzzy Membership Functions / Fuzzy Set Operators / Fuzzy reasoning / Fuzzy System Design and Training / Boosting in Pattern Recognition

Image Understanding Image Understanding Control Strategies / Parallel and Serial Processing Control / Hierarchical Control / Bottom-Up Control / Model- Based Control / Combined Control / Non-Hierarchical Control / RANSAC: Fitting via Random Sample Consensus / Point Distribution Models / Active Appearance Models / Pattern Recognition Methods in Image Understanding / Classification-Based Segmentation / Contextual Image Classification / Boosted Cascade of Classifiers for Rapid Object Detection / Scene Labeling and Constraint Propagation / Discrete Relaxation / Probabilistic Relaxation / Searching Interpretation Trees / Semantic Image Segmentation and Understanding / Semantic Region Growing / Genetic Image Interpretation / Hidden Markov Models / Coupled HMMs / Bayesian Belief Networks / Gaussian Mixture Models and Expectation-Maximization

3D-Vision and its uses

3D Vision, Geometry 3D Vision Tasks / Marr's Theory / Other Vision Paradigms: Active and Purposive Vision / Basics of Projective Geometry / Points and Hyperplanes in Projective Space / Homography / Estimating Homography from Point Correspondences / A Single Perspective Camera / Camera Model / Projection and Back-Projection in Homogeneous Coordinates / Camera Calibration from a Known Scene / Scene Reconstruction from Multiple Views / Triangulation / Projective Reconstruction / Matching Constraints. Bundle Adjustment / Upgrading the Projective Reconstruction, Self-Calibration / Two Cameras, Stereopsis / Epipolar Geometry Fundamental Matrix / Relative Motion of the Camera Essential Matrix / Decomposing the Fundamental Matrix from Point Correspondences / Rectified Configuration of Two Cameras / Computing Rectification / Three Cameras and Trifocal Tensor / Stereo Correspondence Algorithms / Active Acquisition of Range Images / 3D Information from Radiometric Measurements / Shape from Shading / Photometric Stereo

Use of 3D Vision Shape from X / Shape from Motion / Shape from Texture / Other Shape from X Techniques / Full 3D Objects / 3D Objects, Models, and Related Issues / Line Labeling / Volumetric Representation, Direct Measurements / Volumetric Modeling Strategies / Surface Modeling Strategies / Registering Surface Patches and their Fusion to get a Full 3D Model / 3D Model-Based Vision / General Considerations / Goad's Algorithm / Model-Based Recognition of Curved Objects from Intensity Images / Model-Based Recognition Based on Range Images / 2D View-Based Representations of a 3D Scene / Viewing Space / Multi-View Representations and Aspect Graphs / Geons as a 2D View-based Structural Representation / Visualizing 3D Real-World Scenes Using Stored Collections of 2D Views / 3D Reconstruction from an Unorganized Set of 2D Views

Advanced Topics

Advanced Techniques for Segmentation Mean Shift Segmentation / Active Contour Models -Snakes / Traditional Snakes and Balloons / Extensions / Gradient Vector Flow Snakes / Geometric Deformable Models - Level Sets and Geodesic Active Contours / Fuzzy Connectivity / Towards 3D Graph-Based Image Segmentation / Simultaneous Detection of Border Pairs / Sub-optimal Surface Detection / Graph Cut Segmentation / Optimal Single and Multiple Surface Segmentation

Texture Statistical Texture Description / Methods Based on Spatial Frequencies / Co-occurrence Matrices / Edge Frequency / Primitive Length (Run Length) / Laws' Texture Energy Measures / Fractal Texture Description / Multiscale Texture Description - Wavelet Domain Approaches / other Statistical Methods of Texture Description / Syntactic Texture Description Methods / Shape Chain Grammars / Graph Grammars / Primitive Grouping in Hierarchical Textures / Hybrid Texture Description methods / Texture Recognition Method Applications

Computer Graphics

Introduction and Basic Concepts

Introduction Image Processing as Picture Anal ysis / The Advantages of Interactive Graphics / Representative Uses of Computer Graphics / Classification of Applications / Development of Hardware and Software for Computer Graphics / Conceptual Framework for Interactive Graphics.

Basic Raster Graphics Algorithms for Drawing 2d Primitives Overview / Scan Converting Lines / Scan Converting Circles / Scan Convertiing Ellipses / Filling Rectangles / Fillign Polygons / Filling Ellipse Arcs / Pattern Filling / Thick Primiives / Line Style and Pen Style / Clipping in a Raster World / Clipping Lines / Clipping Circles and Ellipses / Clipping Polygons / Generating Characters / SRGP_copyPixel / Antialiasing.

Graphics Hardware Hardcopy Technologies / Display Technologies / Raster-Scan Display Systems / The Video Controller / Random-Scan Display Processor / Input Devices for Operator Interaction / Image Scanners.

Transformations and Viewing in 3D

Geometrical Transformations 2D Transformations / Homogeneous Coordinates and Matrix Representation of 2D Transformations / Composition of 2D Transformations / The Windowto-Viewport Transformation / Efficiency / Matrix Representation of 3D Transformations / Composition of 3D Transformations / Transformations as a Change in Coordinate System.

Viewing in 3D Projections / Specifying an Arbitrary 3D View / Examples of 3D Viewing / The Mathematics of Planar Geometric Projections / Implementing Planar Geometric Projections / Coordinate Systems.

3D Representation and Modeling

Representing Curves and Surfaces Polygon Meshes / Parametric Cubic Curves / Parametric Bicubic Surfaces / Quadric Surfaces.

Solid Modeling Representing Solids / Regularized Boolean Set Operations / Primitive Instancing / Sweep Representations / Boundary Representations / Spatial-Partitioning Representations / Constructive Solid Geometry / Comparison of Representations / User Interfaces for Solid Modeling.

Adding Realism and Color

Achromatic and Colored Light Achromatic Light / Chromatic Color / Color Models for Raster Graphics / Reproducing Color / Using Color in Computer Graphics

The Quest for Visual Realism Why Realism? / Fundamental Difficulties / Rendering Techniques for Line Drawings / Rendering Techniques for Shaded Images / Improved Object Models / Dynamics / Stereopsis / Improved Displays / Interacting with Our Other Senses / Aliasing and Antialiasing.

Visible-Surface Determination Functions of Two Variables / Techniques for Efficient VisibleSurface Determination / Algorithms for Visible-Line Determination / The z-Buffer Algorithm / List-Priority Algorithms / Scan-Line Algorithms / Area-Subdivision Algorithms / Algorithms for Octrees / Algorithms for Curved Surfaces / Visible-Surface Ray Tracing.

Illumination And Shading Illumination Modeling / Shading Models for Polygons / Surface Detail / Shadows / Transparency / Interobject Reflections / Physically Based Illumination Models / Extended Light Sources / Spectral Sampling / Improving the Camera Model / Global Illumination Algorithms / Recursive Ray Tracing / Radiosity Methods / The Rendering Pipeline.

Advanced Topics

Advanced Raster Graphic Architecture Simple Raster-Display System / Display-Processor Systems / Standard Graphics Pipeline / Introduction to Multiprocessing / Pipeline Front-End Architecture / Parallel Front-End Architectures / Multiprocessor Rasterization Architectures / Image-Parallel Rasterization / Object-Parallel Rasterization / Hybrid-Parallel Rasterization / Enhanced Display Capabilities.

Advanced Geometric and Raster Algorithms Clipping / Scan-Converting Primitives / Antialiasing / The Special Problems of Text / Filling Algorithms / Making copyPixel Fast / The Shape Data Structure and Shape Algebra / Managing Windows with bitBlt / Page Description Languages /

Advanced Modeling Techniques Extensions of Previous Techniques / Procedural Models / Fractal Models / Grammar-Based Models / Particle Systems / Volume Rendering / Physically Based Modeling / Special Models for Natural and Synthetic Objects / Automating Object Placement.

Research Area 6: Networking & Mobile Computing

Computer Networks:
Focus: Concepts, terminologies and techniques used in computer networking.

Background and Introductory Concepts: Uses of Computer Networks, the Network Edge, Network Core, Access Networks; Delay and Loss in Packet Switched Networks, Protocol Hierarchies, and their Service Models, Network Architectures (OSI, TCP/IP).

Application Layer: Hypertext Transfer Protocol, File Transfer Protocol: FTP, Mail Transfer Protocols (SMTP, MIME), Domain Name Systems (DNS), DHCP.

Transport Layer: Multiplexing, De-multiplexing, Principles of Reliable Data Transfer (Go-Back-N, and Selective Repeat). TCP: TCP working, TCP Flow Control; TCP Error Control and Congestion Control, UDP.

Network Layer: Datagram Networks, Router fundamentals, Forwarding and Addressing in the Internet. IP Addressing, Unicast Routing Algorithms (DVR, LSR, Path Vector) and Protocols (RIP, OSPF, Border Gateway Protocol. Concepts of mobility and roaming, Types of mobility, Types of IP-based Mobile Networking environments: Mobile IPv4 vis-a-vis Mobile IPv6.

Data Link Layer: Services, Error Detection and Correction Techniques; Multiple Access Protocol (Slotted ALOHA, Pure ALOHA, CSMA, CSMA/CD), Local Area Networks, Ethernet, Link Layer Addressing: MAC Addresses, ARP, RARP. Bridges, L-2 Switches, Introductory Exposure to the IEEE 802.11 WLANs: MAC Sub-layer aspects.

Physical layer: Bandwidth limited signals, Fourier analysis, Guided and unguided media, Channel capacity, Bandwidth, Bandwidth x Delay product, Repeater / Shared Hubs (L-1).

Network Programming: Socket API (TCP, UDP and raw sockets), UDP, Writing simple Clients and (Iterative and Concurrent) Servers, Network I/O fundamentals, Remote Procedure Calls and NFS, Exposure to Network Programming in Unix/Linux/Windows environment.

Network Security:
Overview of Network Security, Introduction to Cryptography, Secret Key Cryptography, Confidentiality using Symmetric Encryption (DES, 3-DES, AES), Public Key Cryptography (RSA, DSA), Elliptic Curve Cryptography, Integrity, Authentication and Non-Repudiation, Public Key Infrastructure, Needham Schroeder Protocol, Kerberos, IPSec: AH and ESP, Web security using SSL/TLS, Secure Electronic Transaction (SET), Pretty Good Privacy and S/MIME, Common attacks: Passive & Active forms. Firewalls, VPNs, IDS, Anti-Malware strategies and Mechanisms.

Research Area 7: Algorithms & Theoretical Computer Science

Data Structures and Algorithms

Algorithm analysis and asymptotic notation. Sorting and searching algorithms and applications. Design, implementation and applications of data structures including stacks, queues, priority queues, linked lists, hash table, heap, binary search tree, balanced binary search tree. Algorithm design techniques like Divide and Conquer, Greedy Approach, Dynamic Programming, Backtracking, Branch & Bound for designing algorithms. P, NP, NP Completeness. Theory of Computations- Finite automata and regular languages-equivalences, closure properties; Context free languages and push down automata-equivalences, closure properties; concepts in parsing; Turing machines; Computability and decidability-universal Turing Machine; recursive functions; church-Turing hypothesis; complexity classes - P, NP, reducibility and NP completeness.

Discrete Structures for Computer Science

Sets & operation on sets; relations & equivalence relations; number theory; weak & strong form of mathematical induction; principle of inclusion & exclusion, pigeonhole principle; recurrence relations & generating functions; digraphs & graphs, graph isomorphism & subgraphs, spanning trees, Euler & Hamiltonian graphs, planar graphs, chromatic numbers & graph coloring; groups.

Design & Analysis of Algorithms-

Basic Design Techniques –Divide-and-Conquer, Greedy, Dynamic Programming (Examples, Analysis, General Structure of Solutions, Limitations and Applicability). Specialized Design Techniques: Network Flow, Randomization (Examples, Analysis, Limitations). Complexity Classes and Hardness of Problems – P, NP, Reductions, NP hardness and NP- Completeness, Reduction Techniques, Basic NP-complete problems. Design Techniques for Hard Problems –Backtracking, Branch-and-Bound, and Approximation (General approaches and structure of solution, Analysis, and Limitations). Linear Programming – LP Problem and Simplex Algorithm, Approach for using LP for modeling and solving problems. Introduction to Design and Analysis of Parallel and Multithreaded Algorithms.

Research Area 8: Software Engineering, Software Architecture and Testing

Software Engineering and Management

Software Lifecycle Models: Introduction, Waterfall Model and its Variants: Classical Waterfall Model, Iterative Waterfall Model, V-Model, Prototyping Model, Incremental Development Model and Evolutionary Model. Rapid Application Development (RAD) Model, Spiral Model, Agile Development Models, Selection of Appropriate Lifecycle model for a project

Requirement Analysis and Specifications: Requirement Gathering and Analysis, Software Requirement Specification (SRS), Techniques for Handling Complex Logic through Semi-Formal techniques: Decision Trees and Tables, Formal System Specifications using Algebraic Specifications and Axiomatic Specifications.

Software Project Management Techniques: Techniques for Project Size Estimation: Lines of Code (LOC) and Function Point (FP). Project Estimation Techniques: Empirical Estimation Techniques, Heuristic Estimation Techniques: COCOMO, Complete COCOMO and COCOMO 2, Analytical Technique: Halstead’s Software Science. Staffing level Estimation, Project Scheduling: Work Breakdown Structure (WBS), Activity Networks, Critical Path Method, PERT Chart, Earned Value Analysis, Project Crashing.

Software Design: Outcome of Design Process, Classification of Design Methodologies, Characteristics of a Good Design, Modularity of Design, Cohesion and Coupling, Classification of Cohesion and Coupling. Function-Oriented Design and Object-Oriented Design

Software Reliability: Software Reliability: Hardware versus Software reliability, Reliability Metrics, Reliability Growth Models: Jelinski and Moranda Model, Littlewood and Verall’s Model, Basic Execution Model and Logarithmic Poisson Execution Model

Software Coding and Testing: Software Coding: Errors, faults and Failures, Techniques for Reducing the Bugs in program. Software Testing: Verification and validation, Pesticide Effect in testing, Test Cases, Minimal Test Suite, Unit Testing, Black-box Testing Strategies: Equivalence Class Partitioning Testing and its Derivatives, Special Value Testing Strategies: Boundary Value Analysis, Robustness Testing, Combinatorial Testing Strategies: Decision Table-Based testing and Pair-Wise Testing. White-Box Testing Strategies: Strong testing, Weaker testing, Complimentary testing, Coverage-Based Testing Strategies: Statement Coverage, Branch Coverage, Path Coverage, Condition Coverage, MC/DC Coverage, Data flow-based Testing Strategies

Software Architecture

Introduction: Introduction to Software Architecture and its importance What is Software Architecture? Architecture Structure and Patterns, Good architecture, Importance of Software architecture, Contexts of Software architecture, Design vs Architecture

Software Quality Attributes: Quality Classes, Understanding Quality Attributes: Usability, Availability, Interoperability, Testability, Performance, Modifiability, Security, Other Quality Attributes, Tactics

Designing the Architecture: Architecture and Requirements, Designing an architecture, Modularity of Software Architectures: Documenting the Architecture Documenting Software Architectures, Reliability

Architecture Patterns: Layering Patterns, Pipe & Filter, Blackboard, Distributed Systems, Reflection, Publish-Subscribe, Map-Reduce Patterns, MVC, Architecture Implementation, Testing, Reconstruction, Conformance, Linear Programming Model for Design Moving From Software Architecture to Software Design, Reliability of S/W Architectures, Physical View Introduction, Creational, Structure, Behaviour, Product Line and Product Mix of S/W Architectures Architecture Management, Architecture in the Context of Cloud Introduction to Cloud Computing, Service Models, Case, Software Architecture: Past, Present, and Future

Software Testing:

Preliminaries: Software Testing: Humans, Errors, and Testing (Errors, faults, and failures, Test automation, Developer and tester as two roles) Software Quality: Quality attributes, Reliability, Requirements, Behavior, and Correctness: Input domain, Specifying program behavior, Valid and invalid inputs, Correctness Versus Reliability: Correctness, Reliability, Operational profiles, Testing and Debugging: Preparing a test plan, Constructing test data, Executing the program, Assessing program correctness, Constructing an oracle, Test Metrics: Organizational metrics, Project metrics, Process metrics, Product metrics: generic, Product metrics: OO software, Progress monitoring and trends, Static and dynamic metrics, Testability, Software and Hardware Testing: Testing and Verification:, Defect Management:, Test Generation Strategies:, Static Testing: Walkthroughs, Inspections, Software complexity and static testing, Model-Based Testing and Model Checking: Types of Testing, Classifier: C1: Source of test generation, Classifier: C2: Life cycle phase, Classifier: C3: Goal-directed testing, Classifier: C4: Artifact under test, Classifier: C5: Test process models, The Saturation Effect: Confidence and true reliability, Saturation region, False sense of confidence, Reducing Δ, Impact on test process, Principles of Testing

Preliminaries: Mathematical: Predicates and Boolean Expressions, Control Flow Graph, Basic blocks, Flow graphs, Paths, Basis paths, Path conditions and domains, Domain and computation errors, Static code analysis tools and static testing, Execution History: Dominators and Post-Dominators, Program Dependence Graph, Data dependence, Control dependence, Call graph, Strings, Languages, and Regular Expressions

Domain Partitioning: Introduction, The Test Selection Problem, Equivalence Partitioning: Faults targeted, Relations, Equivalence classes for variables, Unidimensional partitioning versus multidimensional partitioning, A systematic procedure, Test selection, Impact of GUI design, Boundary Value Analysis:, Category-partition Method:, Steps in the category-partition method

Predicate Analysis: Introduction, Domain Testing: Domain errors, Border shifts, ON- OFF points, Undetected errors, Coincidental correctness, Paths to be tested, Cause-effect Graphing: Notation used in cause-effect graphing, Creating cause-effect graphs, Decision table from cause-effect graph, Heuristics to avoid combinatorial explosion, Test generation from a decision table, Tests Using Predicate Syntax: (A fault model, Missing or extra Boolean variable faults, Predicate constraints, Predicate testing criteria, BOR, BRO, and BRE adequate tests, BOR constraints for non-singular expressions, Cause-effect graphs and predicate testing, Fault propagation, Predicate testing in practice), Tests Using Basis Paths:, Scenarios and Tests

Test Generation From Finite State Models: Software Design and Testing, Finite State Machines, Excitation using an input sequence, Tabular representation, Properties of FSM, Conformance Testing, Reset inputs, The testing problem, A Fault Model, Mutants of FSMs, Fault coverage, Characterization Set, Construction of the k-equivalence partitions, Deriving the characterization set, Identification sets, The W-Method, Assumptions, Maximum number of states, Computation of the transition cover set, Constructing Ζ, Deriving a test set , Testing using the W-method, The error detection process, The Partial W-Method, Testing using the Wp-method for m = n, Testing using the Wp-method for m > n, The Uio-sequence Method, Assumptions, UIO sequences, Core and non-core behavior, Generation of UIO sequences, Explanation of gen-uio, Distinguishing signatures, Test generation, Test optimization, Fault detection, Automata Theoretic Versus Control- Flow Based Techniques, n-switch-cover, Comparing automata theoretic methods

Test Generation from Combinatorial Designs: Combinatorial Designs,Test configuration and test set, Modeling the input and configuration spaces, A Combinatorial Test Design Process, Fault Model, Fault vectors, Latin Squares, Mutually Orthogonal Latin Squares, Pairwise Design: Binary Factors, Pairwise Design: Multi-Valued Factors, Shortcomings of using MOLS for test design, Orthogonal Arrays, Mixed-level orthogonal arrays, Covering And Mixed-level Covering Arrays, Mixed-level covering arrays, Arrays of Strength > 2, Generating Covering Arrays

Test Adequacy Assessment Using Control Flow and Data Flow: Test Adequacy: Basics, (What is test adequacy?), Measurement of test adequacy, Test enhancement using measurements of adequacy, Infeasibility and test adequacy, Error detection and test enhancement, Single and multiple executions, Adequacy Criteria Based on Control Flow: (Statement and block coverage, Conditions and decisions, Decision coverage, Condition coverage, Condition/decision coverage, Multiple condition coverage, Linear code sequence and jump (LCSAJ) coverage, Modified condition/decision coverage, MC/DC adequate tests for compound conditions, Definition of MC/DC coverage, Minimal MC/DC tests, Error detection and MC/DC adequacy, Short-circuit evaluation and infeasibility, Basis path coverage, Tracing test cases to requirements), Concepts from Data Flow: (Definitions and uses, C-use and p-use, Global and local definitions and uses, Data flow graph, Def-clear paths, Def-use pairs, Def-use chains, A little optimization, Data contexts and ordered data contexts), Adequacy Criteria Based on Data Flow: (c-use coverage, p-use coverage, All-uses coverage, k-dr chain coverage, Using the k-dr chain coverage, Infeasible c- and p-uses, Context coverage), Control Flow Versus Data Flow:, The “Subsumes” Relation, Structural and Functional Testing, Scalability of Coverage Measurement

Test Selection, Minimization, and Prioritization for Regression Testing: What is Regression Testing?, Regression Test Process: (Revalidation, selection, minimization, and prioritization, Test setup, Test sequencing, Test execution, Output comparison), Regression Test Selection: the Problem, Selecting Regression Tests: (Test all, Random selection, Selecting modification traversing tests, Test minimization, Test prioritization), Test Selection Using Execution Trace: Obtaining the execution trace, Selecting regression tests, Handling function calls, Handling changes in declarations, Test Selection Using Dynamic Slicing: (Dynamic slicing, Computation of dynamic slices, Selecting tests, Potential dependence, Computing the relevant slice, Addition and deletion of statements, Identifying variables for slicing, Reduced dynamic dependence graph, Scalability of Test Selection Algorithms), Test Minimization: (The set cover problem, A procedure for test minimization, Test Prioritization).

Unit Testing: Introduction, Context, Test Design, Using JUnit, Stubs and Mocks: Using mock objects

Integration Testing: Introduction, Integration Errors, Dependence: (Class relationships: static, Class relationships: dynamic, Class firewalls, Precise and imprecise relationships), OO versus Non-OO Programs, Integration Hierarchy, Choosing an integration strategy, Comparing integration strategies, Specific stubs and retesting, Finding a Near-optimal Test Order: (The TD method, The TJJM method, The BLW method, Comparison of TD, TJJM, and the BLW methods, Which test order algorithm to select?), Test Generation: (Data variety, Data constraints), Test Assessment.