Computer Science Graduate Comprehensive Exams

Part 2 Architecture

A. Binary Representations of Data

• Binary Representations of Octal, Decimal and Hexadecimal digits
• Binary Representation of Characters, ASCII code
• Representations of Signed and Unsigned Integers and Fractions
• Packed Decimal, 2’s Complement and Signed Magnitude
• Representations of Fixed Point and Floating Point numbers
• IEEE Floating Point format

B. Design of Combinational functions and circuits

• Boolean Algebra, Truth Tables and Karnaugh Maps
• Gates, Combinational circuits, and timing delays
• Decoders, Multiplexers, Full and Half Adders, Full and Half Subtractors, Combinational Multiplier and Divider Circuits, and Logic Circuits, ROMs and PLAs

C. Design of Sequential functions and circuits

• State Diagrams, State Tables and Register Transfer Language Programs
• Flip-flops, Registers; the Clock and Timing Control
• Registers with various operations such as: Counters, Logical and Arithmetic Shift operations, and Parallel Load operations.
• Integer and Floating Point .Sequential Multiplier and Divider circuits

D. Register Transfer Language (RTL)

• Representation of Control functions and Microoperations
• Specification of Register and Memory transfers, Buses, Arithmetic and Logical operations
• Translation of an RTL program into a Logic Diagram
• Timing Signals and Control Signals

E. Performance and Cost Analysis

• Benchmarks, Performance Measures, Performance and Execution Time, Amdahl’s law, Speedup, CPU Time, Clock Cycle Time and Clock Rate, Cycles per Instruction and Instruction Count

F. Instruction Set Principles

• Accumulator, Stack and General Purpose Architectures
• Register-Register (or Load-Store Architecture) and Register-Memory Architectures
• Operand Addressing Modes, Instruction Set Operations, Type and Size of Operands and the Encoding of an Instruction Set
• RISC versus CISC

G. Design and Performance Analysis of a non-Pipelined CPU

• An RTL Program Specifying the Fetching and Execution of Instructions
• Operand Address Decoding
• Interrupt Cycle
• Hard-Wired and Microprogrammed Control Units
• Microprogram Instructions and Formats
• Control Words

H. Design and Performance Analysis of a Pipelined CPU

• Relationship between an Instruction set and a Pipelined CPU
• Pipeline Registers
• Pipeline Data and Control Hazards
• Stalls
• Forwarding
• Instruction Scheduling, Delay Slots and a Delayed Branch
• Multi-cycle Operations and Exception Handling

I. Memory-Hierarchy Design and Performance Analysis

• Principle of Locality
• Cache, Main Memory and Secondary Memory
• Cache hit rate and time, miss rate and time, and miss penalty
• Direct, Associative, and Set Associative mappings
• Replacement Algorithms
• Write Through and Write back Caches
• Main Memory, the CPU-Memory Bus, Access time and Cycle time, and bandwidth
• Design of 1-Dimensional and 2-Dimensional RAMs and DRAMs
• Interleaved Memory and Memory Banks
• Virtual Memory

J. I/O and Storage System Design, and Performance Analysis

• Magnetic Disks
• I/O Buses, Bus Masters and Synchronous and Asynchronous Buses
• Data Transfers. Hand Shaking, Cycle Stealing, Bus Request and Acknowledge
• I/O programming and Interrupt Handling
• DMA and 10P
• I/O Performance Measures

K. Multiprocessors

Textbooks

• J. Hennessy & D. Patterson, Computer Architecture A Quantitative Approach, 2nd Edition, Morgan Kaufmann.
• J. Hayes, Computer Architecture, 2nd Edition, Hayes, McGraw-Hill.
• M.M. Mano, Computer System Architecture, 3rd Edition, Prentice Hall.
• D. Patterson and J. Hennessy, Computer Organization and Design, 3rd Edition, Morgan Kaufmann.

Part 3 Artificial Intelligence

A. Search Techniques

• Generate-and-Test approach
• Constrain-and-generate approach
• Uninformed search methods (depth-first, breadth-first, etc.)
• Branch-and-bound
• Informed search methods (best-first, beam, A*, etc.)
• Heuristics for informed search methods and constraint satisfaction problems
• Adversarial search techniques and games (Minimax, Alpha-Beta Pruning)

B. Knowledge Representation

• Semantic networks
• Frames
• Production rule systems
• Neural networks and genetic algorithms

C. Logic

• Propositional Logic
• First-order (predicate) logic
• Clausal form (including skolemization)
• Unification
• Resolution

D. Applications

• Expert systems
• Learning
• Constraints and propagation
• Planning
• Natural language processing

Textbooks

• G. F. Luger and W. Stubblefield, Artificial Intelligence, Third Edition, Addison-Wesley, 1998.
• S. Russell and P. Norvig, Artificial Intelligence – A Modern Approach (second edition), Prentice Hall, 2003.
• P. H. Winston, Artificial Intelligence, Addison Wesley, 1992.
• M. R. Genesereth and N. J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann 1987.
• C. J. Hogger, Essentials of Logic Programming, Oxford UP 1990.
• B. Coppin, Artificial Intelligence, Jones and Bartlett, 2004.

