Qualifying Exam Study Guide

Exam Coverage in terms of the ACM (Undergraduate) Curriculum

DS: Discrete Structures
Book: Discrete Mathematics and Its Applications, 6th ed., K. H. Rosen - McGraw-Hill Science/Engineering/Math, Chapters 1-11

o DS1. Functions, relations, and sets
o DS2. Basic logic
o DS3. Proof techniques
o DS4. Basics of counting
o DS5. Graphs and trees
o DS6. Discrete probability
o DS7. Matrix algebra

PF: Programming Fundamentals:
Book: Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivbest, C. Stein - MIT Press, Chapters 1-4, 6-8, 10-13, 15-16, 22-26

o PF1. Fundamental programming constructs
o PF2. Algorithms and problem-solving
o PF3. Fundamental data structure
o PF4. Recursion

AL. Algorithms and Complexity
Book: Introduction to the Theory of Computation, M. Sipser - PWS Pub. Co, Chapters 0-5, 7, 10.6

o AL1. Basic algorithmic analysis
o AL2. Algorithmic strategies
o AL3. Fundamental computing algorithms
o AL5. Basic computability
o AL6. The complexity classes P and NP
o AL7. Automata theory

AR: Architecture and Organization
Book: Computer Architecture: A Quantitative Approach, 3rd ed., J. L. Hennessy and D. A. Patterson - Morgan Kaufmann, Chapters 1, 2, 3.1-4, 4.1-3, 5.1-9, 7.1-7, A.1-5

o AR1. Digital logic and digital systems
o AR2. Machine level representation of data
o AR3. Assembly level machine organization
o AR4. Memory system organization and architecture

OS: Operating Systems
Book: Operating System Concepts, 8th ed., A. Silberschatz, P. B. Galvin, G. Gagne - John Wiley & Sons, Inc., Chapters 1-10

o OS1. Overview of operating systems
o OS2. Operating system principles
o OS3. Concurrency
o OS4. Scheduling and dispatch
o OS5. Memory management

NC: Net-Centric Computing
Book: Computer Networks and Internets, 5th ed., D. Comer - Prentice Hall, Chapters 1-4, 13, 15, 16, 20-27, 30 OR
Book: Computer Networking: A Top-Down Approach, 5th ed., J. Kurose, K. Ross - Addison Wesley, Sections 1.1-6, 2.1-5, 3.1-5, 4.1-5, 5.1, 5.4-6, 6.2, 6.3, 8.2, and 8.3

o NC1. Introduction for net-centric computing
o NC2. Communication and networking
o NC3. Network security
o NC7. Compression and decompression

PL: Programming Languages
Book: Modern Programming Languages: A Practical Introduction, A. B. Webber - Franklin, Beedle & Associates, Chapters 1-19, 23,24
Book: Compilers: Principles, Techniques and Tools, A. V. Aho, R. Sethi, J. D. Ullman - Addison-Wesley, Chapters 1-5

o PL1. Overview of programming languages
o PL4. Declarations and types
o PL5. Abstraction mechanisms
o PL6. Object-oriented programming
o PL7. Functional programming
o PL8. Language translation systems

IM: Information Management
Book: Database Management Systems, 3rd ed., R. Ramakrishnan, J. Gehrke - McGraw Hill Higher Education, Chapters 1-5, 8, 16, 19

o IM1. Information models and systems
o IM2. Database systems
o IM3. Data modeling
o IM4. Relational databases
o IM5. Database query languages
o IM6. Relational database design