GATE SYLLABUS FOR COMPUETR SCIENCE

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

BASIC MATHEMATICS:

Elements of probability, matrix algebra, numerical methods: interpolation, root

finding, differentiation and integration. Discrete mathematics: sets, relations,

functions, mathematical induction, counting, groups, graphs, partial orders,

lattices and boolean algebra, propostional logic.

THEORY
OF COMPUTATION:

Regular and context free languages, finite state machines and push down automata,

turing machines and undecidability.

COMPUTER HARDWARE:

Logic
function, minimization techniques, design of combinational and sequential

circuits using gates and flip-flops, design with integrated circuts incuding ROM

and multiplexers, microprocessor architecture: programming, interfacing with memory

and I/O devices(modes of data transfer and their implementation, serial and

parallel communication interface). Detailed
knowledge of 8085 microprocessor will

be assumed.

COMPUTER ORGANIZATION:

Number representation and airthmetic, functional organization, machine instructions

and addressing modes, ALU, hardwired and microprogrammed control,
instrucation

pipelining, memory organization, input/output.

PROGRAMMING AND DATA STRUCTURE:

structured
programmming with pascal/C including recursion; arrays, stacks, strings,

queues,
lists, trees, sets and graphs; algorithm for tree and graphs traversals,

connected
component, spanning trees, shortest paths; hashing, sorting and searching

algorithm design and analysis techniques, big 'oh' notation, solution of sample

recurrence relations.

LANGUAGE PROCESSOR:

Assembler, loader, linker, macroprocessors, text editors, programming languages,

scope rules and parameter passing mechanism; compilers lexical analysis, parsing,

syntax, directed translation, run time environment, machine code generation;

interpreters.

OPERATING SYSTEM:

Batch,
multi-programming and time-sharing systems; processsor, memory, device and

file management, virtual memory, process scheduling, interprocess communication,

process synchoronization and concurrency, deadlocks, protection.

DATABASE
SYSTEM:

File organization techniques; indexing,B-trees, B-plus trees; relational and

network datat models; normal forms; query
language: SQL