IInd YEAR Ist SEMISTER

2007-10-16T07:41:00.000-07:00

Syllabus of Andhra University

MCA - MCA 2.1.1 Theory of Computation
With effect from 2004-05 admitted batch

Instruction: 3 Periods/week
Sessional Marks: 50

Univ-Exam-Marks:100
Time: 3 Hours

1. Introduction To Finite Automata : Alphabets and languages

- Finite Representation of Languages. Deterministic Finite

Automata – Non- deterministic Finite Automata – Equivalence

of Deterministic and Non-Finite Automata – Properties of the

Languages Accepted by Finite Automata – Finite Automata

and Regular Expressions – Proofs those Languages Are and

Are Not Regular.

2. Context free languages: Context –Free Grammar – Regular

Languages and Context-FreeGrammar – Pushdown Automata

– Pushdown Automata and Context-Free Grammar – Properties

of Context-Free Languages – Closure Properties – Periodicity

Properties – Determinism and Parsing – Deterministic Pushdown

Automata and Context – Free Languages – Top- down Parsing–

Bottom – Up parsing.

3. Turing machines: The Definition of Turing Machine – Computing

with Turing Machines –Combining Turing Machines – some Examples

of More Powerful Turing Machines.

. Church’ Thesis : Church’s Thesis – The Primitive Recursive functions

– Godelization – Them-Recursive Functions – Turing – Computability

of the m-Recursive functions – Universal Turing Machines.

5. Uncomputability: The Halting Problem – Turing-Enumerability,

Turing –Acceptability, and Turing - Decidability – Unsolved problems

about Turing machines and m-Recursive Functions - Post’s

correspondence problem.

6. Computational complexity: Time-bounded Turing Machines –

Rate of Growth offunctions – Time-Bounded simulations – The

Classes P and NP – NP-Completeness –Some NP-complete Problems

– Integer Programming – The Traveling SalesmanProblem.

7. The Prepositional Calculus : Introduction – Syntax of the

Prepositional Calculus –Truth-Assignments – Validity and

Satisfiability – Equivalence and Normal Forms –resolution

in Prepositional Calculus.

8. The predicate calculus: Syntax of the Predicate Calculate

Calculus – Structures and Satisfiability – Equivalence –

Unsolvability and NP-Completeness- Resolution in the Predicate Calculus.

Text Book:

Elemets Of The Theory Of Computation, Harry R Lewis,

Cristos h. Papadimitriou, Pearson Education / Prentice-

Hall of India Private Limited.

Reference:

Introduction to Automata Theory, Languages, and Computation,

Hopcroft. J.E and J.D.Ullman. Addison-Wesley, Reading, Mass. 1979.

Syllabus of Andhra University

MCA - MCA 2.1.2 Computer Graphics
With effect from 2004-05 admitted batch

Instruction: 3 Periods/week
Sessional Marks: 50

Univ-Exam-Marks:100
Time: 3 Hours

Introduction: Usage of Graphics and their applications,

Presentation Graphics-Computer Aided Design-

Computer Art- Entertainment- Education and

Training-Visualization- Image Processing- Graphical

User Interfaces

Over view of Graphics systems: Video Display Devices-

Raster Scan systems-randomscan systems-Graphics

monitors and workstations-Input devices-hard copy

devices-Graphics software

Output primitives: Points and Lines- Line Drawing

Algorithms- Loading the Framebuffer- Line function

- Circle- Generating Algorithms- Ellipse Generating

Algorithms-Other Curves- Parallel Curve Algorithms-

Curve Functions -Pixel Addressing- Filled AreaPrimitives

-Filled Area Functions- Cell Array- Character Generation

Attributes of Output Primitives: Line and Curve Attributes

-Color and Gray scalelevels- Area Fill Attributes- Character

Attributes-Bundled Attributes- Inquiry Functions -Antialiasing

Two Dimensional Geometric Transformations: Basic

Transformations- MatrixRepresentations-Homogeneous

Coordinates-Composite Transformations-Other

Transformations-Transformations between Coordinate

Systems- Affine Transformations -Transformation

Functions- Raster methods for Transformations

Two Dimensional Viewing: The viewing Pipeline-Viewing

Coordinate ReferenceFrame-Window-to-Viewport Coordinate

Transformation-Two Dimensional Viewing Functions -

Clipping Operations-Point Clipping-Line Clipping-Polygon

Clipping-CurveClipping- Text and Exterior Clipping

