Computer Science Punjab PMS Paper II Syllabus

PAPER II Total Marks:100

SECTION- A

1. Theory of Automata and Formal Languages.

Finite State Models: Language definitions preliminaries, Regular expressions/Regular languages, Finite automatas (FAs), Transition graphs (TGs),NF As, kleene’s theorem, Transducers (automata with output), Pumping lemma and non regular language Grammars and PDA: Context free grammars, Derivations, derivation trees and ambiguity, Simplifying CFLs , Normal form grammars and parsing, Push-down Automata, Pumping lemma and non-context free languages, Decidability, Chomsky’s hierarchy of grammars, Turing Machines Theory: Turing machines, Post machine, Variations on 1M, 1M encoding, Universal Turing Machine, Context sensitive Grammars, Defining Computers by TMs.

REFERENCE MATERIAL:

1. Introduction to Computer Theory, Denial Cohen, John Wiley & Sons, Inc.

2. Introduction to Automata Theory, Languages and Computation, J Hopcraft, D. Ullman.

3. Languages and Machines, An Introduction to the Theory of Comp. Sc., 2/e Thomas A Sudkamp, Addison Wesley.

2 Compiler Theory & Design

Compiler techniques and methodology. Organization of compilers. Lexical and syntax analysis. Parsing techniques. Object code generation and optimization, detection and recovery from errors. Comparison between compilers and interpreters.

REFERENCE MATERIAL:

1. Compiler Design and Construction, by Alfred V. Aho, Ravi Sethi, Hardcover 2nd edition, 1987, Van Nostrand Reinhold,. ISBN: 0317636367.

3. Numerical Methods

Mathematical Preliminaries, Solution of Equations in one variable, Interpolation and Polynomial Approximation, Numerical Differentiation and Integration, Initial Value Problems for Ordinary Differential Equations, Direct Methods for Solving Linear Systems, Iterative Techniques in Matrix Algebra, Solution of nonlinear equations, Approximation Theory, Eigenvalues and Eigenvector computation.

REFERENCE MATERIAL:

1. Elements of Numerical Analysis, Dr. Faiz, M. Afzal

SECTION -B

I. Data Base Systems

Basic database concepts, Entity Relationship modelling, Relational data model and algebra, Structured Query language, RDBMS; Database design, functional dependencies and normal forms, Transaction processing and optimization concepts, concurrency control and recovery techniques, Database recovery techniques, Database security and authorization. Small Group Project implementing a database. Physical database design: Storage and file structure, indexed files, hashed files, signature files, b-trees, files with dense index, files with variable length records, database efficiency and tuning Data Warehousing and Data Mining, Emerging Database Technologies and Applications.

REFERENCE MATERIAL:

1. Database Systems, C.J.Date, Addison Wesley Pub. Co. ( 2004).

2. Database Systems: A Practical Approach to Design, Implementation and Management, R Connolly and P .Begg, Addison-Wesley Pub. Co (2003).

3. Fundamentals of Database Systems, 3/E, Elmasri and Navathe, Addison Wesley, ISBN: 0-201-74153-9.

2. Software Engineering

Software Engineering, Process Models, Software verification and validation. Techniques are introduced to evaluate software correctness, efficiency, performance and reliability, integration of these techniques into a verification and validation plan. Technical reviews, software testing, programme verification, prototyping, and requirement tracing. Attitude of industry toward reliability and performance.

REFERENCE MATERIAL:

1. Software Engineering: A Practitioner’s Approach, Roger Pressman, McGraw-Hill, 2001.

2. Software Engineering, Ian Sommerville, Addison-Wesley 2001, ISBN: 0-201- 39815-X.

SECTION -C

1. Artificial Intelligence

Introduction to Common Lisp. AI classical systems: General Problem Solver, rules, simple search, means-ends analysis. ElIZA, pattern matching, rule based translators, OPS-5. Knowledge Representation: Natural language, rules, productions, predicate logic, semantic networks, frames, objects, scripts. Searching, Depth first search, breadth first search, best first search, hill climbing, min-max search. Symbolic Mathematics: student solving algebra problems, translating English equations, solving algebraic equations, simplification rules, rewrite rules, meta-rules, Macsyma, PRESS, ATLAS. Logic Programming: Resolution, unification, horn-clause logic, Prolog, Prolog programming. Sample case studies of shells and Knowledge Based Systems. A brief appreciation of state of the art computational techniques like neural networks, genetic algorithm, fuzzy sets.

