UGC NET Computer Science Discrete Structures and Optimization Syllabus

Discrete Structures and Optimization syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Discrete Structures and Optimization in UGC NET Computer Science, not a summary of it.

1. 1

   Mathematical Logic

   6 topics

   • Propositional and Predicate Logic
   • Propositional Equivalences
   • Normal Forms
   • Predicates and Quantifiers
   • Nested Quantifiers
   • Rules of Inference
2. 2

   Sets and Relations

   4 topics

   • Set Operations
   • Representation and Properties of Relations
   • Equivalence Relations
   • Partially Ordering
3. 3

   Counting, Mathematical Induction and Discrete Probability

   7 topics

   • Basics of Counting
   • Pigeonhole Principle
   • Permutations and Combinations
   • Inclusion-Exclusion Principle
   • Mathematical Induction
   • Probability
   • Bayes’ Theorem
4. 4

   Group Theory

   11 topics

   • Groups
   • Subgroups
   • Semi Groups
   • Product and Quotients of Algebraic Structures
   • Isomorphism
   • Homomorphism
   • Automorphism
   • Rings
   • Integral Domains
   • Fields
   • Applications of Group Theory
5. 5

   Graph Theory

   14 topics

   • Simple Graph
   • Multigraph
   • Weighted Graph
   • Paths and Circuits
   • Shortest Paths in Weighted Graphs
   • Eulerian Paths and Circuits
   • Hamiltonian Paths and Circuits
   • Planner graph
   • Graph Coloring
   • Bipartite Graphs
   • Trees and Rooted Trees
   • Prefix Codes
   • Tree Traversals
   • Spanning Trees and Cut-Sets
6. 6

   Boolean Algebra

   2 topics

   • Boolean Functions and its Representation
   • Simplifications of Boolean Functions
7. 7

   Optimization

   10 topics

   • Linear Programming - Mathematical Model
   • Graphical Solution
   • Simplex and Dual Simplex Method
   • Sensitive Analysis
   • Integer Programming
   • Transportation and Assignment Models
   • PERT-CPM: Diagram Representation
   • Critical Path Calculations
   • Resource Levelling
   • Cost Consideration in Project Scheduling

Discrete Structures and Optimization flashcards for UGC NET Computer Science

21 of 55 cards from the Discrete Structures and Optimization deck — real questions with worked answers.

1. In propositional logic, when is a conditional statement p → q false?

   Only when p is true and q is false. In all other cases (T→T, F→T, F→F) it is true.

2. State the logical equivalence for the contrapositive, and why it matters.

   p → q ≡ ¬q → ¬p. A conditional and its contrapositive are logically equivalent, so proving one proves the other.

3. What are the two De Morgan's laws for propositions?

   ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q.

4. Define tautology, contradiction, and contingency.

   A tautology is always true, a contradiction is always false, and a contingency is sometimes true and sometimes false depending on truth values.

5. What is the difference between Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF)?

   DNF is a disjunction (OR) of conjunctive clauses (sum of products); CNF is a conjunction (AND) of disjunctive clauses (product of sums).

6. What is the negation of the quantified statement ∀x P(x)?

   ¬∀x P(x) ≡ ∃x ¬P(x). The negation of a universal is an existential of the negation (De Morgan for quantifiers).

7. In nested quantifiers, does ∀x ∃y P(x,y) mean the same as ∃y ∀x P(x,y)?

   No. ∀x ∃y allows y to depend on x; ∃y ∀x requires a single y that works for all x. ∃y∀x ⇒ ∀x∃y, but not the reverse.

8. State the rules of inference Modus Ponens and Modus Tollens.

   Modus Ponens: from p → q and p, infer q. Modus Tollens: from p → q and ¬q, infer ¬p.

9. What does the rule of Hypothetical Syllogism state?

   From p → q and q → r, infer p → r (transitivity of implication).

10. State the inclusion-exclusion formula for the union of two sets.

    |A ∪ B| = |A| + |B| − |A ∩ B|.

11. What is the formula for the number of subsets (power set size) of a set with n elements?

    2^n.

12. Define the symmetric difference of sets A and B.

    A △ B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B): elements in exactly one of the two sets.

13. What are the three properties that define an equivalence relation?

    Reflexive, Symmetric, and Transitive.

14. What does an equivalence relation on a set produce?

    A partition of the set into disjoint equivalence classes whose union is the whole set.

15. What three properties define a partial order relation?

    Reflexive, Antisymmetric, and Transitive.

16. In a poset, what is the difference between a maximal element and a greatest (maximum) element?

    A maximal element has nothing strictly above it; a greatest element is ≥ every element. A greatest element is unique and maximal, but a maximal element need not be greatest.

17. How many ways can a relation on a set of n elements be? (count of relations)

    2^(n²), since a relation is any subset of the n×n set of ordered pairs.

18. State the product rule and sum rule of counting.

    Product rule: if a task has k steps with n₁,…,n_k choices, total = n₁·n₂·…·n_k. Sum rule: for mutually exclusive alternatives, total = n₁ + n₂ + … + n_k.

19. State the Pigeonhole Principle (generalized form).

    If N objects are placed into k boxes, then at least one box contains ⌈N/k⌉ objects.

20. Give the formulas for permutations P(n,r) and combinations C(n,r).

    P(n,r) = n!/(n−r)!; C(n,r) = n!/[r!(n−r)!].

21. State the Binomial Theorem.

    (x + y)^n = Σ_{k=0}^{n} C(n,k) x^{n−k} y^k.

See more Discrete Structures and Optimization flashcards →

Planning Discrete Structures and Optimization for UGC NET Computer Science

Discrete Structures and Optimization (UGC NET Computer Science) FAQ