Structure And Hierarchical Modeling: Concepts of Structures

and Basic models-Editing - Hierarchical Modeling with

Structures-GUI and Interactive Input Methods-Windows

and Icons- Virtual Reality Environments

Three Dimensional Concepts and Object representations:

3D display methods-3DGraphics-Polygon Surfaces- Curved

Lines and Surfaces- Quadratic Surfaces-Super Quadrics-Blobby

Objects-Spline Representations - Cubic Spline methods-Bezier

Curvesand Surfaces- B Spline Curves and Surfaces

Three Dimensional Geometric and Modeling Transformations:

Translation-Rotation-scaling-Other Transformations-Composite

Transformations -3D TransformationFunctions -Modeling

and Coordinate Transformations

Three Dimensional Viewing: Viewing Pipeline- Viewing

Coordinates- Projections -View Volumes- General Projection

Transformations-Clipping-HardwareImplementations-

Three Dimensional Viewing

Text Book:

1) Computer Graphics C Version, Donald Hearn &

M. Pauline Baker , Pearson Education, New Delhi, 2004

(Chapters 1 to 12 except 10-9 to 10-22)

Reference Books:

1) Procedural Elements for Computer Graphics, David

F. Rogers, Tata McGraw Hill Book Company, New Delhi, 2003

2) Computer Graphics: Principles & Practice in C, J. D.

Foley, S. K Feiner, A Van Dam F. H John Pearson Education, 2004

3) Computer Graphics using Open GL, Franscis S Hill

Jr, Pearson Education, 2004.

Syllabus of Andhra University MCA - MCA 2.1.3 File Structures
With effect from 2004-05 admitted batch

Instruction: 3 Periods/week
Sessional Marks: 50

Univ-Exam-Marks:100
Time: 3 Hours

File Processing Operations

Physical and logical files, opening, reading & writing and closing files in C, seeking and special characters in files, physical devices and logical files, file -related header files in C

Secondary Storage

Disks – organization, tracks, sectors, blocks, capacity, non-data overhead, cost of a disk access, Magnetic Tape – types, performance, organization estimation of tape length and data transmissiontimes, disk vs tape, CD-ROM – CD-ROM as a file structure, physical organization, strengths and weakness of CD -ROMS, storage hierarchy

Byte Journey and buffer Management

File manager, I/O buffer, I/O processing, buffer strategies and bottlenecks

File Structure Concepts

A stream file, field structures, reading a stream of fields, record structures and that uses a length indicator, Mixing numbers and characters – use of a hex dump, reading the variable lengthrecords from the files

Managing records in C files

Retrieving records by keys, sequential search, direct access, choosing a record structure andrecord length, header records, file access and file organization

Organizing files for performance

Data compression, reclaiming space – record deletion and storage compaction, deleting fixed length records for reclaiming space dynamically, deleting variable-length records, spacefragmentation, replacement strategies.

Indexing

Index, A simple index with an entry sequenced file, basic operations on an indexed, entry sequenced file, indexes that are too large to hold in memory, indexing to provide access by multiple keys, retrieval using combination of secondary keys, improving the secondary indexstructure – inverted lists

Indexed sequential file access and prefix B + Trees

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, simple prefix B+tree maintenance, index set block size, internal set block size, internal structure of index setblocks: a variable order B-tree, loading a simple prefix B+ tree

Hashing

Collisions in hashing, a simple hashing algorithms, hashing functions and record distributions, memory requirements, collision resolution by progressive overflow, buckets, deletions

Extendable hashing

Working of extendable hashing, implementation, deletion, extendable hashing performance

Designing file structure for CD-ROM

Tree structure on CD -ROM, hashing files on CD-ROM, CD-ROM file structure

Implementation in C++

Text Book:

File Structures – An Object Oriented Approach with C++, Michael J. Folk, Bill Zoellick and Greg Riccardi, Pearson Education

Syllabus of Andhra University MCA - MCA 2.1.4 Design and Analysis of Algorithms
With effect from 2004-05 admitted batch

Instruction: 3 Periods/week
Sessional Marks: 50

Univ-Exam-Marks:100
Time: 3 Hours

1. Introduction:- Notion of Algorithm – Algorithmic Problem solving ( 1.1, 1.2)

2. Analysis of Algorithm Efficiency:- Analysis framework – Asymptotic notations – Analysis of Non-recursive and recursive algorithms (2.1,2.4)