Note

Russell/Norvig is useful for areas A–D, but you may wish to consult Genesereth/Nilsson or Hogger to get more background on logic. Winston is very useful for all areas except logic.

Part 4 Database Systems

• Introduction to Database Systems
• The Relational model, ER diagrams, Relational algebra
• Database Design
• Normal Forms
• Study of Several Real-world Database Management Systems (DBMS’s)
• SQL
• Query and Transaction Processing
• Concurrency, Recovery
• Distributed, Parallel, Client-server, and Object-oriented Databases

Textbooks

• Rob, Peter, et al. Database Systems, Cengage Learning, 2013.
• Date Addison-Wesley, Introduction to Database Systems (Eighth Edition), 2003.
• Korth, Silberschatz, Sudrashan, Database System Concepts (Fifth Edition), McGraw-Hill, 2005.
• Ricardo, Jones and Bartlett, Databases Illuminated, 2004.

Note

Although some books may not cover all of the topics listed above, a good knowledge of any one of the books, plus material on individual DBMSs, should be sufficient to pass the exam.

Part 5 Management Information Systems

(M.S. students must take this exam)

• Requirements elicitation processes, functional requirements, non-functional requirements, requirements analysis techniques:
• UML Diagrams—general definitions and creation of use-case model diagrams, activity diagrams, sequence diagrams, class diagrams, and state transition diagrams
• Information Systems Planning—guidelines for effective planning, tools for identification of opportunities, innovating with technology, systems for strategic advantage, development processes for strategic, tactical and operational plans
• Systems Analysis—approaches, phases, fact-finding techniques including sample size determination, feasibility tests, alternate design approaches, user interface design
• Telecommunications—types of networks, transmission media, transmission speed, network protocols, network topologies, OSI Reference Model, wireless technologies
• Testing techniques and software quality assurance—unit testing, regression testing, equivalence class partitioning, boundary value analysis, path analysis, integration testing, smoke testing, black box testing, white box testing, risk identification/management/amelioration
• Methodologies, Strategies, and Tactics for Software Development and Implementation—waterfall (SDLC), prototyping, RAD, RUP, scrum, XP, agile, custom development options, purchased packages, user-developed software, combinations, conversion strategies from old to new systems, ASPs, six sigma, capability maturity model, outsourcing alternatives
• Software Estimation Methods—lines of code, function point analysis, COCOMO, cyclomatic complexity
• Project Adoption—project evaluation and prioritization techniques, risk identification/analysis (brainstorming, nominal group technique, Delphi method, etc.), justifying technology investments (Payback period, Break-even, Return on Investment, Net Present Value, Internal Rate of Return)
• Organization structure types, organizing a framework for systems technology management
• Changing nature of software, types of artificial intelligence, managerial support systems, decision support systems, executive information systems, GISs, E-commerce, enterprise-wide applications
• Project Scheduling—quantitative and probabilistic—CPM and PERT calculations, types of buffers, resource leveling and smoothing, tradeoffs between methodologies
• Information Systems Project Failure—major categories (Lyytinen/Hirschheim, etc.), primary reasons, impact and cost of defect removal by project phase (Boehm, etc.)
• Project Control and Assessment—risk management categories, planning vs. control issues, cost/benefit and risk analyses, scope management, quality management, project closure

Exam Format

There will be a series of relatively short questions, with some choice. The exam may have a case study, but a case study may not be present each time the exam is given. If there is a case study, there will be several questions on it. For example, you might have to answer a total of 12 out of 15 questions including two case study questions.

Textbooks

• Kenneth C. Laudon and Jane P. Laudon, Management Information Systems: Managing the Digital Firm, 15th edition. Pearson, 2018.
• Joseph Valacich and Joey George, Modern Systems Analysis and Design, 8th edition. Pearson, 2017.
• Jack T.Marchewka, Information Technology Project Management, 5th edition. John Wiley & Sons, 2015.
• Roger S Pressman and Bruce R. Maxim, Software Engineering: A Practitioner’s Approach, 8th edition. McGraw Hill, 2015.

Part 6 Operating Systems

A. OS Types and Organization

• Batch; multi-programming, time-sharing
• Multiprocessor or multicore, distributed, client-server, clustered, real-time systems
• Structure of OS—simple, layered, microkemel
• Virtual Machines
• Protection CPU, Memory, 1/0

B. Input-Output

• Interrupt, trap, interrupt vector
• Interrupt mechanism and handling, privileged instructions
• Alternatives to interrupts: busy-waiting, polling
• Buffering, OMA
• I/O Processing

C. Process Management

• Process concept and process scheduling
• Serving process requests (synchronous and asynchronous interrupts)
• Process switching mechanism
• Cooperating processes, inter-process communication, sockets, RPCs
• Multi-threading—types of threads, multi-threading models system calls, etc.

D. CPU Scheduling

