UGC NET Computer Science Discrete Structures and Optimization Syllabus

State the Binomial Theorem.

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

State the inclusion-exclusion principle for three sets.

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

What are the two steps of proof by Mathematical Induction?

Basis step: prove P(1) (or base case). Inductive step: assume P(k) and prove P(k+1). Then P(n) holds for all n ≥ base.

State Bayes' Theorem.

P(A|B) = P(B|A)·P(A) / P(B), where P(B) = Σ P(B|A_i)P(A_i) over a partition {A_i}.

For independent events A and B, what are P(A∩B) and the addition rule P(A∪B)?

P(A∩B) = P(A)·P(B); P(A∪B) = P(A) + P(B) − P(A)P(B).

What four axioms must a set with a binary operation satisfy to be a group?

Closure, Associativity, existence of an Identity element, and existence of an Inverse for every element.

Distinguish a semigroup, a monoid, and a group.

Semigroup: closure + associativity. Monoid: semigroup with an identity element. Group: monoid in which every element has an inverse.

State Lagrange's Theorem for finite groups.

The order of any subgroup H of a finite group G divides the order of G; i.e., |H| divides |G|.

Define a group homomorphism and an isomorphism.

A homomorphism f: G→H satisfies f(ab)=f(a)f(b). An isomorphism is a bijective homomorphism, making the two groups structurally identical.

What is an automorphism of a group?

An isomorphism from a group onto itself (a structure-preserving bijection G → G).

Define a ring (algebraic structure).

A set with two operations (+ and ·) where (R,+) is an abelian group, · is associative, and · distributes over +.

What distinguishes an integral domain and a field from a general commutative ring?

An integral domain is a commutative ring with unity and no zero divisors. A field additionally requires every nonzero element to have a multiplicative inverse.

What is the difference between a simple graph, a multigraph, and a weighted graph?

Simple graph: no loops or parallel edges. Multigraph: allows multiple (parallel) edges between vertices. Weighted graph: each edge carries a numeric weight.

State the Handshaking Theorem for graphs.

The sum of all vertex degrees equals twice the number of edges: Σ deg(v) = 2|E|. Hence the number of odd-degree vertices is even.

What is the condition for a connected graph to have an Eulerian circuit versus an Eulerian path?

Eulerian circuit exists iff every vertex has even degree. Eulerian path (not circuit) exists iff exactly two vertices have odd degree.

How does a Hamiltonian path/circuit differ from an Eulerian one?

A Hamiltonian path/circuit visits every vertex exactly once; an Eulerian path/circuit traverses every edge exactly once.

Which algorithm finds shortest paths from a single source in a weighted graph with non-negative weights, and its complexity?

Dijkstra's algorithm; O((V+E) log V) with a binary heap (O(V²) with an array).

State Euler's formula for connected planar graphs.

v − e + f = 2, where v = vertices, e = edges, f = faces (regions, including the outer one).

State the Four Color Theorem and define a graph's chromatic number.

Every planar graph is 4-colorable. The chromatic number χ(G) is the minimum number of colors needed to color vertices so no two adjacent vertices share a color.

What is the chromatic number of a bipartite graph, and how is bipartiteness characterized?

A bipartite graph has chromatic number 2 (or 1 if no edges). A graph is bipartite iff it contains no odd-length cycle.

For a tree with n vertices, how many edges does it have, and why?

Exactly n − 1 edges. A tree is connected and acyclic, so adding any edge creates a cycle and removing any disconnects it.

What property must a set of codewords satisfy to be a prefix code, and why is it useful?

No codeword is a prefix of another. This allows unambiguous (instantaneous) decoding without separators; Huffman coding builds optimal prefix codes.

List the three depth-first tree traversal orders and their order of visiting root.

Preorder: root, left, right. Inorder: left, root, right. Postorder: left, right, root.

What is a spanning tree, and which algorithms find a minimum spanning tree?

A spanning tree is a subgraph that is a tree connecting all vertices. Minimum spanning trees are found by Kruskal's and Prim's algorithms.

How are Boolean functions canonically represented in SOP and POS forms?

SOP (Sum of Products) = OR of minterms (where output is 1). POS (Product of Sums) = AND of maxterms (where output is 0).

What tool is commonly used to simplify Boolean functions, and what is its goal?

The Karnaugh map (K-map); it groups adjacent 1-cells into the largest power-of-two blocks to minimize the number of literals/terms (also Quine–McCluskey method).

What are the components of a Linear Programming mathematical model?

An objective function (to maximize/minimize), decision variables, and a set of linear constraints plus non-negativity restrictions.

In the graphical solution of an LP, where does the optimal solution occur?

At a corner (vertex/extreme point) of the feasible region; the optimum of a linear objective over a convex polygon lies at a vertex.

What is the role of the Simplex method and what does the Dual Simplex method handle?

Simplex iterates from vertex to vertex of the feasible region improving the objective until optimal. Dual Simplex maintains optimality while restoring feasibility, useful when the basis is optimal but infeasible (e.g., added constraints).

What does sensitivity analysis in LP study?

How changes in objective coefficients or right-hand-side (resource) values affect the optimal solution, including ranges over which the current basis stays optimal and shadow prices.

How does Integer Programming differ from Linear Programming?

Integer Programming requires some or all decision variables to take integer values, making it NP-hard; LP allows continuous values and is solvable in polynomial time.

In a balanced transportation problem, what is the relationship between supply and demand and the number of basic cells?

Total supply = total demand; a non-degenerate basic feasible solution has exactly m + n − 1 occupied (basic) cells for m sources and n destinations.

Which method solves the Assignment Model optimally, and what type of problem is it?

The Hungarian method; it solves the assignment problem (a special transportation/matching problem) of pairing n agents to n tasks at minimum total cost.

In PERT/CPM, what is the critical path?

The longest-duration path through the project network; it determines the minimum project completion time and has zero slack (float).

How is activity slack (float) calculated in CPM, and what does the PERT expected time formula give?

Slack = LS − ES = LF − EF. PERT expected time t_e = (optimistic + 4·most likely + pessimistic)/6.