Examius
🇮🇳 UGC NET Computer Science · flashcards
UGC NET Computer Science Discrete Structures and Optimization Flashcards
55 question-and-answer cards covering Discrete Structures and Optimization as it is examined in UGC NET Computer Science. 24 of them are printed below, taken from across the deck — no signup, no paywall on the preview.
24 sample cards from the Discrete Structures and Optimization deck
Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.
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.
What this deck covers
The Discrete Structures and Optimization deck follows the UGC NET Computer Science Discrete Structures and Optimization syllabus — 7 chapters and 54 topics — so questions land on material that is genuinely examinable rather than trivia around it. That works out to roughly 7.9 cards per chapter.
Answers are written to be recallable, not just readable — averaging about 137 characters, which is long enough to carry the reasoning and short enough to say out loud.
A deck like this earns its keep on the second and third pass. Read the syllabus first so you know the shape of the subject, then use the cards to find the specific facts that have not stuck.
Discrete Structures and Optimization flashcards FAQ
How many Discrete Structures and Optimization flashcards are in this UGC NET Computer Science deck?
55 cards. This page previews 24 of them, sampled evenly across the deck so you can judge the difficulty before installing anything.
Are these UGC NET Computer Science flashcards free?
Yes. The preview here is free to read with no signup, and the full 55-card deck is free inside the Examius app.
What do the Discrete Structures and Optimization cards cover?
They follow the UGC NET Computer Science Discrete Structures and Optimization syllabus — 7 chapters and 54 topics — so the questions track what is actually examinable.
How should I use these flashcards?
Read the syllabus first so you know the shape of the subject, then drill the deck. Examius schedules each card with spaced repetition, so cards you keep missing come back sooner and ones you know drift further apart.