THIRUVALLUVAR UNIVERSITY

[Link] / Ph.D Entrance Examination SYLLABUS

COMPUTER SCIENCE
UNIT I
Computer Organization and Architecture
Basic of Computer, Von Neumann Architecture, Generation of Computer, Classification of
Computers, Instruction Execution. Register Transfer, Bus and Memory Transfers, Three-
State Bus Buffers, Memory Transfer, Micro-Operations, Register Transfer Micro-Operations,
Arithmetic Micro-Operations, Logic Micro-Operations, Shift Micro-Operations. Stack
Organization, Register Stack, Memory Stack, Reverse Polish Notation.
Instruction Formats, Three- Address Instructions, Two – Address Instructions, One - Address
Instructions, Zero - Address Instructions, RISC Instructions, Addressing Modes. RISC &
CISC. Addition And Subtraction With Signed-Magnitude, Multiplication Algorithm, Booth
Multiplication Algorithm, Array Multiplier, Division Algorithm, Hardware Algorithm,
Divide Overflow, Floating-Point Arithmetic Operations, Decimal Arithmetic Operations,
BCD Adder, BCD Subtraction. Modes Of Transfer, Priority Interrupt, DMA, Input-Output
Processor (IOP), CPU-IOP Communication. Memory Organization: Memory Hierarchy,
Main Memory, Auxiliary Memory, Cache Memory, Virtual Memory, Associative Memory.
Control memory – Address sequencing.
UNIT II
Digital Logic and Fundamentals
Number Systems and Codes: Number System – Base Conversion – Binary Codes – Code
Conversion. Logic Gates – Truth Tables – Universal Gates. Boolean Algebra – Simplification
of Boolean Functions – Using Theorems, K-Map – Binary Arithmetic: Binary Addition –
Subtraction – Adder – Subtractor. Combinational Logic: Multiplexers – Demultiplexers –
Decoders – Encoders. Sequential Logic: RS, JK, D, and T Flip-Flops – Master-Slave Flip-
Flops. Registers: Shift Registers – Types of Shift Registers. Counters: Asynchronous and
Synchronous Counters - Ripple, Mod, Up-Down Counters– Ring Counters. Memory: Basic
Terms and Ideas –Types of ROMs – Types of RAMs.
UNIT III
Data Structures and Algorithms
Introduction of algorithms - analyzing algorithms, Arrays, Stacks and queues, Application of
Stack: Evaluation of Expression - Infix to postfix Conversion - Sparse Matrices. Linked list :
Singly Linked list - polynomial addition - Doubly linked List and Dynamic Storage
Management - Garbage collection and compaction. Trees - Binary trees - Traversal -
Threaded Binary trees, Graphs: - Traversals, connected components and spanning Trees,
Single Source Shortest path problem - Hash Tables - Hashing Functions. External sorting :
Storage Devices- K-way merging - sorting with tapes. Internal sorting : Insertion sort - Quick
sort - 2 way Merge sort - Heap sort - shell sort - sorting on keys. Files: Files, Queries and
sequential organizations - Index Techniques - File organization.

1
Design and Analysis of Algorithms
Algorithm Definition – Algorithm Specification – Performance Analysis-Asymptotic
Notations. Elementary Data Structures: Stacks and Queues – Trees – Dictionaries – Priority
Queues – Sets and Disjoint Set Union – Graphs - Divide and Conquer - The Greedy Method -
Dynamic Programming - Backtracking
UNIT IV
Database Management Systems
Introduction: Database System Applications-DBMS Vs. File System - View of Data-Data
Model Database Languages - Database users and Administrators - Database System
Structure. Data Models: Basic Concepts - Constraint- Keys- ER Diagram - Weak Entity -
Extended ER Features - UML; Relational Model: Structure of Relational Databases -
Relational Algebra - Set Operation-Aggregate Function-Null Values-Nested Sub Queries -
Views - Modification of the Database - Data Definition Language - Embedded SQL -
Dynamic SQL. Advance SQL : Integrity and Security: Domain - Constraint - Referential
Integrity - assertions - Triggers - Security and Authorization. Relational Database Design:
First Normal Form - Pitfalls in Relational Database Design-Functional Dependencies -
Boyce-Codd Normal Form - Third Normal Form - Fourth Normal Form - Overall Database
Design Process. Transaction Management: Transaction concepts - States - Serializability.
Lock based concurrency control: Locks - Granting - Two-Phase Locking protocol. Time
stamp based protocol: Timestamps - Timestamp ordering protocol - Dead lock handling.
UNIT V
Operating Systems
Introduction - History of operating system- Different kinds of operating system – Operating
system concepts - System calls-Operating system structure. Processes and Threads: Processes
- threads - thread model and usage - Inter process communication. Scheduling - Memory
Management: Memory Abstraction - Virtual Memory - Page replacement algorithms.
Deadlocks: Resources- introduction to deadlocks - deadlock detection and recovery -
deadlocks avoidance - deadlock prevention. Input / Output: principles of I/O hardware -
principles of I/O software. Files systems: Files - directories - files systems implementation -
File System Management and Optimization.
LINUX and Shell Programming
Introduction to Linux : operating system and Linux - History of Linux and Unix - Linux
overview - Linux Distributions - Vi editors. Shell - comparison of Shells - working in the
shell - Learning Basic Commands - Compiler and interpreter differences - various directories
- Drilling deep into process management, job control and Automation. Text processing - Text
filtering Tools - working with commands. - Logical operators. - local variables and its scope -
working with arrays.
UNIT VI
Computer Networks
Introduction – Reference Models – OSI and TCP/IP Models – Example Networks: Internet,
ATM, Ethernet and Wireless LANs - Physical Layer – Data Communication - Guided
Transmission Media. Wireless Transmission - Communication Satellites – Telephone
System: Structure, Local Loop, Trunks and Multiplexing and Switching. Data Link Layer:

