RAJASTHAN PUBLIC SERVICE COMMISSION, AJMER SYLLABUS

FOR COMPETITIVE EXAMINATION FOR THE POST OF LECTURER

IN COMPUTER SCIENCE FOR COLLEGE EDUCATION

DEPARTMENT PAPER-II

1. Discrete Mathematical Structures: Counting principles, linear recurrence, mathematical induction, relations and functions, predicate and propositional logic. Graph: Definition and properties, connected graph, cycles & circuits, Tree: rooted tree, spanning trees. Models of Computability: Regular Expressions and Finite Automata. Context free grammars and Push down Automata. Regular and Context free languages, pumping lemma. Turing Machines and undecidability.

2. Data Structures and Algorithms: Analysis, Asymptotic notation, Notions of space and time complexity, Best,Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and conquer; Tree and graph traversals, Spanning tree algorithms, Shortest paths; Hashing, Sorting, Searching. Basic concepts of complexity classes P, NP, NP-hard, NP-complete.

3. Database Management System: ER-model, Relational model (relational algebra, tuple calculus), Database design (integrity constraints, normalization-1NF, 2NF, 3NF, BCNF and 4NF), Structured Query languages (SQL), File structures (sequential files, indexing, B and B+ trees), Transactions and concurrency control.

4. System Software: Assemblers: one pass & two pass assemblers design, Macros & Macro processors, loaders & linkers, Text editors & debuggers, Program generators, Compiler & Interpreter, Different phases of compilation process.

5. Emerging Trends and Technologies: Concept of Parallel Computing (Parallel Virtual Machine and Message passing Interface) , Mobile Computing: Cellular system, Handoff, Location Management, Pervasive Computing, WLAN, ETechnologies: E-commerce framework and applications, Business models, electronic payment System: Digital Token, Smart Cards, Credit Cards, risks in epayment systems. Data Warehousing and Data Mining.