GRADUATE EXAM TOPICS

Topic List for CMPS 5113, Programming Languages

  1. Language Design Issues
    • Various forms of efficiency
    • Generality, orthogonality, uniformity
  2. Formal Syntax Definitions
    • Syntax diagrams
    • Backus-Naur form
    • Ambiguity, associativity, precedence
    • Parsing
  3. Semantics
    • Scope rules
    • Types of allocation and binding
  4. Control Structures
    • Parameter passing modes
    • Activation record
    • Run-time stack
    • Access links
  5. Object-oriented Programming Languages
    • Inheritance
    • Overloading and Polymorphism
    • Dynamic binding
  6. Functional Programming Languages
    • Recursion
    • List handling in LISP
  7. Logic Programming
    • Syntax diagrams
    • Backus-Naur form
    • Ambiguity, associativity, precedence
    • Parsing
  8. Semantics
    • Scope rules
    • Types of allocation and binding
  9. Control Structures
    • Parameter passing modes
    • Activation record
    • Run-time stack
    • Access links
  10. Object-oriented Programming Languages
    • Inheritance
    • Overloading and Polymorphism
    • Dynamic binding
  11. Functional Programming Languages
    • Recursion
    • List handling in LISP
  12. Logic Programming
    • Horn clauses
    • Resolution and Unification

REFERENCE: Programming Languages, Principles and Practice, Louden


Topic List for CMPS 5133, Computer Architecture

  1. General Concepts
    • Binary and hexadecimal numbers (Ch 10)
    • Binary representation of floating point numbers (Ch 10)
    • Instruction set architecture
      • Addressing modes (Ch 13)
      • Types of operations (Ch 12)
      • RISC vs CISC (Ch 15)
    • Main hardware components
      • CPU (Ch 14)
      • Registers (Ch 14)
      • Memory (Ch 5)
      • Disks (Ch 6)
    • Execution cycle/interrupts (Ch 3)
    • Bus Systems (Ch 3)
  2. Memory Systems:
    • Memory allocation and management (Ch 8)
    • Cache memory (Ch 4)
      • Mapping functions
      • Replacement algorithms
      • Data cache
      • Instruction cache
    • Virtual memory (Ch 8)
    • Shared memory - cache coherence (Ch 17)
  3. Pipelined Processors (Ch 14)
    • Description – pipeline stages
    • Instruction prefetching
    • Hazards
    • Branch handling
  4. Parallel Systems
    • Instruction - level parallelism (Ch 16)
    • Superscalar (Ch 16)
    • VLIW (Ch 17)
    • Multiprocessors (Ch 17)
    • Nonuniform memory access (Ch 17)

REFERENCES: Computer Organization and Architecture (10th Edition): William Stallings


Topic List for CMPS 5143, Operating Systems

Emphasis will be placed on the terms and concepts listed below. TOPICS:

  1. Operating System Structures
    • Virtual Machines
    • System Calls
    • Layered Systems
  2. Process Management
    • Process creation and control structures: PCB, state diagrams, ready list, etc.
    • Threads
    • Scheduling (Long-term scheduling, short-term scheduling and thread scheduling)
    • Interprocess Communication: semaphores, monitors, message passing, etc.
  3. Input/Output
    • Deadlock
    • Interrupts
    • Device controllers
    • Direct Memory Access
  4. Storage Management
    • Static: MFT, MVT
    • Dynamic memory management: paging, segmentation
    • Virtual memory: paging, segmentation, virtual-to-real address mapping and translation, etc.
    • Page Replacement Algorithms
    • Sharing
    • Protection
  5. File Systems
    • Organization
    • Implementation
    • Sharing
    • Protection

REFERENCES: Applied Operating Systems Concepts, by Silberschatz, Galvin and Gagne


Topic List for CMPS 5153, Software Engineering

  1. Software Process Models
    • Waterfall and variants
    • Distribution of time, effort and cost in phases
    • Evolutionary models
    • Rapid Application Model
  2. Project Management
    • Team and People Management
    • Project Scheduling and Tracking
  3. Analysis and Design Tools and Techniques
    • Requirements Gathering
    • Structured Programming
      • Data Flow and Data Structure Design Techniques
    • Object Oriented Programming
      • UML Diagrams
    • Module Design
  4. Software Quality
    • 11 Quality Factors
    • Assurance Activities
    • Metrics (product and process)
    • Standards (CMM and ISO9000)
  5. Testing
    • Types and philosophies of testing
    • Choice of test data
    • Object oriented testing
    • Debagging

REFERENCES: Software Engineering, 6th ed, by Ian Sommerville


Topic List for CMPS 5243, Algorithm Analysis

  1. Complexity (Ch 3,4)
    • Big-O definition
    • Runtime comparisons
    • Recursion and recurrence relations
    • Concepts of P and NP
  2. Data Structures
    • Array based vs. list based (Ch 10)
    • Hash tables (Ch 11)
    • Trees: binary search trees (BSTs) (Ch 12)
    • Balanced BSTs (Ch 13)
  3. Sorting / Searching (Ch 6,7,8)
    • O(n) search (linear)
    • O(log n) search (binary)
    • O(n2) sort (bubble, selection, insertion)
    • O(n log n) sort (quicksort, mergesort)
    • O(n) sort (counting, radix)
  4. Graph Algorithms
    • DFS, BFS (Ch 22)
    • Minimum spanning trees (Ch 23)
    • Shortest path (single source, all-pairs) (Ch 24,25)
  5. Algorithm categories
    • Recursive
    • Greedy (Ch 16)
    • Divide and conquer (Ch 4)
    • Dynamic programming (Ch 15)
  6. String matching and Parsing (Ch 32)

REFERENCE: Introduction to Algorithms, by Cormen, Leiserson, and Rivest (3rd Edition)