Home > Graduate > Academics > Master’s Qualifying Examination

Master’s Qualifying Examination

Result of MS qualifying Exam-Fall 2018: Click here

ECE department requires all MS-CSE students to pass qualifying exams of any three to five different subjects form the seven subjects listed below. The requirement depends according to the following rule:

  1. For thesis based Masters students need to pass in three subjects
  2. For project based Masters students need to pass in four subjects
  3. For course based Masters students need to pass in five subjects

List of Subjects

Database Management Systems Syllabus
Computer Networks Syllabus
Software Engineering Syllabus
Operating Systems Syllabus
Artificial Intelligence Syllabus
Algorithms Syllabus
Automata Theory Syllabus

For each subject, students are required to register at the department. Without registration, students are not allowed to sit for the exam.

Syllabus for Qualifying Examination of Database Management System

Topics:

  1. Introduction to database design
    1. Database design through Entity Relational (ER) model, entity, relation, relationship sets,
    2. Key, principal constraints, weak entities, aggregation, class hierarchies,
    3. Conceptual design through ER model, UML design.
  2. Relational model
    1. Creating and modifying relations using SQL,
    2. Integrity constraints over relations,
    3. Transforming ER to relational model,
    4. Views and operations on views.
  3. Relational algebra and Calculus
    1. Selection, projection and other set operations,
    2. Joins, division,
    3. Tuple and domain relational calculus.
  4. SQL queries
    1. Basic SQL queries,
    2. Nested SQL queries,
    3. Aggregate and join operations,
    4. Complex integrity and triggers.
  5. Transaction management
    1. ACID properties of transaction,
    2. Serializability, lock based concurrency control, deadlocks, performance of locking,
    3. Deadlock prevention, timestamp based concurrency control.
  6. Schema refinement and Normal forms,
    1. Introduction to schema refinement and problems caused by redundancy,
    2. Functional dependencies, different normal forms,
    3. Lossless join decomposition and dependency preserving decomposition.

Reference Book:

  • Database Management System. Raghu Ramakrishnan, Johannes Gehrke, McGraw Hill, 3rd. or 4th. Edition.
  • Fundamentals of Database System. Ramez Elmasri, Shamkant B. Navathe, Fifth/Sixth Edition, Pearson Education.

 

Syllabus for Qualifying Examination of Computer Networks

Topics:

  1. Functionalities/services of each OSI and TCP/IP layer, Network Applications and protocols
  2. UDP, TCP, Flow Control and Congestion Control
  3. IPv4, IPv6, NAT, RIP, OSPF, BGP
  4. Wireless networks – Spread spectrum, FHSS, WLAN, hidden and exposed node problems
  5. Network security – encryption and decryption, Digital Signature, Hash functions

Reference Books:

  • Computer Networking: A Top-Down Approach by James F. Kurose and Keith W. Ross
  • Computer Networks by Andrew S. Tanenbaum. (Chapters – 2, 3, 4.4, 5 to 8)
  • Data Communications and Networking by Forouzan (Chapter 3)

 

Syllabus for Qualifying Examination of Software Engineering

Topics:

  1. Software process models, process iteration, software specification, software design and implementation, software validation, software evolution, automated process support
  2. Management activities, project planning, project scheduling, risk management
  3. Defect testing, integration testing, object oriented testing, testing workbenches
  4. Limits to thinking, group thinking, choosing and keeping people, the people capability maturity model
  5. Requirement analysis, functional vs. nonfunctional requirements, use cases, requirement completeness and inconsistency
  6. Object oriented concepts e.g. inheritance, polymorphism, overriding etc.
  7. Software design and software engineering, design fundamentals, effective modular design

Reference Books:

  1. Software Engineering – Ian Sommerville (Chapter 1, 3, 4, 20, 22)
  2. Software Engineering, A Practitioner’s Approach – Roger Pressman (Chapter 6, 8, 10)

 

Syllabus for Qualifying Examination of Operating Systems

Topics:

  1. Concepts on OS and its Structure
    1. Look at Firmware, Bootstrap programs
    2. Various OS types (No Structure, Layered, Micro kernel based etc.)
    3. Virtual Machines (JVM and VMWare – basic concepts)
    4. Memory Hierarchy and relationship among them
    5. System Call (What is it, look at fork() )
    • Question Pattern: There will be questions about basic concepts on these three topics to know about your understanding.
  2. Concepts on Process Management
    1. Scheduling Algorithms(FCFS, RR,Priority, SJF)
    2. Various Threading models (The context when a model is useful)
    3. Synchronization (Hardware methods e.g. test and Set, Swap; Software Methods e.g. Semaphores, Monitors)
    4. Classic Synchronization Problems ( Dining Philosophers, Reader Writer and Bounded Buffer )
    5. Critical Section and handling of it
    6. Concepts on Memory Management
    7. Current Knowledge of Any OS
    • Question Pattern: There will be a math problem from scheduling algorithms, one problem on synchornization and one from the other concepts
  3. Concepts on Memory Management
    1. Contiguous Allocation scheme
    2. Paging (and its illustration)
    3. Segmentation (and its illustration)
    4. Virtual Memory scheme for paging and segmentation
    • Question Pattern: There will be a question on illustration on any memory management scheme where the scenario is given.
  4. Current Knowledge of Any OS
    • Question Pattern: Here you will be asked to write a short note on any current OS of your choice. It will be a good idea to know about its advantages and limitations.