REFERENCE MATERIAL:

1. Artificial Intelligence by Luger, 4th edition, Pearson Education.

2. Computer Graphics

Graphics hardware, Fundamental algorithms, Applications of graphics. Interactive graphics programming -graph plotting, windows and clipping, and segmentation. Programming raster display systems, panning and zooming. Raster algorithms and software Scan-Converting lines, characters and circles. Region filling and clipping. Two and three dimensional imaging geometry and transformations. Curve and surface design, rendering, shading, colour and animation.

REFERENCE MATERIAL:

1. Computer Graphics, Principles and Practice, J. D. Foley, A van Dam, S. K. Feiner and J. F. Hughes, Addison-Wesley ISBN: 0-201-12110-7.

2. Computer Graphics, F.S.Hill, Maxwell MacMillan ISBN: 0-02-354860-6.

FURTHER SUGGESTED READINGS

1. Computers: Tools for an Information Age, 8th Ed. H I Capron, Addison Wesley, 2003. Paul Wilton.

2. Computer Concepts, 3rd Ed, ITP 1998; J.J.Parsons & D. Oja

3. Silberschatz. Galvin & Gagne, Operating System Concepts, 6th Ed. 2002. John Wiley & Sons, Inc. ISBN 0-471-41743-2.

4. Tanenbaum. A.S., Modern Operating Systems, 2nd. Ed, 2001.

5. Deitel & Deitel, C++ How to Program, 4th Ed. Prentice Hall.

6. Tocci & Widmer, Digital Systems, Principles and Applications, 8th Ed.. Published by Pearson Education.

7. John F. Wakerly, Digital Designs, Principles & Practices, 3rd. Ed. Published by Prentice Hall.

8. M. Morris Mano, Computer System Architecture (Solutions Manual), Prentice Hall, 1979, ISBN 0- 132-14510-3.

9. Jim Keogh, C++, Programmers Notebook, 2nd Ed.

10. Sipser, Introduction to the Theory of Computation, 2nd Ed. Thomson Course Technology, 2006.

11. Ian Sommerville, Software Engineering, 6th Ed. Addison Wesley,2001

12. M. A. Weiss, Data Structures and Algorithm Analysis in C. Pearson Education 2nd Ed. 1997.

13. Elmasri & Navathe, Fundamentals of Database Systems, 4th Ed.

14. Expert Systems and Applied Artificial Intelligence by Efraim Turban

15. Artificial Intelligence by Rich & Knight.

16. Artificial Intelligence by George F. Luger.

17. Donald Hearn and M. Pauline Baker. Computer Graphics and OpenGL, 3rd Ed.

18. Foley, Van Dam, Feiner, and Hughes, Computer Graphics Principle & Practices.

19. Mathematical Structures for Computer Science, Freeman & Company; G.L.Gersting.

20. Java Script; The Definitive Guide, 2nd Ed, O. Reilly, 1997. D. Flanagan.

21. The HTML, Sourcebook, Wiley 1996. I.S. Graham.

22. Computer Science; An Overview 6th Ed. Addison Wesley, 1998. J.G. Brookshear.

23. Java; An Object First Approach, Addison Wesley, 1996. F. Culwin.

24. Web Page Scripting Techniques, Hayden Books,1996. J. Bloomberg, J. Kawski. J & P. Treffers.

25. Kenneth H. Rosen, Discrete Mathematics and its Application, 5th Ed. 2003, McGraw-Hill.

26. T .H. Cormen, C.E. Leiserson, R.L. Rivest, and C.D. Stein, Introduction of Algorithms, MIT Press. 2nd Ed. 2001.

27. Assembly language programming of IBM PC by Ytha Yu and Charles Marut. McGraw Hill, 1992.

28. Saeed Bhatti & Naeem Bhatti, a first course in Numerical Analysis, 4th Ed. 2003.

29. David A Patterson, John L. Hennessy, Computer Organization and Design, 3rd Ed.

30. Hennessy, J.I. & Patterson .D.A., Computer Architecture; A quantitative Approach, 2nd Ed. Morgan Kaufmann, 1996.

31. Introduction to Digital Systems by Ercegovac, Lang & Moreno, Wiley, 1999.

32. Introduction to Wireless Systems by P.M. Shankar, John Wiley & Sons,2002.

33. Advanced Digital Designs with the Verilog HDL by Michael D. Ciletti. Prentice Hall, 2003.