• Basic concepts
• Interactive versus batch processing
• Scheduling criteria and algorithms—First Come First Served, Shortest Job First, Priority, Round-Robin, Multi­level Queue, Multi-level Feedback Queue

E. Process Synchronization

• Critical section problem, synchronization hardware and primitives, semaphores, monitors, mutex locks
• Classical problems of synchronization: Bounded-Buffer, Producer-Consumer, Readers-Writers, Dining Philosophers

F. Deadlocks

• Conditions, prevention, avoidance, detection, and recovery
• Resource allocation graphs, Banker’s Algorithm

G. Memory Management

• Logical versus physical memory
• Memory management hardware
• Memory allocation—MFP, MVP (best-fit, worst-fit, first-fit), internal and external fragmentation
• Paging: page table organization, special hardware support, page table structure (hierarchical, hashed, inverted), shared pages
• Segmentation: segmentation implementation, shared segments, segmentation with paging
• Virtual memory:·demand paging, pre-paging, page replacement algorithms (FIFO, Optimal, LRU, Additional reference bits, Second Chance/Clock), allocation of frames, thrashing, working set theory and its application to paging, program structure.

H. Mass Storage Structure

• File systems and their implementations
• Magnetic disc hardware, seek time, rational latency
• Other types of storage devices
• Disk Scheduling Algorithms—First Come First Served, Shortest Seek Time First, SCAN, C-SCAN, LOOK, C-LOOK

Textbooks

• Silberschatz & Galvin, Operating Systems Concepts, 6th edition, Addison-Wesley, 2003.
• Tanenbaum, Modern Operating Systems, 2nd edition, Prentice-Hall, 2001.
• Stallings, Operating Systems Internals and Design Principals, 4th edition, Prentice-Hall, 2001.

Part 7 Programming Languages

Compilers

• regular expressions
• finite automata
• context-free grammar
• recursive-descent parsing
• storage organization
• activation record
• parameter passing
• symbol table
• dynamic storage allocation

OOP

• state (instance variable, data members) I behavior (methods, member functions) of a class
• class, instance/class variables
• data access: public I private I protected
• Inheritance (is-a) versus Composition (has-a)
• upcasting, downcasting
• message passing, receiver, this
• constructors: default constructors
• get/set methods
• high-level versus low-level classes/methods
• overloading/overriding
• polymorphism
• reading/writing objects for persistence
• super/subclasses; super/subinterfaces
• abstract classes and methods
• OOP languages (Java and C++)

Functional Programming

• types
• pattern-matching
• recursion
• lambda expressions
• polymorphism
• higher-order functions
• FP languages (Haskell and Python)

Textbooks

• Aho A., Lam, M., Sethi, R., Ullman, J., Compilers: Principles, Techniques, & Tools, Addison Wesley, 2007.
• Timothy Budd, An Introduction to Object-Oriented Programming, 3rd Edition, Addison Wesley, 2002.

Part 8 Telecommunications and Networking

Textbooks

• Text #1: Stallings, William, Data and Computer Communications, 7th edition, Prentice-Hall.
• Text #2: Kurose, James and Ross, Keith, Computer Networking, 2nd edition, Addison Wesley.

Readings

• Text #1 Chapter 1: Data Communications and Networking Overview or Text #2 Chapter 1: Computer Networks and the Internet
• Text #1 Chapter 2: Protocol Architecture or Text #2 Chapter 1: Computer Networks and the Internet
• Text #1 Chapter 3: Data Transmission
• Text #1 Chapter 4: Guided and Wireless Transmission
• Text #1 Chapter 5: Signal-Encoding Techniques
• Text #1 Chapter 6: Digital Data Communication Techniques
• Text #1 Chapter 7: Data Link Control
• Text #1 Chapter 8: Multiplexing
• Text #1 Chapter 9: Spread Spectrum
• Text #1 Chapter 10: Circuit Switching and Packet Switching
• Text #1 Chapter 11: Asynchronous Transfer Mode
• Text #1 Chapter 14: Cellular Wireless Networks
• Text #1 Chapter 15: Local Area Networks Overview
• Text #1 Chapter 16: High Speed LANs
• Text #1 Chapter 17: Wireless LANs
• Text #1 Chapter 18 and Chapter 19 (section 19.2 only): Internetwork Protocols and Operation or Text #2 Chapter 4: Network Layer and Routing (exclude sections 4.8 and 4.9)
• Text #1 Chapter 20: Transport Protocols or Text #2 Chapter 3: Transport Layer or Text #2 Chapter 2: Application Layer
• Text #1 Chapter 22: Distributed Applications
• Text #1 Appendix 8: Fourier Analysis

Part 9 Theoretical Computer Science

(questions will include both computability theory and formal language theory)

Textbooks

• Michael Sipser, Introduction to the Theory of Computation (Any Edition).
• Peter Linz, An Introduction to Formal Languages and Automata, 5th Edition.
• Dexter C. Kozen, Automata and Computability.

Formal Language Theory

Computability Theory

Complexity Theory