Reference Books:

Syllabus for Qualifying Examination of Artificial Intelligence

Topics:

  1. Introduction to AI, the foundations and the state of art of AI.
  2. Intelligent agents
    1. Agents and environments,
    2. The nature of environments, the structure of agents,
    3. Different type of agents.
  3. Solving problems by searching
    1. Problem solving agents, well defined problems and solutions, real world and different toy problems,
    2. Different search strategies like breadth first, depth first, depth limited, bidirectional, iterative deepening search.
  4. Informed search and exploration
    1. Heuristic search strategies,
    2. Greedy best first search, A* search,
    3. Heuristic functions,
    4. Local search algorithms and optimization problems like hill climbing, simulated annealing, local beam and genetic algorithms,
    5. Constraint satisfaction problems,
  5. Knowledge and reasoning or expert systems
    1. Logical agents and their properties
    2. Propositional Logic(PL), reasoning patterns in PL, resolution, forward and backward chaining, effective propositional inference,
    3. First order logic and semantics and syntax of first order logic,
    4. Quantifiers and knowledge engineering in first order logic,
    5. Inference in first order logic, forward backward chaining, the resolution inference rules, conjunctive normal forms etc.
  6. Learning
    1. Learning decision trees
    2. Neural Networks

Reference Book:

  • Artificial Intelligence: A Modern Approach. Stuart Russel and Peter Norvig. Pearson Education, 2nd Edition.
  • Artificial Intelligence. Elaine Rich and Kevin Knight. Mc GrawHill, 2nd Edition.

 

Syllabus for Qualifying Examination of Algorithms

Topics:

  1. Introduction to Algorithm and Flowchart. Illustrate best and worst case running time analysis of algorithm using Insertion Sort as an example
  2. Asymptotic analysis of algorithms: Big/small Oh, Big/small Omega, and Big/small Theta notations. Analyze worst case running time of different algorithms. Amortized analysis.
  3. Introduction to divide and conquer algorithms. Describe different divide & conquer (D&C) algorithms:
    1. Merge Sort,
    2. Quick Sort

    Methods for solving recurrence relations: substitution methods and recursion tree method

  4. Heap data structure and its operations/applications: MaxHeapify, BuildMaxHeap, HeapSort, etc. Analyzing running time of these algorithms
  5. Lower bound on the running time of comparison sorts. Linear time sorting algorithms: (i) Counting Sort, (ii) Radix Sort. Applicability and running time analysis of these algorithms.
  6. Dynamic programming (DP) algorithms, its properties and contrast them with greedy problems. Longest Common Subsequence problems and analysis of algorithms for solving these problems
  7. Major graph algorithms: BFS, DFS, TopologicalSorting, MST-KrusKal, MST-Prims, Dijkstra’s, and BellmanFord algorithms. Implementation, applications, and analysis of these algorithms.
  8. Unsolvable vs. Intractable problems, P vs. NP, Basic theory of NP Completeness, proving NP-completeness, approximation algorithms, approximation ratio

Reference Books:

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, “ Introduction to Algorithms”, 3rd , The MIT Press
  • Ellis Horwitz, Sartaz Sahni, “Computer Algorithms,” Silicon Pr; 2 edition
  • Christos Papadimitriou, Umesh Vazirani, Sanjoy Dasgupta, “Algorithms”, 1st
  • Éva Tardos, Jon Kleinberg, Algorithm Design, 1st

Syllabus for Qualifying Examination of Automata Theory

Topics:

  1. Alphabets and languages, string operations, formal languages
  2. Regular expressions (RE) and regular languages, operators of regular expressions, applications of regular expressions, pumping lemma for regular languages
  3. Deterministic and non-deterministic finite automata (DFA, NFA, ε-NFA), conversion between finite automata and regular expressions, conversion from ε-NFA to DFA, conversion between NFA and DFA, applications of finite automata
  4. Context-free grammars and languages (CFG and CFLs), Chomsky normal form (CNF), Parse trees, ambiguity in CFG and parse trees, applications of CFG, Pumpling Lemma for CFL
  5. Pushdown automata (PDA), language of a PDA. Acceptance by final state and acceptance by empty stack, equivalence of CFG and PDA
  6. Turing Machines (TMs), Computing with TM, Church-Turing thesis.
  7. Universal Turing Machines, halting problem.
  8. Computability, decidability, reducibility, Unrestricted and Context Sensitive Grammars and their corresponding languages, Chomsky’s Hierarchy of languages.
  9. Common types of computational problems: decision, search, counting, and optimization problems. Time and space complexity, hierarchy theorems, complexity classes P, NP, NPC, #P, L, NL, PSPACE, BPP and IP, complete problems, P versus NP.

Reference Books:

  • Harry Lewis & Christos Papadimitriou, “Elements of The Theory of Computation”, 2nd Edition
  • John Hopcroft, Rajeev Motwani, Jeffrey Ullman, “Introduction to Automata Theory, Languages, and Computation”, 3rd Edition