3. Divide and Conquer:- Merge sort – Quick Sort – Binary search – Large integer Multiplication and Strassens Matrix multiplication-closest pair and convex Hull problems ( 4.1 to 4.3,4.5 to 4.6)

4. Decrease and conquer: - DFS and BFS, Topological sorting, Decrease – by – a – Constant - factor Algorithms, variable – size – Decrease Algorithms- (5.2, 5.3, 5.5, 5.6)

5. Transform and conquer:- Horner’s Rule and Binary Exponentiation – Problem Reduction – (6.5, 6.6)

6. Space and Time Tradeoffs:- Input Enhancement in String Matching (7.2)

7. Dynamic Programming:- Warshall’s and Floyd’s Algorithm – Optional Binary Search Trees – knapsack Problem (8.2 to 8.4)

8. Greedy Technique:- Prim’s and kruskal’s Algorithms, Dijkstra’s Algorithm, Huffman Trees (9.1 to 9.4)

9. Limitations of Algorithm Power:- Lower Bound Arguments – Decision Trees – P,NP and NP Complete problems (10.1 to 10.3)

10. Coping with limitations of Algorithmic Power:- Backtracking, Branch and Bound, Approximation Algorithms for NP – hard problems ( 11.1 to 11.3)

Text Book:

Introduction to the design and analysis of Algorithms, Anany Levitin : Pearson Education, 2003.

Reference Books :

1. Fundamentals of Computer Algorithms,Horowitz and Sahni, Galgothia publications.

2. Introduction to Algorithms,Cormen, Leiserson and Rivest : Prentice Hall of India

Syllabus of Andhra University MCA - MCA 2.1.5 Operating Systems
With effect from 2004-05 admitted batch

Instruction: 3 Periods/week
Sessional Marks: 50

Univ-Exam-Marks:100
Time: 3 Hours

Overview

Introduction, Computer System structures, Operating systems structures

Process Management

Processes, Threads, CPU scheduling, Process synchronization , Deadlocks

Storage Management

Memory management, Virtual memory, file system, I/O systems, Mass – storage structure

Protection and Security

Protection and Security

Text Book:

Applied Operating System Concepts, Avi Silberschatz, Peter Galvin, Grey Gagne

Syllabus of Andhra University MCA - MCA 2.1.6 Operating Systems Lab
With effect from 2004-05 admitted batch

Instruction: 3 Periods/week
Sessional Marks: 50

Univ-Exam-Marks:100
Time: 3 Hours

1. Study of laboratory environment:
Hardware specifications, software specifications

2. Simple Unix-C programs:
Programs using system calls, library function calls to display and write strings on standard output device and files.

3. Programs using fork system calls.

2. Programs for error reporting using errno, perror( ) function.

3. Programs using pipes.

4. Shell programming.

5. Programs to simulate process scheduling like FCFS, Shortest Job First and Round Robin.

6. Programs to simulate page replacement algorithms like FIFO, Optimal and LRU.

7. Programs to simulate free space management.

8. Programs to simulate virtual memory.

10. Programs to simulate deadlock detection.

References:

1. Unix Systems Programming : Communication, Concurrency and Threads, Kay Robbins, 2-Edition, Pearson Education

2. Unix concepts and applications, Sumitabha Das, TMH Publications.

3. Unix programming, Stevens, Pearson Education.

4. Shell programming, Yashwanth Kanetkar.

5. Operating System Concepts, Silberschatz, and Peter Galvin.

Syllabus of Andhra University MCA - MCA 2.1.7 File Structures Lab
With effect from 2004-05 admitted batch

Instruction: 3 Periods/week
Sessional Marks: 50

Univ-Exam-Marks:100
Time: 3 Hours

1. File Operations:

Opening, reading, writing, closing and creating of files in C++

2. Study of secondary storage devices:

Tracks, sectors, block capacity of disk, tape and CDROMs

3. File Structures in C++

Reading a stream of fields, record structures and its length indicators, Mixing of numbers and characters, Use of a hex dump, Retrieving records by keys using sequential search, direct access

4. File performance

Data compression, storage compacting, reclaiming space dynamically

5. Indexing and indexed sequential files

Index file, inverted file operations, usage of B and B++ trees

6. Hashing files

Hashing functions, algorithms, record distribution and collision resolution by progressive over flow, Extendable hashing and hashing performance

MCA SYLLABUS

IInd YEAR Ist SEMISTER