2
Design Issues – Error Detection and Correction. Elementary Data Link Protocols - Sliding
Window Protocols – Data Link Layer in the Internet - Medium Access Layer – Channel
Allocation Problem – Multiple Access Protocols – Bluetooth. Network Layer - Design Issues
- Routing Algorithms - Congestion Control Algorithms – IP Protocol – IP Addresses –
Internet Control Protocols. Transport Layer - Services - Connection Management -
Addressing, Establishing and Releasing a Connection – Simple Transport Protocol – Internet
Transport Protocols (ITP) - Network Security: Cryptography.
UNIT VII
Software Engineering
Introduction - Software Life Cycle Models - Classical Waterfall Model -Iterative Waterfall
Model - Prototyping Model - Evolutionary Model - Spiral Model. Software Project
Management: Responsibilities of a Software Project Manager - Project Planning - Metrics for
Project Size Estimation - Project Estimation Techniques -Risk Management. Requirements
Analysis and Specification: Requirements Gathering and Analysis -Software Requirements
Specification (SRS) Software Design: Cohesion and Coupling -Neat Arrangement - Software
Design Approaches.
Overview of SA/SD Methodology - Structured Analysis - Data Flow Diagrams
(DFDs).Object Modeling Using UML: Overview of Object-Oriented Concepts - UML
Diagrams - User Interface Design. Testing: UNIT Testing - Black-Box Testing - White-Box
Testing - Debugging -Integration Testing - System Testing. Software Reliability and Quality
Management: Software Reliability - Statistical Testing -Software Quality - Software Quality
Management System. Software Maintenance - Software Reverse Engineering - Software
Reuse.
UNIT VIII
Programming Languages
C Programming : C fundamentals - Expressions - Statements - Operators - Library
functions. Data input output functions - Flow of control - if, if-else, while, do-while, for loop,
Nested control structures - Switch, break and continue, go to statements - Comma operator.
Functions - Recursions. Storage Classes - Arrays - Structures - Unions - Bit wise operations.
Pointers - Structures and Pointers - Files: Creating Processing, Opening and Closing a data
file.
Object Oriented Programming: Principles of Object- Oriented Programming – Beginning
with C++ - Tokens, Expressions and Control Structures – Functions in C++. Classes and
Objects – Constructors and Destructors – New Operator – Operator Overloading and Type
Conversions. Managing Console I/O Operations – Working with Files – Templates –
Exception Handling. Standard Template Library – Manipulating Strings – Object Oriented
Systems Development.
Programming in JAVA: An overview of Java Object Oriented Programming. Data types –
Variables – Type conversion and casting – Strings – Arrays – Control Statements. Class
Fundamentals – Introducing Methods – Constructors – Garbage collection -Overloading
Methods – command line arguments. Inheritance Basics & Types - Method overriding –
Dynamic Method Dispatch – Using Abstract class –Packages & Interface - Exception
Handling - I/O & Applets - AWT Classes.

3
 UNIT IX
Computer Graphics
Overview of graphics Systems: Video Display Device - Refresh Cathode-Ray tubes Raster -
Scan Displays Random - Scan Displays - Color CRT Monitors - Direct view Storage tubes
Flat - Panel Displays Three - Dimensional Viewing Devices, Stereoscopic and Virtual -
Reality Systems. Raster Scan Systems - Random-Scan Systems - Input devices – Voice
Systems - Hard-Copy Devices - Line Drawing Algorithms -DDA Algorithms - Circle
generating Algorithm Properties of Ellipses. Two Dimensional Geometric Transformation -
Three Dimensional Concepts - Visible Surface Detection Methods.
Multimedia Systems
Multimedia Definition - Use Of Multimedia - Delivering Multimedia - Text: About Fonts and
Faces - Using Text in Multimedia - Computers and Text - Font Editing and Design Tools -
Hypermedia and Hypertext. Images – Sound – Animation – Video. Making Multimedia: The
Stage of Multimedia Project - The Intangible Needs - The Hardware Needs - The Software
Needs - An Authoring Systems Needs- Multimedia Production Team.
UNIT X
Theory of Computation
Introduction to formal proof – Additional forms of proof – Inductive proofs –Finite.
Automata (FA) – Deterministic Finite Automata (DFA) – Non-deterministic Finite. Automata
(NFA) – Finite Automata with Epsilon transitions. Regular Expression – FA and Regular
Expressions – Proving languages not to be regular – Closure properties of regular languages –
Equivalence and minimization of Automata. Context-Free Grammar (CFG) – Parse Trees –
Ambiguity in grammars and languages – Definition of the Pushdown automata – Languages
of a Pushdown Automata – Equivalence of Pushdown automata and CFG– Deterministic
Pushdown Automata. Normal forms for CFG – Pumping Lemma for CFL – Closure
Properties of CFL – Turing Machines – Programming Techniques for TM. A language that is
not Recursively Enumerable (RE). An undecidable problem RE – Undecidable problems
about Turing Machine – Post’s Correspondence Problem – The classes P and NP.