Title
Analysis And Design Of Algorithms
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.
Back
To Top
System
Software
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.
Back
To Top
Operating
Systems
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.
Back
To Top
Computer
Graphics
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
Back
To Top
Algorithms
Lab
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.
Back
To Top
Advanced
Data Structure Using
C++
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.
Back
To Top
Data
compression Techniques
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
and applications, Prentice Hall Intl. 1995.
2 Raghuveer M. Rao, Wave let transforms : Introduction to theory and
applications, Addison Wesley pub. Co. ltd, 1998.
Back
To Top
Software
Practice and Testing
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.
Back
To Top
Introduction
to UNIX
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. file system 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 permissions, chmod simple filters :
the sample data base,pr;head; tail; cut ,apste sort uniq; nl ;tr.Regular
Expression 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.
Back
To Top
Programming
Languages
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
Back
To Top
Optimization
Techniques
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
8. 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.
Back
To Top
Object
Oriented Systems Development
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.
Back
To Top
Numerical
Algorithms
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
Back
To Top
Fuzzy
Logic
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.
Back
To Top
Internet
& Intranets
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.
Back
To Top
Signals
& Systems
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.
Back
To Top
File
Structures
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.
Back
To Top
Unix Programming
Laboratory
Subject Code:IS5L6 Duration
of Exam:3hrs
Subject Title: Unix Programming Laboratory Max.Exam.Marks:100
Max.I.A. Marks:25
Contents:
Programs illustrating the use of shell and system calls and library
functions are to be developed and executed in UNIX environment .Typical
programs would include awk programs (flod long into 80 columns; calendar
service etc), Bourne shell scripts( calendar 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 number of regular
files ,directories etc ,rewrite make paths 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).
Back
To Top
