|
Subject Code: CS5TI/1S5T Max.
I.A. Marks 25
Duration of Exam: 3 Hrs
Subject: Title Analysis And
Design Of Algorithms
Max. Exam. Marks :100 Total
contact hrs: 48
Contents:
I. INTRODUCTION
6
Hours.
Program Performance Space and Time Complexit; Asymptotic Notation:; Practical
Complexiti and Performance Measurement.
2. GRAPHS
6
Hours
Definitions; Applications; Properties: The ADTs Graph and Digraph;
Representation of Graphs and Digraphs; Representation of Networks; Class
Defrnitions; Graph Iterators; Language Features; Graph Search Methods -
Breadth-First Search, Depth-First Search; Applications- Finding a path.
Connected Graphs and Components, Spanning Trees.
3. THE GREEDY METHOD
6 Hours
Optimization Problems; The Greedy Method; Applications - Container Loading,
0/1 Knapsack problem, Topological sorting, Bipartite Cover, Single Source
Shortest Paths, Minimum Cost SpanninI Trees Kniskal, Prim, Sollin.
4. DIVIDE AND
CONQUER
6 Hours
Divide and Conquer Method; Applications - Defective Chessboard, Merge sort,
Quick sort, Selectioa Closest Pair of Points; Solving Recurrence Equations;
Lower Bounds on Complexities.
5.. DYNAMIC PROGRAMMING 6
Hours
Dynamic Programtning Method; Applications - Oil Knapsack Problem, Image
Compression, Matrix Multiplication Chains, All Pairs Shortest Paths, Non
crossing Subset of Nets, Component Folding.
6. BACDRK.TRACKING AND BRANCH AND BOUND
9
Hours
Backtracking Method; Applications - Container Loading, 0/I Knapsack Problem,
Max Clique, Travefling Salesperson, Board Permutation; Branch and Bound
Method; Applications - Container Loading, 0/I Knapsack Problem, Max Clique,
Travelling Salesperson, Board Permutation.
7. NP-COMPLETENESS AND APPROXIMATION ALGORITHMS
9
Hours
Polynomial Time and Verification, NP-Completeness and Reducibility,
Approximate Alg(.rithnls for the Vertex-Cover Problem and the Travelling
Salesman Problem.
Text Books:
1. Sartaj Sahni, Data Structures, Algorithms, and Applications in C++,
McGraw-Kill, 1998. (Chapters 2, 12,13,14,15,16, l7)
2. Thomas H Cormen, Charles F Leiserson & Ronald L Rivest, Introduction
to algorithms, Prentice.HaIl Jndia, 1998. (Chapters 36.1,36.2, 36.3.37.1,
37.2)
Reference Books
1 Gi!les Brassard & Paul Brattley, Fundamental Algorithms, Prentice-Hall,
1997.
2. Aho, Hoproft &Ullman, The Design and Analysis of Con'outer Algorithms,
Addison VesIey,1998
3. Basse and Allen Wan Gelder, Computer Algorithnis, Intro(Action to Design
and Analysis, Th Edition, Addison Wesley, 2000.
Subject Code CC5T2/1S5B4 Max.I.A.
Marks: 25
Duration of Exar :3 Hrs
Subject
Title :System Software
Max. Exam, Marks :100 Total
contact hrs: 48
Contents
1. MACHINE ARCHITECTURE AND ASSEMBLERS
12 hours.
Introduction, System software are and machine architecture; Simplified
Instructional Computers (SIC)- SIC Machine Architecture, SIC/XE Machine
Architecture, SIC Prngramming Examples; Traditional (CISC) Machines- \'AX
Architecture, Pentium Pro Architecture; RISC Machines- Ultra SPARC
Architecture, PowerpC Architecture, Cray T3E- Architecture. Assembler :
Definition, A Simple SIC Assemhl,-r, Assembler Algoritltm & Data
Structures: Machine- Dependent Assembler Features- Literals,
Symbol-Definition statements, Expression, Program blocks, Control Sections
and Programming Linking; Assembler Design Options- One-pass Assembler,
Multi-Pass As3emblers; Implementation Examples- MASM Assemb'er, SPARC
Assembler, AIX Assembler.
2. LOADERS, LINKERS, EDITORS, DEBUGGING SYSTEMS
12
Hours
Basic Loader Functions- Design of an Absolute Loader, A Simple Bootstrap
Loader; Machine- dependent Loader Features- Relocation, Program Linking,
Algorithm and Data Structures for a Linking Loader; Machine-independent
Loader Features- Automatic Library Search, Loader Options, Loader Design
Options - Linkage ~Editor, Dynamic Linkage, Bootstrap Loaders; Implementation
Examples - MS-DOS Linker, SunOS Linker, Cray MPP Linker. Text Editors -
Over-view of Editing Process, User Interface, Editor Structure; Interactive
Debugging Systems - Debugging Functions and Capabilities, Relationship with
other parts of the system, User- Interface Criteria.
3. MACRO
PROCESSORS
6 Hours.
Basic-Macro Processor Functions- Macro Defmition and Expansion, Macro
Processor Algorithrn & Data Structares; Machine-independent Macro
Processor Features - Concatenation of Macro Parameters, Generation of Unique
Labels, Conditional Macro Expansion, Keyword Macro Parameters; Macro
Processor Design Options - Recursive Macro Expansion, General-purpose Macro
Processors, Macro Processing within Language Translators; Implementation
Examples - MASM Macro Language, ANSI C Macro Language, The ELENA Macro
Processor.
4.
COMPILERS
12 Hours
Basic Compiler Functions - Grammars, Lexical Analysis, Syntactic Analysis,
Code Generation; Machine-Dependent Compiler Features - Intermediate Form of
the program, Machine-Dependent Code Optimization; Macliine-Independent
Compiler Featutes - Structured Variables, MachineIndependent Code
Optimization, Storage Allocation, Block-structured Languages; Compiler Design
Options - Division into Passes, Interpreters, P-code compilers,
Compiler-Compilers.
5. LEX AND YACC
6
Hours
A language specifying lexical analyser ( LEX ) and parser generator ( YACC),
Examp~es of Using LEX and YACC.
Text Book:
1. Leland L Beck, System Software, Third Edition, Addison-Wesley, 1997.
(Chapters 1, 2, 3,4, 5 (Except 5.5), 7.2, 7.3 )
2. Alfred V Aho, Ravi Sethi, and Jeffrey D UlIman, Compilers Principles,
Techniques and Tools, Addison Wesley, 1986. (Chapters 3.5 and 4.9)
ReferenceBooks:
1. D M Dhamdhere, Systems Programming and Operating Systems, Edition,
TMH, 1999. 2. Kemighan and Pike, The UNIX Programming Environment.
Subject Code: CSST3/IS5A4
Duration of Exain 3 Hrs
Subject Title Operating Systems
Max. Exam. Marks 100
Total contact hrs 48
Max. I.A. Marks 25
Contents:
I. INTRODUCTION
6 Hours
Batch Systems, Concepts of multi programming and time-sharing, parallel,
distributed and real-time systems. Operating system structures - Operating
system components and services, System calls, system programs, Virtual
machines.
2. PROCESS
MANAGEMENT
6 Hours
Process concept, Process scheduling, Cooperating processes, Threads,
Interprocess communication, CPU scheduling criteria, Scheduling algorithms,
Multiple-processor scheduling, Real-time scheduling, Algorithm evaluation.
3. PROCESS SYNCHRONIZATION AND DEADLOCKS
10
Hours
The Critical-Section problem, Synchronization hardware, Semaphores, Classical
problems of synchronization, Critical regions, Monitors. Deadlocks - System
model, Characterization, Deadlock Prevention, Avoidance and Detection,
Recovery from deadlock. Combined approach to deadlock handling.
4. STORAGE
MANAGEMENT
16 Hours
Meniory Inanagellient logical and Physical address space, Swapping,
Contiguous allocation, Paging, Segnientation. Segmentation with paging in
MULTICS an(l Intel 386. Virtual Memory dEMAND pagilig and its perforniance.
Page replacement algorithms. Allocation of frames, Thrashing, Page size and
other consideratioris. Demand segmentation. File systems, Secondary Storage
Structure - File concept, access methods, directory structure, protection and
consistency semantics, File-system structure, Allocation methods, Free space
management, Directory implementation, Efficiency and performance, Recovery,
Disk structure, Disk scheduling methods, Disk management, Swap-Space
managc.ient, Disk reliability. Protection and Security Goals of protection,
Domain of protection, Access Matrix, Implementation of Access Matrix,
Revocation of Access Rights, Language based protection, The Secunty problem,
Authentication, One-Time Passwords, Program threats, System threats, Threat
Monitoring, Encryption.
5. CASE STUDY - Windows NT and LINUX Operating
Systems 10 Hours
Windows NT - Design principles, System components, Environmental subsystems,
File system, Nctx'orking and programme interface. Linux System - Design
principles, Kernel Modules, Process Management, Scheduling, Memory
management, File Systems, Input and Output, Interprocess comrnunication,
Network structure, Security.
Text Book:
I. Abraham Silberschatz and Peter Baer Galvin, Operating System Concepts,
Fifib Edition, Addison-Wesley 1998.( Chapters 1, 3.l, 3.2,3.3,3.4,3.6,4,5,6
(Except 6.8,6.9), 7,8,9, 10, II, 13 (Except 13.6),19 (Except 19.6), 20
(Except 20.8,20.9), 22, 23 )
Reference Books
1. Milan Milankovic, operating Systems, Concepts and Design Second Edition,
McGraw.Hill, 1992.
2. Harvey M Detal, ()periting Systems, Second Edition, Addison-Wesley, 1990.
3. Richard Peterson, Linux The Complete Reference, Osborne McGraw-Hill,
January 1998.
Subject Code C55T4 /1S5133
Duration of Exam:3Hrs
Subject Title Computer Graphics
Max. Exam. Marks 100
Total contact hrs :48
Max. I.A. Marks 25
Contents
1. INTRODUCTION
9
hrs
Image Processing as picture analysis, Advantages of interactive graphics,
Representative use.of computer graphics, Classification of applications,
Development of hardware and software for computer graphics, Conceptual
framework for interactive graphics, Drawing with SRGP, Basic interaction
handling, Raster graphics features, Limitations of SRGP, hardcopy
technologies, Raster scan display Systems, The video controller, Random-scan
display processor, Input devices for operato. interaction, Image scanners.
2.RASTER GRAPHICS
ALGORITHMS
9 Hour
Overview, Scan convertilig lines, Scan converting circles, Filling
recta~:~tes Filling polygons, Filung Ellipse arcs, Pattern filling, Thick
primitives, line style and pen style, Clipping in a raster world, Clipping
lines, Clipping circles and ellipses, Clipping polygons, Generating
characters, SRCP Hardcopy pixel, Antialiasing.
3.GEOMETRICAL TRANSFORMATIONS
6 hour's
2D transformations, Homogeneous coordinates and Matrix representation of 2D
transformations, Composition of 2D transformations, the window-to-viewport
transformation, Efficiency, Matrix representation of 3D transformations,
Composition of 3D transformations, Transformations as a change in coordinate
system.
4.VIEWING IN 3D
. 6
Hours
Projections, Specifying an arbitrary 3D view, Examples of 3D viewing, The
Mathematics of plan geometric projections, Implementing planar geometric
projections, Coordinate systems.
5. INTERACTON TECIINIQUES, DIALOG DESIGN AND USER INTERFACE SOFTWARE
6 Hours
Interaction hardware, Basic interaction tasks, Composite intcractions tasks,
The Form and Content User-Computer dialogues, User-interface styles,
Important design considerations, Modes and synta Visual design, The dcsign
methodologies.
6. REPRESENTING CURVES AND
SURFACES 6
hours
Polygons meshes, Parametric cubic curves, Parametric Bicubic surfaces,
Quadric surfaces.
7. VISIBLE SURFACE DETERMINATION
6
hours
Functions of two variables, Techniques for efficient visible-surface
algorithms, Algorithms Visible-Line determination, Z-buffer algorithm,
List-priority algorithms, Scan-line algorithms, Are. Subdivision algorithms,
Algorithms for Octrees, Algorithms for curved surfaces, Visible-Surface r
tracing.
Text Book:
James D Foley, Andries van Dam, Steven K Feiner, John F Hughes, Computer
Graphics, Addison-Wesley 1997. ( Chapters 1, 2, 3 (except 3.4), 4 (except
4.2), 5, 6, 8, 9, 11, 15)
Reference Book
1. Donald Hearn and M Pauline Baker, Computer Graphics, Second Edition,
Prentice Hall of india 1994
Subject Code CS5L5/1S5L5
Duration
of Exam :3 Hrs
Subject Title Algorithms Lab Max.
Exam. Marks :100
Max. l.A. Marks 25
Contents
Problems such as the following using C or C++:
1. Kruskal's algorithm
2. Prim's algorithm
3. Shortest path, Scheduling
4. Time and space complexity ofbinary search
5, Quicksort
6. Dynamic Programming
7. Knapsack problem
8. Floyd's algoritlrrn
9. DFS & BFS searches
10. Queen Problem
11. Travelling sales person problem.
Duration of Exam :3
Hr
Subject Code CS5AI/ ISSAl
Max. Exam. Marks :100
Subject Title Advanced Data Structure Using C++ Max. I.A. Marks
25
Total contact hrs 48
Contents:
1. REVIEW
6
Hrs
Review of classical data structures using C++; Abstract Data Types, The List
ADT; The Stack ADT The Queue ADT.
2. TREES
6 Hrs.
Preliminaries; Binary Trees; The Search Tree ADT; AVL Trees; Splay Trees;
Tree Traversal.' (Revisited); B-Trees.
3. HASHING, PRIORITY QUEUES (HEAPS)
6
Hrs.
General Idea; Hash Function; Qpen Hashing ; Closed Hashing; Rehashing;
Extendible Hashing Priority Queues: Model; Simple Implementations; Binary
Heap; Applications of Priority Queues; d-Heaps; Leftist Heaps; Skew Heaps;
Binomial Queues.
4. THE DISJOINT SET ABSTRACT DATA TYPE; AMORTIZED ANALYSIS
6Hrs.
Disjoint Set ADT Equivalence Relations; The Dynamic Equivalence Problem;
Basic Data Stn~cture Srnart Union Algorithms; Path Compression; Worst Case
for Union-by-Rank and Path Compression An Application. Amortized Analysis: An
Unrelated Puzzle; Binomial Queues; Skew Heaps Fibonacci Heaps; Splay Trees.
5. USING
STL -I
12Hrs
Introduction; Overview of STL Components; How STL Differs from Other
Libraries; Iterators Generic Algorithms.
6. USING STL -
II
12Hrs.
Sequence Containers; Sorted Associative Containers; Function Objects;
Container Adapters; Iterato Adaptors; Function Adaptors; A Program for
Searching a Dictionary; Defining an Iterator Class Combining STL With Object
-Oriented Programming.
Text Books:
1. Mark Allen Weiss: Data Structures and Algorithm Analysis in C++,
Addison-Wesley 1999.(Chapters 3,4,5,6,8,11).
2. David R. MMsser and Atul Saini: STL Tutorial alid Reference Guide,
Addison-Wesley, l996 (Capters Ito 12 ,16,17).
Reference Books:
1. yedidyah Langsam, Moshe J. Augen stein, Aaron M Tenen baum : Data
Structures Using C a C++, Prentice-Hall India, 1996.
2 Glenn W.Rowe Introduction to Data Structures and Algorithms with C ++,
Prentice -- Hall Indi 1997.
3. Cormen, T. H. et si Introduction to Algorithms, Prentice-Hall India, 1998.
4. D. E Knuth : The Art of Computer Programming : Volume I Fundamental
Algorithms ( Secon Edition ), Addison-Wesley, 1973.
Subject Code C55A2/IS5A2
Duration
of Exam 3 Hrs
Subject Title Data compression Techniques Max.
Exam. Marks 100
Total contact hrs 48 Max
I.A. Marks 25
Contents
I. INTRODUCTION: Compression Techniques, Lossless compression, Lossy
compression, Measures of performance, modeling and coding. 2 hours
2. MATHEMATICAL PRELIMINARIES: Overview, Introduction to information
theory, models: physical models, Probability models, Marko models 4 hours
3. HUFFMANCODING: Good codes, Huffman coding algorithm, minimum
variance Huffman codes,length of Huffman codes, extended Huffman codes, non
binary Huffman codes, Adaptive Huffman codes, Applications. 8 hours
4 ARITHMETIC CODES. Overview, coding a sequence, generating a binary
code,Comparision of Huffman and Arithmetic coding ,application. 6 hours
5 LOSSLESS IMAGE COMPRESSION: Introduction, facsimile encoding, Run
length encoding, progressive image transmission , othcr approaches. .4
hours
6 VECTOR QUANTIZATION: lntroduction , advantages, LBG-algorithm, empty
cell problem , Tree structured vector quantizer ,other vector quantization
schemes. 8 hours
7 DIFFERENTIAL CODING: Overview, Introduction, Basic Algorithm DPCM,
ADPCM, Delta modulation, CFDF, speech coding. 6 hours
8 TRANSFORM CODING: Diffcrent trnsforms, Quantization and coding of
transforms,application to image compression. Wave Let Transforms and data
Compression Introduction, Transform coding, DTWT for image Compression, Audio
compression, Video coding using multi-resolution techniques. 10 hours
Text Book:
1. Khalid Sayood Introduction to Data Compression: second edition Jan 1996,
Morgan Kaufmann Publilcations. (Chapters 11 to 1.2, 2.1 to 2.3, 3.1 to 3.6,
4.1 to 4.6, 6.1 to 6.5, 9.1 to 9.6, 10.1 to 10.7, 12.1 to 12.6)
Reference Books:
1.Ralf Steinmetz and Klara Nahrstedt, Multimedia computing and communication
andl applications, Prentice Hall Intl. 1995.
2 Raghuveer M. Rao, Wave let transforms : Introduction to theory and
applications, Addison Wesley pub. Co. ltd, 1998.
Subject Code:CS5A3/IS5A3 Subject
Title Software Practice and Testing
Max.Exam-Marks: 100
Total Contact Hrs: 48
Max. IA. Marks :25
Contents:
1. SOFTWARE PRACTICE -I 6Hrs.
Style: Names, Expressions, Statements, Consistency and idioms, Function
Macros, Constants, Comments; Interface: CSV, Prototype Libraries, Interface
principles, Resource management, User Interfaces.
2. SOFTWARE PRACTICE -2 6Hrs.
Algorithms and Data Structures: Searching, Sorting, Libraries, Growing
:ai'rays, J ists, Trees, Hash Tables. Design and Implementation: Markov Chain
algorithm, Data Structure alternatives, Building the Data Structure in 'C' ,
Generating the output, Performance, Lessons.
3. SOFTWARE PRACTICE-3 6Hrs.
Performance: Performance bottlenecks, Timing and Profiling, Speed, Space
efficiency, Estimation, Portability: Language, Headers and Libraries, Program
Organization, Isolation, Data Exchange, Byte order, Portability and Upgrade,
Internationalization.
4. SOFTWARE PRACTICEA 6Hrs.
Notation: Formatting data, Regular Expressions, Programming tools, Interpreters
and Compilers, Program generators. Macros. Debugging: Debuggers, Clues and
bugs, debugging tools.
5. SOFTWARE TESTING PROCESS MATURITY AND FRAMEWORK FOR TEST PROCESS
IMPROVEMENT 6Hrs.
The Six essentials of Software Testing: The State of the art and the State of
the practice; The clean sheet approach to getting started. Establishing a
practical perspective; Critical Choices: What, When, and Jiow to Test;
Critical Disciplines: Frameworks for Testing.
6. TESTING METHODS 12Hrs.
Verification Testing: Basic Verification Methods, Getting lcvcrage on
verification, Verifying documents at diffcrcnt phases, Getting the bcst from
verification,Three critiical success factors for implementing verification,
Reeon~nendations; Validation Testing: Validation Overview, Validation
Methods, Validation activities, and Recommendation strategy for validation
testing; Controlling Validation Costs: Minimizing the cost of performing
tests, Minimizing the cost of maintaining the tests. Minimizing val id~tion
Testware development costs, Recommendations; Testing Tasks, Deliverables, and
Chronology: Master Test planning, Verification testing tasks and
deliverables, Validation testing tasks and deliverables, A Testing orphan -
User manuals, Product release criteria, Summary of IEEE/ANSi test related
documents, Life-cycle mapping of tasks and deliverables; Software Testing
Tools: Categorizing test tools, Tool acquisition; Measurement: Measurement
provides answers, Useflil measures, and other interesting measures,
Recommendations.
7. MANAGING TEST TECHNOLOGY, STANDARD CHECKLISTS 6 Hrs Organizational
Approaches to Testing: Organizing and reorganizing testing, Structural d~sign
elements, Approaches to organizing the test function, Selecting the right
approach; Current practices, trends, challenges: Gills: What's New here?,
Usage Testing, I~cstcr-to-dcveloper ratios, Software measures and practices
benchmark snidy; Getting sustainable gains in place: Getting gains to happen,
Gctting Help, Follow-up; Standards relevant to Software Engluecring and
Testing; Verification Checklists.
Text Books:
I. Brian W. Kernigham and Rob Pike: The Practice of Prograninung,
Ad(lison-Weslcy, I 999.(Chaptei 1,2,3,4,5,7,8,9) 2. Fd Kit : Soflwaic Testuig
in the Real world, Addison-Wesley, 1995 (Chapters 1 to 15, Appendices A an(
B).
Reference Books:
1.William Perry: I flective Methods for Softwarc ~'estiiig (Second L.dition),
Jul ii Wiley, 1999.
2. Beizer. B: Software Testing Techniques.(Second Edition), Van Nostrand
Reinluold, 1990.
3. Myers, G. J. : The Art of Software Testing, John Wiley, 1979.
4. Steve Maguire : Writing Solid Code, Microsoft Press, 1993.
Subject Code CS5A4/IS512
Duation of Exam 3 hrs
Subject Title Introduction to UNIX
Max. Exam.
Marks :100
Total contact hrs 48
Max.
l.A. Marks 25
Contents
1.BASIC CONCEPTS-I 12 hrs.
Getting Started; Brief History Un derstandnigThe UNIX Command, General -
Purpose Utilities banner; cal; date; calendar; who; ety; uname; passwd; lock;
echo; tput. spell script: spell and Navigating the file system: The File,
What's in a File(namc), The Parent-Child Relationship, pwd The Home
Directory, Absolute Pathnames, Using the Absolute Pathoame for a Command. cd:
mkdir rmdri; Is; Relative Patlinames, The UNIX.filesystem Handling ordinary
files act, cp, rio; niv niore; Ip; tile; wc; od; split; emp; com; diff..The
Shell :sh: The Command, Pattern Matching The Wild cards, Escaping .the
Backslash(\), Quoting, Redirection, /dev/null and dev/tty: Two Spec ia Files,
Pipes, Tees, Comman(l Substitution, Shell Variables,the Shell's 'l'reatment
of the Comman( Line, The Korn, Bash and C Shells.
2. BASIC CONCEPTS-II
12hrs
The vi Editor: The Three Modes,
input Mode, Saving, The Repeat Factor, Command NIode, Deletion Navigation,
Pattern Search, Joining Lines, Repeating the Last Command, Undoing Last
Editin Instructions, Search and Replace. The Environrnti:f: System Variables,
profile, stty; PWD; Assasci Command history, On-line Command Editing, set
Option , Miscellaneous Features.Basics file attributes Is -I; -d option file
perniissions, chmod simple filters : the sample data base,pr;head; tail; cut
,apste sort uniq; nl ;tr.Regular Experession and The grep family,grep regular
expressions,egrep;fgrep.the process The sh Procress ,Parents and Children
,ps,System Processes,Mechanism of process creation, Internal and external
Commands, Running Jobs in Background, kill nice; Job Control in the Korn and
flash Shells, at and batch; cron.write; mesg; talk; mail; elm; pine; finger;
Connecting to Remote Machines. Aiore :Attributes: File Systems, Ihe mode,
chown and chgrp; Listing by Modification and Access Times touch; In; The
Directory, The Device.
3. TOOLS. 12 hrs.
Shell Programmimg:Shell Scripts, read; Command Line Arguments; Exit Status,
&& and ||;ex it; if,case Conditionals; expr; sleep an&wait;
while; until; for; $@; Redirection;The here document; SC trap; Sample
Validation and Data Entry Scripts. Advanced Filters: A sed Instruction, Liii
Addressing, Inserting and Changing Text, Context Addressing, Writing Selected
Lines to a File, -f Option; Substitution; Properties of Regular Expressions,
Simple awk Filtering , Splitiing a in to Fields, printf; the I.ogical and
Relational Operators, Number Processing, Variables Option; The BEGIN aud END
Sections, Positional Parameters, getlinc; Built-in Variable Arr Functions,
Interface with the Shell, Control Flow. pen - 7he Afasier Waniptilator:
n" Re' I Sample Database, Startiug perl, The chopO Function, Specifying
the Interpreter, Varianics a' Operators, Specifying Filenames in Command Line
$_ and $ ; Lists, Arrays, Associat'\ ~ Array.' Regular Expressions and
Substitutions, File Handling, File Tests, Subroutines, Forrnatted Printing
Advanced vi: Operators, The ex Mode; Named, Numbered Buffers; Entering
Control Character.' Searching for a Character, Making ~'ext, Customizing vi,
The ·exrc File and EXINIT handling th Terminal, Options to vi. Advan('e(1
Shell Pfl)gramming: The sh Command; export; cd; TI Comniand; expr;
Conditional Parameter Substitution, Merging Streams, ;heli Functions, eval;
exec Statement.
4. NETWORKING, SYSTEM ADMINISTRATION. 12hrs.
TCP/IP Networking: Features of TCP/IP, A TCP/IP Network, MAC and IP
Addresses. The For Layers, Daemons, Ports and Sockets, The IP Addressing
System, Subnets, Routing, telnet; fm~ rlogit rep; rsh; Other Remote Commands;
PPP; The Network File System . The Jnter,net: DL.\'S; Intern'. Accounts; Mail
Service; Newsgroups; irc; Anonymous ftp; archie; gopher; WWW; Connecting to 4
Internet. System Administration I: The Routine Duties: root; The
Administrator's Privilege Operation, Managing Disk Space, find; dd; Handling
DOS Diskettes; Backups; cpio; tar. System Administration II: Partitions, File
Systems, Inoiles, Data Blocks, The Boot Block, The Superblnel The Directory,
How the Kernal Accesses a File, The Standard File Systems, fdisk; Dividing
Partition into File Systems, File System Mounting, Symbolic Links,The File
System Organization 5VR4. System Administration JI!: useradd; letc/passwd and
leteishadowi; usermod and userdel; Umask; Controlling Use of at and cron;
Password Administration, rsh; Allowing a User to Shutdo" Only;
Set-User-ID; Sticky Bit; fsck; Adding a Hard Disk; mount Revisited; mit; Ietclinittab:
When 4 System Doesn't Boot; Shutdown and the s~nc Operation; mit Revisited;
Configuring a Pintcr; lpsta Controlling the Spooler, Configuring the Network
Interface; ping; inetd; Co. figuring Routin: Setting Up PPP for the Internet;
Enforcing Security for rlogin and rep; Setting u~ NIS: Pack~ Strategy; File
System Backup; Maintaining a Table of Contents, Relinking the Kernal; xargs.
Text Book:
1.Surnitabha Das UNIX Concepts and Applications (Second Edition). Tata Mc
Graw Hill, 199S (Chapters 1 to 21, 23 to 26)
Reference Books:
1. Kenneth Rosen et al : UNIX: The Complete Reference, Osborne IMeGraw
Hill, 1999.
2. Steve Moritsugu: Using UNIX (Second Edition), Prentice-Hall India, 1999.
3. Mark, G. Sobel: A Practical Guide to the UNIX System (Third Edition),
Addison-Wesley, 1995.
4. Brian Kernighan~and Rob Pike: The UNIX Programming Environment,
Prentice-Hall India, 1984.
5. Mark, G. Sobel,: A Practical Guide to the Linux, Addison-Wesley, 1992.
Subject Code CS5BI /IS5BI
Duration of Exam :3 Hrs
Subject Title Programming Languages
Max. Exam. Marks 100
Total contact hrs 48
Max. I.A. Marks 25
Contents:
1.
INTRODUCTION
6 Hours
The Role of Programming Languages - Toward higher-level languages, Problems
of scale, Programming paradigms, Language implementation: Bridging the gap,
Language Description: Syntactic structure - Expression notations, Abstract
syntax trees, Lexical syntax.
2. STATEMENTS : STRUCTURED PROGRAMMING
6 Hours
Need for Structured programming, Syntax-Directed control flow, Design
considerations: Syntax, Handling special cases in loops, Programming with
Invariants, Proof rules for partial conrectness, Control flow in C.
3. TYPES : DATA REPRESENTATION
6 Hours
The Role of types, Arrays: Sequences of elements, Records: Named fields,
Unions and variant records, Sets, Pointers: Efficiency and Dynamic
allocation, Two string tables, Types and Error checking.
4.PROCEDURE ACTIVATIONS 6 Hours
Introduction to Procedures, Parameter passing methods, Scope rules for
Naines, Nested scopes in the source text, Activation records, Lexical scope:
Procedures as in C, Lexical scope: Nested procedures and Pascal.
5. OBJECT ORIENTED
PROGRAMMING
6 Hours
Groupings of Data and Operations - Constructs for Program structuring,
Information hiding, Program design with modules, Modules and defmed types,
Class declaration in C++, Dynamic allocation in C++, 'Templates:
Parameterized types, Implementations of Objects in C++. Object-Oriented
Programming - What is an Object ?, Object-oriented thinking, Inheritance,
Object oriented programming in C++, An extended C++ Example, Derived classes
and information hiding.
6. FUNCTIONAL
PRORAMMING 6 Hours
Elements of Functional Programming - A little language of expressions,
Types: Values and operations, Function declarations, Approaches to expression
evaluation, Lexical scope, Type checking, Functional programming in a Typed
Language - Exploring a list, Function declaration by class, Function as
First-class values,ML: Implicit types, Data types, Exception handling in ML,
Little quilt in standard ML.,
7. FUNCTIONAL PROGRAMMING WITH LISP
6
Hours
Scheme, A Dialect of LISP, The structure of lists, List manipulation,
Motivating Example: Differentiation, Storage allocation for lists.
8. LOGIC PROGRAMMING
6
Hours
Computing with relation, Introduction to PROLOG, Data Structures in PROLOG,
Programming techniques, Control in PROLOG, Cuts.
Text Book:
I. Ravi Sethi, Programming Languages, Second Edition, Addison-Wesley, I
996. (chapters l,2.l,2.2,2.3,3,4,5,6,7,8,9, 10,11)
Referenee Book:
2. T W Pratt and M V Zelkowita, Programming Languages Design and
Implementation, Third Edition, Prentice-Hall India 1996.
3. Doris Appleby, Julius J Vandekopple, Programming languages : Paradigm and
Practice, TMH, 1998
Subject Code C55B2 /155B2
Duration of Exam 3 Hrs
Subject Title Optimization Techniques Max.
Exam. Marks :100
Total contact hrs 48
Max. I.A. Marks 25
Contents:
I. INTRODUCTION:
Optimization, Types of problems., Size of problems, Iterative algorithms
and convergence, Linear Programming, Basic properties of linear programs,
Examples of linear programming problems, Basic solutions, The flindamental
theorem of linear programming, Relations to convexity. 6 hours
2. THE SIMPLEX METHOD: Pivots, Adjacent extreme points, Determining
minimum easible solution, Computational procedure-Simplex method, Artificial
variables, Variables with upper bounds, Matrix form of simplex method, The
revised Simplex method. 6 hours 6hours
3. UNCONSTRAINED PROBLEMS: Basic properiies of solutions and Algorithms,
Necessary conditions for local minima, Sufficient conditions for a relative
minimum, Convex and Concave flinctions, Minjrnization and Maximization of
Convex Functions, Global convergence of descent algorithms, Speed of
convergence.6 hours
4. BASIC DESCENT METHODS:
Fibonacci and golden section search, Line search by curve fitting, Global
convergence of curve fitting, Closedaess of line search
algorithrns,Inaccurate line search, The method of steepest descent, Newtons
method, Coordinate descent methods, spacer steps. 6 hours
5. CONJUGATE DIRECTION METHODS:
Conjugate directions, Descent properties of the conjugate direction method,
The conjugate gradient method, Conjugate gradient method as an optimal
process ,The partial conjugate gradient method, Extensions to Non-Quadratic
problems. 6 hours
6. CONSTRAINED MINIMIZATION: Constrained Minimization conditions,
Constraints, Tangent plane, Necessary and sufficient condition (equality
constraints) Eigen values in subtpace, Sensitivity Inequalilty constraints. 6
hours
7 PRIMAL METHODS: Advantages of Primal methods, Feasible direction
methods, Global convergence,The gradient projection method, The redt'ced
gradien' method, Convergence rate of reduced gradient method, Variations.
6 hours
6. PROBABILISTIC METHODS: Games, Strategies, Stable games, Unstable
games, solution by linear programming. Dominance, Decision processes, Naive
decision criteridn, A priori criterion. Aposteriori criterion. Decision trees
Utility,lotteries ,von neumann utilities. 6 hours
Texts Books David G. Luenberger: Introduction to Linear and Non linear
Programming. Addision Wesley Publishing Company, Reading Massachusetts.(2
Edition ) (Chapters 1.1 to 1.4,2.1 to 2.5,3.1 to3.8,6.l to6.7,7.1 to 7.9,8.1
to 8.6, 10.1 to 10.7 11.1 to 11.9)
2. Richard Bronson: Theory and Problems of Operations Research, Schaum's
Outline Series McGraw hill Book Company, Singapore.
Subject Code CS5B3/IS5T3 Duration
of Exams:3 Hrs
Subject Title Object Oriented Systems Development
Max Exams Marks:100
Total Marks:48 Max
I.A.Marks: 25
Contents:
1.INTRODUCTION. 6 hrs.
An Overview of Object Oriented Systems Development; why an Object
Orientation?, Overview of th Unified Approach. Object Basics: Introduction,
An Ohject-Oricnted Philosophy, Objects, Classe' Attributes; Object Behavior
and Methods, Encapsulation and Information Hiding, Class Hierarch~
Polymorphism, Object Relationships and Associations, Aggregations and Object
Containment, Cas Study: A Payroll Program. Advanced Topics. Object-Oriented Systems
Development Life Cyclc Introduction, The Software Development Process,
Building High-Quality Software, Object-Oriente Systems Development: A
Use-Case Driven Approach, Reusability.
2.METHODOLOGY, MODELING AND UML. 6 hrs.
Object Oriented Methodologies; Introduction: Survey ofSome of the
Object-Oriented Methodologiet ambaugh Object Modeling Technique, The Booch
Methodology, The Jacobson et a ivlethodologies, Patterns, Frameworks, The
Unified Approach. Unified Modeling language Introduction, Static and Dynamic
Models, Why Modeling, Introduction to the Unified Modelin Language, UML
Diagrams, UML Class Diagram, Use-Case Diagram, UML Dynamic Modeling Model
Management: Packages and MO(lel Organization, UMI Ixtensibitity, I JNil
Meta-Model.
3. OBJECT ORIENTED ANALYSIS. 12 hrs.
Object Oriented Analysis Process-Identifying Use Cases: Introductioti,
I3usiness Object Analysis Understanding the l3usin'ess Layer, Use-Case Driven
Object-Oriented Analysis: The Unified Apprach.Business Process Modeling,
Use-Case Model, Developing L.ffective Docuntentation, Case Studv ViaNet Bank
ATM. Object Analysis-Classification: Introdnetion, Classifications Theory,
Approache.' for Identifying Classes, Noun Phrase Approach, Comnton Class
Patterns Approach, Use-(:ase Driver Approach-Identifying Classes and Their
Behaviors through Sequence/Collaboration Modeling Classes, Responsibilities,
and Collaborators, Naming Classes. Identifying Object Relationships
Attributes, and Methods: Introduction, Associations, Super-Sub Class
Relationships, A-Parr-o: Relationships-Aggregation, Case Study. Class
Responsibility: ldentify Log Atttribu tes and Methods Class Responsibility:
Def~tning Attribu~tes by Arialyzing Use Cases artd other UML Diagrans.
Defit~tn, Attribtttes ~)r ViaNet Bank Objects, Obiect Responsibility: Methods
and Messages ,Definig Methods for Via Net Bank Objects.
4. OBJECT-ORIENTED DESIGN I2Hrs. |
The Object-Oriented Design Process and Design Axioms: Introduction,
Object-Oriented Design Process, Object-Oriented Design Axioms, Corollaries,
Design Patterns. Designing Classes: Introduction, The Object-Oriented Design
Philosophy, UML Object Constraint Language, Designing Classes: The Process,
Class Visibility: Design: Well-Defined Public, Private and Protected
Protocols, Designing Classes: Refining Attributes, Refining Attributes for
tlte ViaNet Bank Objects, Designing Methods and protocols, Designing Methods
for the ViaNet Bank Objects, Packages and Managing Classes. Acces~
Layer-Object Storage and Object Interoperabity: Introduction, Object Store
and Persistence: Database Management Systems , Organization and Access
Control, Distributed Databases and Client-Server Computing, Distributed objec
ts Computing Object-Oriented Databjse Management Systems, Object-Relational
Systems, Multidatabase Systems, Designing Access Layer Classes, Case Study:
Designing the Access Layer for the ViaNet Bank ATM. View LayerDesigning
Interface Objects: Introduction, User Interface Design as a Creative Process,
Designing View Layer Classes, Macro-Level Process: Identifying View Classes
by Analyzing Use Cases, Micro-Level Process, The Purpose of a View Layer
Interface, prototyping the User Interface, Case Study.
5. DESIGNING WITH PATTERNS
12Hrs.
GRASP-Patterns for Assigning Responsibilities: Introduction, Activities
and Dependencies, Well- Designed Interaction Diagrams are Valuable,
Responsibilities and Methods, Responsibilities and Interaction Diagrams,
Patterns, GRASP: Patterns of General Principles in Assigning
Responsibilities, The UML Class Diagram Notation, Expert, Creator, Low
Coupling, High Cohesion, Controller, Responsibilities, Role Playing and CRC
Cards. More Patterns and Designing With Patterns: GRASP: General
Responsibility Assignment Software Patterns, Polymorphism, Pure Fabrication,
Indirection, Don't Talk to Strangers, State(GoF), Polymorphism(GRASP),
Singleton(GoF), Remote Proxy and Proxy(GOF), Fa~ade and Device Proxy(GOF),
Corrtmand(GOF). Development Process Issues: Introduction, Why? Guiding
Principles of a Successful Process, Interactive and Incremental Development,
Use case Driven Development, Early Emphasis on Architecture, Phases of
Development, Length of Development Cycles, Development Cycle Issues,
Scheduling Development of Architectural Layers.
Text Books:
I. All Bahrami: Object Oriented Svste,ns Development. McGrawHill,1999
(Chapters 1to 12)
2. Craig Larman,: Applying UAIL and Patterns, An 1ntroduction to
Object-Oriented Analysis and Design, Addison-Wesley, 1998(Chapters 18, 34,
3S, 37)
Reference Books:
1. Rebecca Wirfs- Brock et al: Designing Object Orien ted Software,
Prentice-Hall India, 1990.
2. Grady Booch el al: Un fied Modeling Language User Guide, Addison- Wesley,
1999.
3. Gamma,E. et al: Design Patterns: Elements of Reusable Object-Oriented
Software, Wesley, 1995.
4. Marlin. J., and Odell, J: Object-Oriented Methods: A Foundation,
Prentice-Hall, 1995.
Duration
of Exam 3 Hrs
Subject Code :CS5Cl/155C1
Max. Exam. Marks :100
Subject
Title Numerical Algorithms
Max. l.A. Marks 25
Total contact hrs 48
Contents:
1. REVIEW: Approximations and errors, Roots of equations, Simultaneous
equations.
3 hrs.
2. CURVE FITTINGS:
6 Hrs
Linear Regression, Polynomial Regression, Multiple Linear Regression, General
Linear Least squares. Nonlinear Regression.
3. INTERPOLATION:
6 Hrs
Newton's Divided-Difference Interpolating Polynomials, Langrange
Interpolating Polynomials, Coefficients of an Interpolating PolynoLnials,
lnve~'' Interpolation, Additional Comments, Spline Interpolation.
4.
OPTIMIZATION:
15 Hrs
Motivation, Golden-Section Search, Quadratic Interpolation, Newton's Method,
Linear Programming, Nonlinear Constrained Optimization, Optimization with
Packages..
5. INTEGRATION:
12
Hrs.
The Trapezoidal Rule, Simpson's Rules, Integration with Unequal Segments,
Open Integration Fomiulas, Newton-Cotes Algorithms for Equations, Romberg
Integration, Gauss quadrature, Improper Integrals.
6. FINITE ELEMENT METHODS:
6
Hrs.
The General Approach, Finite Element Application in One Dimension, Two
Dimensional Problems, PDEs with Libraries and Packages.
Text Book:
1. Steven C Chapra & Raymond P.Canale, Numerical Methods for Engineers,
3rd Edition ,WCB/ McGraw-Hill International Edition, 1998. (Chapters No.
3,17,18, PT 4.1,13,15.1-15.3,2 1,22,31)
Reference Books:
1. Curtis. F. Gerald, Patrick. O.Wheatley ,App lied Numerical Analysis, , 5th
Edition, Addition Wes Icy. 1998.
2. Samuel.D~onte'Carl De.Boor, Elementary Numerical Analysis- An Algorithmic
Approach, 3rd Editi' McGraw Hill International Edition, 1981
Subject Code : C55C2 / 1S5C2 Subject
Title: Fuzzy Logic
Total contact hrs 48
Duration of Exam :3hrs
Max. Exam. Marks
:100 Max.
1.A. Marks 25
Contents:
I. INTRODUCTION :
Uncertainty and Imprecision, Static and random processes, Uncertainty in
inforruation, Fuzzy sets and classical sets, properties, mapping of classical
sets to function, Fuzz set operation, properties, sets as points in
Hypercubes. 6 hour
2. Cartesian product, crisp relations, Fuzzy relations, Tolerance and
equivalence relations, Fuzzy tolerance, value assignments. 6 hours
3. Membership functions, Features of membership functions standard
forms and boundaries, Fuzzificati.)n, membership value assignment. 6 hours
4. Fuzzy to crisp conversions, Lambda cuts for fuzzy sets, Lambda cuts
for fuzzy relations, Deflizzification methods, extension principle, crisp
function, mapping and relations, practical considerations, Fuzzy numbers,
interval analysis in arithmetic, approximate methods of extensic Fuzzy
vectors. 12 hours
5. Classical logic and Fuzzy logic, predicate logic, Fuzzy logic, approximate
reasoning, Fuzzy tautologies, contradiction, equivalence and logical proofs.6hours
6. Fuzzy rule based-systems, natural language, linguistic hedges, Rule
based systems, canonical ru forms, Decomposition of compound rules,
likelihood and truth qualification, aggression of Fuzz rules, graphical
techniques. 6 hours
7. Fuzzy classification by equivalence relations, crisp relations,
Fuzzy relations cluster analysis, cluster validity, C-mean clustering, HCM,
LCM, Classification metric, Hardening the fuzzy C- partition, Similarity
relations from clustering. 6 hours
Text Book:
I. Timothy. J. Ross, Fuzzy logic with engineering applications, McGiaw HLII
Inteniational edition 1997. (Chapters 1,2,3,4,5,6,7,8, II)
Reference Book:
I. B; Kosko, Neural networks and Fuzzy systems A dynamical system approach
Prentice Hall, 1991.
Subject Code CS5C3 /1S5C3 Duration
of Exam 3 Hrs
Subject Title Internet & Intranets Max.
Exam. Marks :100
Total contact hrs 48
Max.
I.A. Marks 25
Contents
1.INTERNET STRUCTURE, PROTOCOLS, AND ACCESS WITH AN EYE TO INTRANETS
12Hrs.
Overview; Internet Protocol Model Overview; Internet Addresses; Internet
Protocol: Basis for Internet and Intranets; Transport Layer; Uppe'r-Layer
Protocols; Internet Access; Internet Applications; Future of the Internet and
Internet-Related Applications. Router Technology: Introduction; Network
Fundamentals (051 Layers); Internet Routing; New Developments; Router Market.
2. INTERNET AND INTRANET WEB SERVER TECHNOLOGY, ACCESS AND PROTOCOLS AND
HTML TECHNOLOGY, APPLICATIONS. 12Hrs.
Introduction; Overview of Hyper Text Markup Language (HTML); Overview of
Hyper Text Transfer Protocol (HTTP); Web Servers; Web Access; Security;
Related Web Capabilities; World Wide Web Proxies; Future of the Web. HTML
Technology, Applications, and Examples: Introduction; The Nuts and Bolts of
HTML; Tools and Guides; Practical Consideration for Internet and/ or Intranet
Pages; Beyond HTML.
3. BROWSERS; BUILDING A CORPORATE WEB SITE 12Hrs
Browsing Systems for the Web, the Internet, and Intranets: Browser Features
and Capabilities; Netscape; Using Browsers for Commercial Gain. Building a
web site: Background; Getting Connected; Elements of a Web Service; Security
Issues; Management Issues related to Web Server Set Up; Novell's WWW Service
Alternative; Extensions and Applications on the Web; Legal and Ethical
Issues.
4. ON LINE SERVICES; BROADBAND COMMUNICATIONS; VIRTULA REALITY
APPLICATIONS. 12Hrs.
On- Line Services.. Technology, Applications and Vendors: Overview;
Definitions of C line Services; History of On-line Services; The On-line
Services Market: Trends; On-line Services Industry Makeup; Technology Trends.
Broadband Communication: Services and Requirements Driving the Need for Broadband;
Network Architecture Supporting Broadband; Broadband Carrier Services for
Intranets and for the Internet; Example of Broadband-based Application: Web
TV. Virtual Reality Technology: A Synopsis; Evolving Virtual Reality
Applications; Opportunities of Corporate Education and Training.
Opportunities for Marketing and Business Applications.
Text Books:
1. Daniel Minoli : Internet and Intranet Engineering, Tata McGraw Hill, 1997.
(Chapters 1,2,3,4,5.1 to 5.3,5.7,6,7.1 to 7.6,8, 9)
Reference Books:
1. Margaret Levine Young: Internet: The Complete Reference, Tata McGraw Hill,
1999.
2. Ed Tittel : The Intranet Bible, IDG Books Worldwide, 1997.
3. Bernard Ryan: The Corporate Intranet, (Second Edition), John Wiley, 1997.
4. Mellanle Hills: Intranets Business Strategies John Wiley, 1997.
Subject Code C55C4/155C4
Duration of Exam :3 Hrs
Subject Title Signals &
Systems Max. Exam. Marks :100
Total contact hrs 48
Max. I.A. Marks 25
Contents:
1. Basic concepts, mathematical modeling, continuous and discrete time
signals and systems, continuous-time functions, discrete time functions,
Review of complex variables and matrices. 8 hours
2. Definition of a signal, interconnection of signals, time scaling,
time shifting and lin.its of signals, signals dcfined on intervals, digital
wavefonn~, message signals, TDM.
8 hours
3. Definition of a system, system representations, electrical
networks, Fourier series and Fourier transforms, 8 hours
4. Amplitude and phase spectra, energy and power signals, energy spectral
density, power spectral density. Power calculations for periodic signals.
Spectral content of a signal. 8 hours
5 The convolution representation, graphical convolution, convolution
integral ----
2 hours
6. Introduction to discrete - time signals, sampling, coding,
quantization. DIA converters, Discrete time systems, Digital filters. 6
hours
7. Z-transforms and Discrete - time fourier transforms. Fourier transform
of a sampled signal, Reconstruction of signals from their samples, aliasing
and Nyquist sampling theorem, ZOH. 8 hours
Text Book:
1. Douglas K. Lindner, Introduction to signals and systems, N'~cGraw Ilill
international edition 1999. (Chapters 1.1k) 1.5,2.1 k)2.3,3.l to 3.2,4.1
to4.2,5.1 to 5.6,6.1 to6.3,7.l to 7.5,8.1 to 8.6, 12.1 to 12.3, 17.1 to 17.6,
18.1 to 18.4,19.1 to 19.5)
Reference Book
1. Simon Haykin and Barry Van Veen, Signals and Systems, John Wiley, 1999.
Subject Code:IS5T4 Duration
of Exam:3hrs
Subject Title: File
Structures Max.Exam.Marks:100
Total contact hrs:48
Max.I.A.Marks:25
Contents:
1.INTRODUCTION:
File Strutures: The Heart of the file structure Desgin,A short histroy of
files strutures Desgin,A Conceptual Toolkit;Fundamental file
organisations:Physical files and Logical files ,opening files,closing files,
reading and writing,seeking ,specaila characters,The Unix irectory
structures, Physical and Logical Files in UNIX, File-related Header Files,
UNIX file System Commands. Seconda7y Storage and System Software: Disks,
Magnetic Tape, Disk versus Tape, CD-ROM: Introduction, Physical Organization,
Strengths and Weaknesses; Storage as Hierarchy, A journey of a Byte, Buffer
Management, Input /Output in UNIX.
2.FUNDAMENTAL FILE STRUCTURE CONCEPTS, MANAGING FILES OF RECORDS
6 Hrs.
Field and Record Organization, Using Classes to Manipulate Buffers, Using
Inheritance for Record Buffer Classes, Managing Fixed Length, Fixed Field
Buffers, An Objc~tOricntcd Class for Record Files, Record Access, More about
Record Structures, Encapsulating Record Operations in a Single Class, File
Access and File Organization, Beyond record structures.
3.ORGANIZATION OF FILES FOR PERFORMANCE, INDEXING: 6 Hrs.
Data Compression, Reclaiming
Space in files, Internal Sorting and Binary Searching, Keysorting; What is an
Index? A Simple Index for Entry-Sequenced File, Template Classes in C++,
Object- Oriented support for Indexed, Entry-Sequenced Files of Data Objects,
Indexes that are too large to hold in Memory, Indexing to provide access by
Multiple keys, Retrieval Using Combinations of Secondary Keys, Improving the
Secondary Index structure, Inverted Lists, Selective indexes, Binding.
4. COSEQUENTIAL PROCESSING AND THE SORTING OF LARGE FILES:
6 Hrs.
A Model for Implementing Cosequential Processes, Application of the Model to
a General Ledger Program, Extension of the Model to include Mutiway Merging,
A Second Look at Sorting in Memory, Merging as a Way of Sorting Large Files
on Disk, Sorting Files on Tape, Sort-Merge packages, Sorting and Cosequential
Processing in UNIX.
5. MULTI-LEVEL INDEXING AND B-TREES:
6 Hrs.
Introduction; Indexing with Binary Search Trees; Multi-Level Indexing;
B-Trees; Example of Creating a B-Tree, An Object-Oriented Representation of
B-Trees, B-Tree Methods; Nomenclature, Formal Definition of B-Tree
Properties, Worst-case Search Depth, Deletion, Merging and Redistribution
during insertion; A Way to improve storage utilization, B* Trees, Buffering
of pages; Virtual B-Trees; Variable-length Records and keys.
6. INDEXED SEQUENTIAL FILE ACCESS AND PREFIX B +TREES
6
Hrs.
Indexed Sequential Access, Maintaining a Sequence Set, Adding a Simple Index to
the Sequence Set, The Content of the Index: Separators Instead of Keys, The
Simple Prefix B+ Tree and its maintenance, Index Set Block Size, Internal
Structure of Index Set Blocks: A Variable-order B- Tree, Loading a Simple
Prefix B+ Trees, B+ Trees, B+ Trees and Simple Prefix B+ Trees in
Perspective.
7. HASHING 6 Hrs.
Introduction, A Simple Hashing Algorithm, Hashing Functions and Record
Distribution, How much Extra Memory should be used?, Collision resolution by
progressive overflow, Buckets, Making deletions, Other collision resolution
techniques, Patterns of record access.
8. EXTENDIBLE HASHING, CD-ROM FILE
STRUCTURES:
6 Hrs.
How Extendible Hashing Works, Implementation, Deletion, Extendible Hashing
Performance, Alternative Approaches. File Structures on CD-ROM, Tree
Structures on CD-ROM, Hashed Files on CD-ROM, The CD-ROM File System.
Text Books:
1. Michael J. Folk, et al: File Structures-An Object Oriented Approach with
C++(Third Edition), Addison-Wesley, 1998.(Chapters 1 to 12, Appendix A)
Reference Books:
1. Cormen, T.H. et al: Introduction to Algorithms, Prentice-Hall India,1998.
2. Scot Robert Ladd: C++ Components and Algorithms, BPB Publications, 1993.
3. Raghu Ramakrishan and Johannes Gehrke: Database Management
Edition),McGraw Hill,2000.
4. Loomis: Data Management and File Structures(Second Edition), Prentice-Hall
India, 1989.
Subject Code:IS5L6 Duration
of Exam:3hrs
Subject Title:Unix Programming
Laboratory Max.Exam.Marks:100
Max.I.A. Marks:25
Contents:
Pragrams illustrating the use of shell and system calls and libray
functions are to be developed and executed in UNIX environment .Typical
programs would include awk programs(flod long into 80 columns;calendar sevice
etc),Bourne shell scripts( calender service;finding which cmd in path is
executed;find links to a file specified as an argument;find information about
users given their ids etc) Korn shell scripts (write last component of
pathname argument;given a directory name,write maximum of lengths of files in
that directory; shell function to list nuber of regular files ,directories
etc ,rewrite makepaths as a non-recursive function etc)C programs to make use
of system calls(use of low-level file I/O operations,create and kill child
processes).
|