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
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
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
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
. 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,
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 –
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
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
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,
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,
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,
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-
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
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
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
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
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
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:
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:
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
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 &
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
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.
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
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
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
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.
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
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
