Skip to content
JNTUK · B.Tech study libraryFree access · No sign-up
JNTUK · R23 · CSE · Semester 2-1

Advanced Data Structures & Algorithm Analysis exam preparation.

Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.

  • Practice questions in the exam's style
  • Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
Units
5
Questions
60
2-mark
30
10-mark
30
Checked on

Exam guide

Paper pattern

Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.

  1. Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
  2. Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
  • The semester-end examination carries 70 marks; internal assessment carries 30.
  • Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
  • The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.

Read the R23 regulations (PDF) ↗

How to split your time

This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.

  1. 10 minRead the paper and choose one option in each either/or question
  2. 30 minQuestion 1: ten short answers (about 3 minutes each)
  3. 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
  4. 10 minFinal check of numbering, calculations and diagrams

Study tips for Advanced Data Structures & Algorithm Analysis

  • Practise AVL and B-tree insertions and deletions by hand on short key sequences, redrawing the whole tree after every step and labelling each node's balance factor or key count. That way a wrong rotation or a missed split is caught at the step where it happens.
  • For divide and conquer analysis, write the recurrence first, then solve it both by the master theorem and by drawing the recursion tree level by level. Check that the two methods give the same order of growth, such as O(n log n) for merge sort.
  • When solving dynamic programming problems like 0/1 knapsack, optimal binary search trees, string editing or all-pairs shortest paths, fill the table cell by cell in a neat grid and write the recurrence used beside it. Then trace back through the table to recover the actual solution, not just the optimal value.
  • For backtracking and branch and bound problems such as 8-queens, sum of subsets or the travelling salesperson, draw the state space tree and mark pruned nodes and the bounds at each level. Beside each tree, write short pseudocode from memory, indented or boxed, so the logic is clear.
Unit 1

Algorithm Analysis, AVL Trees and B-Trees

Syllabus: Introduction to algorithm analysis; Space and time complexity analysis; Asymptotic notations; AVL trees: creation; AVL tree insertion and deletion; Applications of AVL trees; B-trees: creation; B-tree insertion and deletion; Applications of B-trees

One-page revision summary

  • An algorithm is a finite, definite and effective sequence of steps, and algorithm analysis predicts its time and memory needs independently of hardware.
  • Best, worst and average cases describe running time on the most favourable, least favourable and typical inputs of size n.
  • The frequency count method multiplies each statement's step cost by its execution count and adds the results; the dominant term gives the order of growth.
  • Space complexity S(P) = c + Sp(n) is a fixed part plus a variable part that includes arrays sized by n and the recursion stack.
  • Big-O gives an upper bound, Omega a lower bound and Theta a tight bound; little-o and little-omega are strict versions defined by limits.
  • Common growth rates in increasing order are 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!.
  • An AVL tree is a BST in which every node's balance factor is −1, 0 or +1, so its height is O(log n).
  • An AVL tree is created by repeated insertion: a BST insert, an update of balance factors, then a rotation at the first node whose BF becomes ±2.
  • LL and RR imbalances need a single rotation, while LR and RL imbalances need a double rotation; an insertion needs at most one single or double rotation.
  • AVL deletion removes the key as in a BST and may need rotations at several ancestors up to the root.
  • AVL trees suit in-memory, search-heavy uses such as compiler symbol tables, ordered sets and maps.
  • A B-tree of order m is created by inserting keys into an initially empty root leaf and splitting any node that overflows.
  • B-tree insertion splits a full node at its median, which moves up; a root split increases the height by one.
  • B-tree deletion uses direct removal, replacement by predecessor or successor, borrowing from a sibling and merging with a sibling; a merge at the root decreases the height.
  • B-trees are used for database indexes (mostly B+-trees) and file systems because wide nodes match disk blocks and keep disk accesses few.

Learn these by heart

  • f(n) = O(g(n)) ⇔ ∃ c > 0, n0 such that f(n) ≤ c·g(n) ∀ n ≥ n0. Ω uses ≥ instead, and Θ needs both bounds: c1·g(n) ≤ f(n) ≤ c2·g(n).
  • Balance factor BF = height(left) − height(right), and it must lie in {−1, 0, +1} for every AVL node.
  • Rotation choice: LL → right rotation, RR → left rotation, LR → left then right, RL → right then left.
  • A B-tree of order m has at most m children and m − 1 keys per node, and at least ⌈m/2⌉ − 1 keys per non-root node. The root has at least 1 key, and all leaves are on the same level.
  • The height of a B-tree with n keys and t = ⌈m/2⌉ satisfies h ≤ log_t((n + 1)/2).
  • Space complexity S(P) = c + Sp(n), where c is the fixed part and Sp(n) is the variable part.

2-mark questions

1 Define an algorithm and list its essential characteristics. 2 marks
Model answer

An algorithm is a finite sequence of well-defined instructions that solves a given problem. Its essential characteristics are:

  • Input: zero or more inputs.
  • Output: at least one output.
  • Definiteness: every step is unambiguous.
  • Finiteness: it stops after a finite number of steps.
  • Effectiveness: every step is basic enough to be carried out exactly.
2 Distinguish between time complexity and space complexity of an algorithm. 2 marks
Model answer

Time complexity is the computing time an algorithm needs, expressed as a function of the input size n. It is usually measured by counting basic operations.

Space complexity is the total memory the algorithm needs. It has a fixed part (code, constants, simple variables) and a variable part (arrays whose size depends on n, dynamic memory, the recursion stack).

3 Show that f(n) = 3n + 2 is O(n). 2 marks
Model answer

We need constants c and n0 such that 3n + 2 ≤ c·n for all n ≥ n0.

For n ≥ 2 we have 2 ≤ n, so 3n + 2 ≤ 3n + n = 4n.

Taking c = 4 and n0 = 2 satisfies the definition. Hence 3n + 2 = O(n).

4 What is the balance factor of a node in an AVL tree? What values are allowed? 2 marks
Model answer

The balance factor of a node is BF(node) = height(left subtree) − height(right subtree).

In an AVL tree every node must have BF equal to −1, 0 or +1. If an insertion or deletion makes some node's BF +2 or −2, that node is rebalanced by a single or double rotation.

5 State the properties of a B-tree of order m. 2 marks
Model answer
  • Every node has at most m children and at most m − 1 keys.
  • Every non-root internal node has at least ⌈m/2⌉ children.
  • Every non-root node has at least ⌈m/2⌉ − 1 keys.
  • The root has at least 2 children unless it is a leaf.
  • All leaves are on the same level.
  • Keys inside a node are sorted and separate the key ranges of its subtrees.
6 Give two applications each of AVL trees and B-trees. 2 marks
Model answer

AVL trees:

  • Symbol tables in compilers.
  • In-memory ordered dictionaries and sets where searches dominate, since lookup is guaranteed O(log n).

B-trees:

  • Database indexes, usually the B+-tree variant.
  • File-system directory and metadata indexes.

B-trees suit these storage uses because one wide node fits a disk block, which keeps disk accesses few.

10-mark questions

1 Define the asymptotic notations Big-O, Omega, Theta, little-o and little-omega. For f(n) = 3n² + 2n + 5, prove that f(n) = Θ(n²) by finding suitable constants. 10 marks
Model answer

Asymptotic notations describe how the running time or space of an algorithm grows as the input size n becomes large. They ignore constant factors and lower-order terms. Let f(n) and g(n) be non-negative functions.

1. Big-O (upper bound): f(n) = O(g(n)) if there exist positive constants c and n0 such that f(n) ≤ c·g(n) for all n ≥ n0. It is commonly used for worst-case statements.

2. Omega (lower bound): f(n) = Ω(g(n)) if there exist c > 0 and n0 such that f(n) ≥ c·g(n) for all n ≥ n0.

3. Theta (tight bound): f(n) = Θ(g(n)) if there exist c1, c2 > 0 and n0 such that c1·g(n) ≤ f(n) ≤ c2·g(n) for all n ≥ n0. Equivalently, f = O(g) and f = Ω(g).

4. Little-o (strict upper bound): f(n) = o(g(n)) if lim (n→∞) f(n)/g(n) = 0. For example, n = o(n²).

5. Little-omega (strict lower bound): f(n) = ω(g(n)) if lim (n→∞) f(n)/g(n) = ∞. For example, n² = ω(n).

Proof that f(n) = 3n² + 2n + 5 = Θ(n²):

Step 1 (upper bound). For n ≥ 1 we have n ≤ n² and 1 ≤ n². Hence 3n² + 2n + 5 ≤ 3n² + 2n² + 5n² = 10n². So c2 = 10, n0 = 1, and f(n) = O(n²).

Step 2 (lower bound). For n ≥ 1, 2n + 5 > 0, so 3n² + 2n + 5 ≥ 3n². So c1 = 3, n0 = 1, and f(n) = Ω(n²).

Step 3 (combine). 3n² ≤ f(n) ≤ 10n² for all n ≥ 1. Therefore f(n) = Θ(n²) with c1 = 3, c2 = 10 and n0 = 1.

Check at n = 2: f(2) = 12 + 4 + 5 = 21. Also 3·4 = 12 and 10·4 = 40, and 12 ≤ 21 ≤ 40 holds.

Diagram in words: A graph has input size n on the horizontal axis and time on the vertical axis. It shows three rising curves: the lowest is 3n², the middle one is f(n) and the highest is 10n². A vertical dashed line labelled n0 = 1 is drawn; to the right of it, f(n) always stays between the two bounding curves.

Common growth rates, in increasing order: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!.

In conclusion, O gives an upper bound, Ω a lower bound and Θ an exact order of growth. The function 3n² + 2n + 5 grows quadratically, so f(n) = Θ(n²).

2 Explain how the time and space complexity of an algorithm are analysed. Using the frequency count (step count) method, find the time and space complexity of an algorithm that adds two n × n matrices. 10 marks
Model answer

Analysing an algorithm means predicting the resources it needs before running it. This lets different solutions be compared independently of the machine and the language. The two main resources are time and memory.

Time complexity. Running time is measured by counting basic steps as a function of the input size n. In the frequency count method:

  • each statement gets a step count (1 for a simple assignment or comparison);
  • this count is multiplied by the number of times the statement executes;
  • the products are added, and the dominant term gives the order of growth.

The count can also depend on the actual input, so we separate best, worst and average cases. For linear search the best case is 1 comparison, the worst case is n comparisons, and a successful search needs about (n + 1)/2 comparisons on average.

Space complexity. S(P) = c + Sp(n). Here c is the fixed part (instructions, constants, simple variables). Sp(n) is the variable part (arrays sized by n, dynamic memory, the recursion stack).

Example: matrix addition.

Algorithm MatAdd(A, B, C, n)
1  for i := 1 to n do
2      for j := 1 to n do
3          C[i][j] := A[i][j] + B[i][j];

Step 1. Line 1: the loop test is true n times and false once, giving n + 1.

Step 2. Line 2: for each of the n values of i, the inner test runs n + 1 times, giving n(n + 1) = n² + n.

Step 3. Line 3: it runs once for every (i, j) pair, giving n².

Step 4. Total T(n) = (n + 1) + (n² + n) + n² = 2n² + 2n + 1.

Step 5. The dominant term is 2n², so T(n) = O(n²). Since T(n) ≥ 2n², it is also Θ(n²).

Check for n = 2: line 1 runs 3 times, line 2 runs 6 times and line 3 runs 4 times. The total is 13, and 2·4 + 2·2 + 1 = 13.

Space analysis:

  • Matrices A, B and C need 3n² words (variable part).
  • Simple variables i, j and n need 3 words (fixed part).
  • So S(n) = 3n² + 3, and the space complexity is Θ(n²).
  • The auxiliary space, beyond the input and output matrices, is only i and j, which is O(1).

In conclusion, frequency counting gives the exact step formula 2n² + 2n + 1. Asymptotic notation reduces this to Θ(n²) time and Θ(n²) total space for matrix addition.

3 Construct an AVL tree by inserting the keys 10, 20, 30, 40, 50, 25 in that order. Show the balance factors and name each rotation used. 10 marks
Model answer

An AVL tree is a height-balanced binary search tree. For every node, BF = height(left) − height(right) must be −1, 0 or +1. Each key is first inserted as in an ordinary BST. The balance factors are then updated on the way back to the root, and the first node with BF = ±2 is repaired by a rotation. Here a leaf has height 1 and an empty subtree has height 0.

Step 1: Insert 10. The tree is the single node 10, with BF(10) = 0.

Step 2: Insert 20. Since 20 > 10, it becomes the right child of 10. BF(10) = −1, so the tree is balanced.

Step 3: Insert 30. It goes to the right of 20. BF(20) = −1 and BF(10) = 0 − 2 = −2. The new key lies in the right subtree of the right child, which is the RR case. A single left rotation at 10 gives 20 with left child 10 and right child 30; all BFs are 0.

Step 4: Insert 40. The path is 20 → 30 → right. BF(30) = −1 and BF(20) = 1 − 2 = −1, so the tree is balanced.

Step 5: Insert 50. The path is 20 → 30 → 40 → right. BF(40) = −1 and BF(30) = −2, which is the RR case again.

  • A left rotation at 30 makes 40 the parent of 30 and 50.
  • The tree is now 20 (left 10, right 40), with 40 (left 30, right 50).
  • BF(40) = 0 and BF(20) = 1 − 2 = −1.

Step 6: Insert 25. Since 25 > 20, go right; 25 < 40, go left; 25 < 30, so 25 becomes the left child of 30. Now BF(30) = +1, BF(40) = 2 − 1 = +1 and BF(20) = 1 − 3 = −2. The key went right of 20 and then left of 40, which is the RL case and needs a double rotation.

  • First, a right rotation at 40: 30 moves up as the right child of 20, with 25 as its left child and 40 as its right child. 40 keeps 50 as its right child.
  • Then, a left rotation at 20: 30 becomes the root and 20 becomes its left child. 30's former left child 25 becomes the right child of 20.

Final balance factors:

  • 30: left height 2, right height 2, so BF = 0.
  • 20: children 10 and 25, so BF = 0.
  • 40: only a right child 50, so BF = −1.
  • 10, 25 and 50 are leaves, so BF = 0.
Final AVL tree after inserting 10, 20, 30, 40, 50, 25Diagram in words: The root node 30 has a left edge to node 20 and a right edge to node 40. Node 20 has a left edge to leaf 10 and a right edge to leaf 25. Node 40 has no left child and a right edge to leaf 50. Each node is labelled with its balance factor: 30(0), 20(0), 40(−1), 10(0), 25(0), 50(0).30 (BF 0)20 (BF 0)40 (BF −1)10 (BF 0)25 (BF 0)50 (BF 0)
Final AVL tree after inserting 10, 20, 30, 40, 50, 25

The inorder traversal is 10, 20, 25, 30, 40, 50, which confirms that BST order is preserved.

In conclusion, two RR single rotations and one RL double rotation were needed. The final AVL tree has height 3, and every balance factor lies in {−1, 0, +1}.

4 Explain the four rotations used to rebalance an AVL tree. Describe the AVL deletion procedure with a suitable example and list the applications of AVL trees. 10 marks
Model answer

AVL trees stay balanced through rotations. A rotation changes a few pointers in O(1) time and keeps the inorder (BST) order. Let A be the nearest ancestor whose balance factor becomes ±2, and let B be its taller child.

1. LL case (BF(A) = +2, B is the left child and is left-heavy or even): a single right rotation at A. B becomes the subtree root, A becomes B's right child, and B's old right subtree becomes A's left subtree.

2. RR case (BF(A) = −2, B is the right child): a single left rotation at A, the mirror image of LL.

3. LR case (BF(A) = +2, B is the left child and is right-heavy): a left rotation at B, then a right rotation at A.

4. RL case (BF(A) = −2, B is the right child and is left-heavy): a right rotation at B, then a left rotation at A.

Deletion procedure:

Step 1. Delete as in a BST. A leaf is removed directly. A node with one child is replaced by that child. A node with two children is replaced by its inorder successor, which is then removed from its old place.

Step 2. Move from the parent of the removed node up to the root, recomputing heights and balance factors.

Step 3. At a node with BF = +2, look at its left child L. If BF(L) is 0 or +1, apply a right rotation (the R0 or R1 case). If BF(L) = −1, apply an LR double rotation. For BF = −2, use the mirror rules. A rotation may reduce the subtree height, so several rotations, up to O(log n), may be needed.

Example: The root 20 has left child 10 and right child 30, and 10 has children 5 and 15. Delete 30.

  • 30 is a leaf, so it is removed.
  • BF(20) = 2 − 0 = +2, and its left child 10 has BF 0, so this is the R0 case: a right rotation at 20.
  • 10 becomes the root with left child 5 and right child 20. 15, the old right child of 10, becomes the left child of 20.
  • The new BFs are 10 = 1 − 2 = −1, 20 = +1, 5 = 0 and 15 = 0, so the tree is balanced.
AVL deletion of 30: before and after the right rotation at 20Diagram in words: Before deletion, root 20 has a left edge to 10 and a right edge to 30, and 10 has a left edge to 5 and a right edge to 15. After deletion and the right rotation, root 10 has a left edge to 5 and a right edge to 20, and 20 has a left edge to 15 and no right child.Before deletionAfter right rotation2010305151052015leftrightleftrightleftrightleft
AVL deletion of 30: before and after the right rotation at 20

Applications of AVL trees:

  • Symbol tables in compilers and interpreters.
  • In-memory dictionaries, ordered sets and maps where searches dominate updates.
  • In-memory indexing and range queries on data held in RAM.

In conclusion, the four rotations keep the height below about 1.44 log₂ n after both insertion and deletion, so search, insert and delete all run in O(log n).

5 Explain the insertion algorithm for a B-tree of order m. Construct a B-tree of order 5 by inserting the keys 8, 14, 2, 15, 3, 1, 16, 6, 5, 27, 37, 18, 25, 20, 30, 32, 40 in that order. 10 marks
Model answer

A B-tree of order m is a balanced multiway search tree. Each node holds at most m − 1 sorted keys and m children. Every non-root node holds at least ⌈m/2⌉ − 1 keys, and all leaves lie on the same level. For m = 5, a node holds at most 4 keys, and every non-root node holds at least 2.

Insertion algorithm: 1. Search from the root to find the leaf where the key belongs. 2. Insert the key into that leaf in sorted position. 3. If the leaf now has m keys (overflow), split it. The median key moves up into the parent; the smaller keys form the left node and the larger keys form the right node. 4. If the parent overflows, split it in the same way. If the root splits, a new root is created and the height grows by one.

Construction:

Step 1. Insert 8, 14, 2, 15. The root leaf is [2, 8, 14, 15].

Step 2. Insert 3. The node [2, 3, 8, 14, 15] overflows, and the median 8 moves up. The root is [8], with children [2, 3] and [14, 15].

Step 3. Insert 1, 16, 6. The leaves become [1, 2, 3, 6] and [14, 15, 16].

Step 4. Insert 5. The leaf [1, 2, 3, 5, 6] overflows, and the median 3 moves up. The root is [3, 8], with leaves [1, 2], [5, 6] and [14, 15, 16].

Step 5. Insert 27, 37. The leaf [14, 15, 16, 27, 37] overflows, and the median 16 moves up. The root is [3, 8, 16], with leaves [1, 2], [5, 6], [14, 15] and [27, 37].

Step 6. Insert 18 and 25, giving the leaf [18, 25, 27, 37]. Insert 20: [18, 20, 25, 27, 37] overflows, and the median 25 moves up. The root is [3, 8, 16, 25], with leaves [1, 2], [5, 6], [14, 15], [18, 20] and [27, 37].

Step 7. Insert 30 and 32, giving the leaf [27, 30, 32, 37]. Insert 40: [27, 30, 32, 37, 40] overflows, and the median 32 moves up, leaving leaves [27, 30] and [37, 40].

  • The root [3, 8, 16, 25, 32] now overflows, and its median 16 moves up into a new root.
  • The left internal node is [3, 8] and the right internal node is [25, 32].
  • The height grows from 2 to 3.
B-tree of order 5 after inserting all 17 keysDiagram in words: The root node [16] has a left link to internal node [3, 8] and a right link to internal node [25, 32]. Node [3, 8] has three links, from left to right, to leaves [1, 2], [5, 6] and [14, 15]. Node [25, 32] has three links, from left to right, to leaves [18, 20], [27, 30] and [37, 40]. All six leaves are on the same level.163 | 825 | 321 | 25 | 614 | 1518 | 2027 | 3037 | 40
B-tree of order 5 after inserting all 17 keys

Check: the inorder traversal gives all 17 keys in sorted order: 1, 2, 3, 5, 6, 8, 14, 15, 16, 18, 20, 25, 27, 30, 32, 37, 40. Every non-root node holds exactly 2 keys, so the minimum is satisfied.

In conclusion, a B-tree grows upward by splitting at the root. This keeps all leaves at the same depth and the height O(log_m n).

6 Explain the cases of deletion in a B-tree and list the applications of B-trees. For the following B-tree of order 5, delete 8, 18 and 1 in that order, showing the tree after each deletion. Tree: the root is [16] with children [3, 8] and [25, 32]; node [3, 8] has leaves [1, 2], [5, 6, 7], [13, 14]; node [25, 32] has leaves [18, 20], [27, 30, 31], [37, 40]. 10 marks
Model answer

In a B-tree of order 5, every non-root node must keep at least ⌈5/2⌉ − 1 = 2 keys. Deletion must therefore repair any node that falls below this minimum, which is called underflow.

Deletion cases: 1. The key is in a leaf with more than the minimum number of keys: simply remove it. 2. The key is in an internal node: replace it by its inorder predecessor (largest key in the left subtree) or successor (smallest key in the right subtree), then delete that key from its leaf. 3. Underflow, and an adjacent sibling has more than the minimum: borrow. The separating key in the parent moves down into the deficient node, and the sibling's nearest key moves up into the parent. 4. Underflow, and the siblings have only the minimum: merge the node, the separating parent key and a sibling into one node. The parent loses a key and may underflow in turn. If the root becomes empty, its only child becomes the new root and the height decreases.

Delete 8 (case 2): 8 is in the internal node [3, 8]. Its predecessor is 7, in the leaf [5, 6, 7]. That leaf has 3 keys, so 7 can safely replace 8. The node becomes [3, 7] and the leaf becomes [5, 6].

Delete 18 (case 3): the leaf [18, 20] becomes [20], which is an underflow. The right sibling [27, 30, 31] has 3 keys, so we borrow.

  • The parent key 25 moves down, giving the leaf [20, 25].
  • The key 27 moves up into the parent, giving [27, 32].
  • The leaves under [27, 32] are now [20, 25], [30, 31] and [37, 40].

Delete 1 (case 4, cascading): the leaf [1, 2] becomes [2]. Its only sibling [5, 6] has just 2 keys.

  • Merge [2], the parent key 3 and [5, 6] into [2, 3, 5, 6].
  • The parent [3, 7] drops to [7], which is an underflow.
  • Its sibling [27, 32] has only 2 keys, so merge again: [7], the root key 16 and [27, 32] form [7, 16, 27, 32].
  • The root is now empty and is removed, so the height decreases from 3 to 2.
B-tree of order 5 after deleting 8, 18 and 1Diagram in words: The final root [7, 16, 27, 32] has five links, from left to right, to leaves [2, 3, 5, 6], [13, 14], [20, 25], [30, 31] and [37, 40]. All leaves are on one level, and each holds between 2 and 4 keys.7 | 16 | 27 | 322 | 3 | 5 | 613 | 1420 | 2530 | 3137 | 40
B-tree of order 5 after deleting 8, 18 and 1

Applications of B-trees:

  • Database indexes, usually the B+-tree variant, for fast search and range queries.
  • File-system indexes for directories and for locating file blocks.
  • Any large on-disk dictionary. One node fits one disk block, and the large fan-out keeps the height, and hence the number of disk reads, very small.

In conclusion, B-tree deletion combines removal, replacement, borrowing and merging. Merging can travel up to the root and shrink the tree, but all leaves always stay at the same depth.

Unit 2

Heaps, Graphs and Divide and Conquer

Syllabus: Heap trees as priority queues: min and max heaps; Heap operations and applications; Graph terminology; Graph representations; Basic search and traversals; Connected components; Biconnected components; Applications of graphs; Divide and conquer: the general method; Quick sort; Merge sort; Strassen's matrix multiplication; Convex hull

One-page revision summary

  • A heap is a complete binary tree with the heap-order property that gives O(log n) insert and delete-max (or delete-min) and O(1) find-max, so it is the natural priority queue used in heap sort, CPU and job scheduling, Dijkstra's and Prim's algorithms, Huffman coding and finding the k largest elements.
  • A graph G = (V, E) may be directed or undirected, its key terms are degree (in-degree and out-degree for digraphs), path, simple path, cycle, subgraph and connected graph, and a complete undirected graph on n vertices has n(n−1)/2 edges while a tree on n vertices has exactly n−1 edges and no cycle.
  • Graphs can be stored as an adjacency matrix (O(n²) space), as adjacency lists (O(n+e) space), or as an adjacency multilist or incidence representation.
  • BFS uses a queue and finds shortest paths by number of edges, while DFS uses recursion or a stack and is the basis for cycle detection, topological sorting and finding articulation points.
  • Connected components are found by starting a new BFS or DFS from each still-unvisited vertex, each search marking exactly one component, in O(V + E) total time.
  • A biconnected graph has no articulation point, and its biconnected components partition the edges and meet only at cut vertices.
  • In transport and communication systems, graphs model road maps where Dijkstra's algorithm gives shortest routes, computer networks where cut vertices and biconnected components reveal single points of failure, and cable or pipeline layouts where a minimum spanning tree (Prim or Kruskal) gives the cheapest connection.
  • In computing and society, graphs model social networks where BFS levels give degrees of separation and friend suggestions, task or course prerequisites where a topological order of the DAG gives a valid schedule, the web where crawlers traverse hyperlinks by BFS, and compilers where dependency and call graphs are analysed for cycles.
  • Divide and conquer divides a problem into smaller subproblems, conquers them recursively, solves very small cases directly and combines the results, with quick sort doing its work in the divide (partition) step and merge sort in the combine (merge) step.
  • Strassen's method splits each n×n matrix into four n/2 × n/2 blocks and computes seven products: M1=(A11+A22)(B11+B22), M2=(A21+A22)B11, M3=A11(B12−B22), M4=A22(B21−B11), M5=(A11+A12)B22, M6=(A21−A11)(B11+B12), M7=(A12−A22)(B21+B22).
  • Strassen's result blocks are C11=M1+M4−M5+M7, C12=M3+M5, C21=M2+M4 and C22=M1−M2+M3+M6.
  • For A = [[1,2],[3,4]] and B = [[5,6],[7,8]], Strassen gives M1=65, M2=35, M3=−2, M4=8, M5=24, M6=22, M7=−30, so C11=65+8−24−30=19, C12=−2+24=22, C21=35+8=43 and C22=65−35−2+22=50, matching ordinary row-by-column multiplication.
  • Solving T(n) = 7T(n/2) + cn² by unrolling, level i costs cn²(7/4)^i, so the geometric sum up to level log₂n is dominated by its last term cn²·(7/4)^(log₂n) = c·n^(log₂7), giving O(n^2.81), which Master theorem case 1 (n^(log₂7) grows faster than n²) confirms.
  • Ordinary block divide and conquer needs eight half-size products, T(n) = 8T(n/2) + cn² = O(n³), so Strassen's saving of one multiplication per level is what lowers the exponent to log₂7 ≈ 2.81.
  • The convex hull is the smallest convex polygon enclosing all given points, with corners taken from the input, and QuickHull starts by joining the leftmost and rightmost points, which always lie on the hull, to split the remaining points into an upper set and a lower set.
  • On each side, QuickHull adds the point farthest from the dividing line to the hull, discards every point inside the triangle formed by that point and the line's two ends, and recurses on the two new outer edges until no points remain outside.
  • The orientation of points p1, p2, p3 is the sign of (x2−x1)(y3−y1) − (y2−y1)(x3−x1), where positive means a left (counter-clockwise) turn, negative a right turn and zero collinear, and this test decides which side of a line each point lies on.
  • For points (0,0), (1,1), (2,3), (3,1), (4,0) and (2,−2), QuickHull splits on the line from (0,0) to (4,0), picks (2,3) as farthest above so (1,1) and (3,1) fall inside the triangle and are dropped, picks (2,−2) below, and returns the counter-clockwise hull (0,0), (2,−2), (4,0), (2,3).
  • The merge-based hull sorts points by x-coordinate, splits them at the median into left and right halves, builds both hulls recursively and joins them in O(n) by finding the upper and lower common tangents, giving T(n) = 2T(n/2) + O(n) = O(n log n).
  • QuickHull satisfies T(n) = T(n1) + T(n2) + O(n) with n1 + n2 ≤ n, so it runs in O(n log n) when the splits are balanced but degrades to O(n²) when the farthest point repeatedly leaves almost all remaining points on one side.

Learn these by heart

  • Heap in array a[1..n]: parent(i) = ⌊i/2⌋, left(i) = 2i, right(i) = 2i+1. Insert and delete take O(log n), and building a heap bottom-up takes O(n).
  • Handshaking lemma: the sum of the degrees of all vertices = 2|E|.
  • BFS and DFS take O(V + E) time with adjacency lists and O(V²) with an adjacency matrix.
  • low(u) = min{dfn(u), low(w) for each child w, dfn(x) for each back edge (u,x)}. A non-root u is a cut vertex if some child w has low(w) ≥ dfn(u). The root is a cut vertex if it has two or more tree children.
  • Divide and conquer recurrence: T(n) = aT(n/b) + f(n); compare f(n) with n^(log_b a) to apply the Master theorem.
  • Merge sort: T(n) = 2T(n/2) + cn = O(n log n) in all cases. Quick sort: O(n log n) on average and O(n²) in the worst case, with about n(n−1)/2 comparisons on sorted input.
  • Strassen: T(n) = 7T(n/2) + cn² = O(n^log₂7) ≈ O(n^2.81), using 7 multiplications and 18 additions or subtractions, against 8 multiplications and O(n³) for plain block multiplication.
  • Check any Strassen example against ordinary multiplication: for A = [[1,2],[3,4]] and B = [[5,6],[7,8]] the product must be [[19,22],[43,50]].
  • QuickHull: O(n log n) on average and O(n²) in the worst case; the merge-based hull: T(n) = 2T(n/2) + O(n) = O(n log n) always.
  • Match application to algorithm: shortest route → Dijkstra, cheapest network → minimum spanning tree, single point of failure → articulation points, valid schedule → topological sort, fewest hops → BFS.

2-mark questions

1 Define min heap and max heap. 2 marks
Model answer

A heap is a complete binary tree usually stored in an array. In a max heap, every parent key is greater than or equal to the keys of its children, so the root holds the maximum. In a min heap, every parent key is less than or equal to its children's keys, so the root holds the minimum.

2 Compare the adjacency matrix and adjacency list representations of a graph. 2 marks
Model answer

An adjacency matrix is an n×n array where a[i][j] = 1 if edge (i, j) exists. It needs O(n²) space and tests an edge in O(1) time. An adjacency list stores, for each vertex, a list of its neighbours. It needs O(n + e) space and is better for sparse graphs.

3 What is an articulation point? 2 marks
Model answer

An articulation point, or cut vertex, of a connected undirected graph is a vertex whose removal, together with its incident edges, splits the graph into two or more connected components. A connected graph with no articulation point is called biconnected.

4 Write the general recurrence relation for the divide and conquer method. 2 marks
Model answer

Suppose a problem of size n is split into a subproblems, each of size n/b, and dividing plus combining costs f(n). Then T(n) = a·T(n/b) + f(n) for large n. For small n, T(n) = g(n), the cost of solving directly. For merge sort, a = 2, b = 2 and f(n) = cn.

5 How many multiplications does Strassen's method use for 2×2 block matrices, and what is its time complexity? 2 marks
Model answer

Strassen's method uses 7 block multiplications instead of 8, plus 18 block additions or subtractions. Its recurrence is T(n) = 7T(n/2) + cn², which gives T(n) = O(n^log₂7) ≈ O(n^2.81). This is faster than the O(n³) conventional method.

6 Define the convex hull of a set of points. 2 marks
Model answer

The convex hull of a finite set of points in a plane is the smallest convex polygon that contains every point, either on its boundary or inside it. Its corners are a subset of the given points. It can be pictured as a rubber band stretched tightly around all the points.

10-mark questions

1 Explain insertion and deletion in a max heap used as a priority queue. Insert the keys 40, 20, 60, 10, 80, 30 one by one into an empty max heap, showing the heap after each step, and then perform one delete-max operation. 10 marks
Model answer

A max heap is a complete binary tree in which every node's key is greater than or equal to the keys of its children, so the largest key is always at the root. It is stored in an array a[1..n]: the children of a[i] are a[2i] and a[2i+1], and the parent is a[⌊i/2⌋]. This layout makes the heap an efficient priority queue.

Insertion (sift-up): 1. Place the new key at position n+1, the next free leaf, so the tree stays complete. 2. While the key is larger than its parent, swap it with the parent. 3. Stop when the parent is larger or the root is reached. Cost: O(log n).

Deletion of the maximum (sift-down): 1. Remove a[1], move the last element a[n] to the root, and reduce n by one. 2. Compare the root with its larger child and swap if the root is smaller. 3. Repeat down the tree until heap order holds. Cost: O(log n).

Trace for 40, 20, 60, 10, 80, 30:

  • Insert 40: [40].
  • Insert 20: [40, 20]. 20 < 40, so no swap.
  • Insert 60: [40, 20, 60]. 60 > parent 40, so swap → [60, 20, 40].
  • Insert 10: [60, 20, 40, 10]. 10 < parent 20, so no swap.
  • Insert 80: placed at position 5 with parent 20, so swap → [60, 80, 40, 10, 20]. Its new parent is 60, so swap again → [80, 60, 40, 10, 20].
  • Insert 30: placed at position 6 with parent 40. 30 < 40, so no swap → [80, 60, 40, 10, 20, 30].

Delete max:

  • Remove 80 and move the last key, 30, to the root: [30, 60, 40, 10, 20].
  • The children of 30 are 60 and 40. The larger, 60, exceeds 30, so swap → [60, 30, 40, 10, 20].
  • The children of 30 are now 10 and 20. The larger, 20, is less than 30, so stop.
  • Final heap: [60, 30, 40, 10, 20]. Deleted value: 80.
Max heap after delete-max: [60, 30, 40, 10, 20]Diagram in words: The root node is 60. A left edge goes down from 60 to node 30, and a right edge goes down from 60 to node 40. Node 30 has a left edge down to node 10 and a right edge down to node 20. Node 40 has no children.6030401020
Max heap after delete-max: [60, 30, 40, 10, 20]

A min heap works the same way with every comparison reversed, so the smallest key stays at the root.

Conclusion: Insertion and deletion each move along a single root-to-leaf path, so each takes O(log n) time, while reading the maximum takes O(1). This is why heaps are the standard implementation of priority queues.

2 Explain the heap sort algorithm and use it to sort the list 15, 5, 20, 1, 17, 10 in ascending order. Also list the important applications of heaps. 10 marks
Model answer

Heap sort is a comparison-based, in-place sorting method that uses a max heap. It first turns the array into a max heap. It then repeatedly moves the root, which holds the largest key, to the end of the array and restores the heap on the remaining part.

Algorithm:

Adjust(a, i, n):            // sift-down a[i] within a[1..n]
  while 2i <= n:
    j = 2i
    if j < n and a[j+1] > a[j]: j = j + 1
    if a[i] >= a[j]: break
    swap a[i], a[j]; i = j

HeapSort(a, n):
  for i = n/2 down to 1: Adjust(a, i, n)   // build heap
  for k = n down to 2:
    swap a[1], a[k]
    Adjust(a, 1, k-1)

Step 1: Build the max heap from [15, 5, 20, 1, 17, 10]. Here n = 6, so start at i = 3.

  • i = 3: 20 is compared with its child 10. No change.
  • i = 2: 5 is compared with its children 1 and 17. Swap with 17 → [15, 17, 20, 1, 5, 10].
  • i = 1: 15 is compared with its children 17 and 20. Swap with 20 → [20, 17, 15, 1, 5, 10]. Then 15 is compared with its child 10. No change.

Max heap: [20, 17, 15, 1, 5, 10].

Step 2: Repeated deletion (the sorted part is shown after |).

  • Swap 20 and 10 → [10, 17, 15, 1, 5 | 20]. Adjust: 10 swaps with 17 → [17, 10, 15, 1, 5 | 20].
  • Swap 17 and 5 → [5, 10, 15, 1 | 17, 20]. Adjust: 5 swaps with 15 → [15, 10, 5, 1 | 17, 20].
  • Swap 15 and 1 → [1, 10, 5 | 15, 17, 20]. Adjust: 1 swaps with 10 → [10, 1, 5 | 15, 17, 20].
  • Swap 10 and 5 → [5, 1 | 10, 15, 17, 20]. Since 5 > 1, no change.
  • Swap 5 and 1 → [1 | 5, 10, 15, 17, 20].

Sorted output: 1, 5, 10, 15, 17, 20.

Step 3: Analysis.

  • Building the heap bottom-up takes O(n) time.
  • Each of the n − 1 deletions costs O(log n).
  • Total time is O(n log n) in the best, average and worst cases. Extra space is O(1). The sort is not stable.

Applications of heaps:

  • Priority queues for CPU and job scheduling, where the highest-priority job is served first.
  • Dijkstra's shortest path and Prim's minimum spanning tree algorithms, which use a min heap to pick the nearest vertex.
  • Finding the k largest or k smallest elements of a large data set.
  • Huffman coding, where the two least frequent symbols are combined repeatedly.
  • Event-driven simulation, where the earliest pending event is extracted next.
  • Merging k sorted lists efficiently.

Conclusion: Heap sort guarantees O(n log n) time with constant extra memory. The same heap structure also supports many priority-based applications.

3 Explain breadth first search and depth first search with algorithms. Apply both to the undirected graph with edges A–B, A–C, B–D, B–E, C–F, E–F and G–H, taking adjacency lists in alphabetical order and starting from A. Use the traversals to find the connected components. 10 marks
Model answer

A graph G = (V, E) is a set of vertices and edges. Two vertices are adjacent if an edge joins them. The degree of a vertex is the number of edges meeting it. A graph is connected if a path exists between every pair of vertices. A traversal visits every vertex systematically, and the graph is usually stored as adjacency lists for this purpose.

Undirected graph with vertices A to H and two connected componentsDiagram in words: There are eight vertices, A to H. The undirected edges are A–B, A–C, B–D, B–E, C–F, E–F, and a separate edge G–H. Vertices A to F form one piece. Vertices G and H form another piece with no link to the first.{A, B, C, D, E, F}{G, H}ABCDEFGH
Undirected graph with vertices A to H and two connected components

Adjacency lists: A: B, C; B: A, D, E; C: A, F; D: B; E: B, F; F: C, E; G: H; H: G.

BFS uses a queue and visits vertices level by level.

BFS(s):
  visited[s] = true; enqueue(s)
  while queue not empty:
    u = dequeue()
    for each v adjacent to u:
      if not visited[v]: visited[v] = true; enqueue(v)

BFS trace from A: 1. Visit A. Queue: [B, C]. 2. Remove B and add D and E. Queue: [C, D, E]. 3. Remove C and add F. Queue: [D, E, F]. 4. Remove D, E and F. No new vertices appear, because F was already reached from C. BFS order: A, B, C, D, E, F.

DFS goes as deep as possible before backtracking, using recursion (an implicit stack).

DFS(u):
  visited[u] = true
  for each v adjacent to u:
    if not visited[v]: DFS(v)

DFS trace from A: 1. A → B, the first unvisited neighbour. 2. B → D. D has no unvisited neighbour, so return to B. 3. B → E, then E → F, then F → C. C has no unvisited neighbour. 4. Backtrack to A. All its neighbours are visited. DFS order: A, B, D, E, F, C.

Finding connected components: 1. Mark every vertex as unvisited. 2. Take each vertex v in order. If v is unvisited, start a BFS or DFS from v. All vertices reached form one component. 3. The search from A reaches {A, B, C, D, E, F}. G is still unvisited, so a new search from G gives {G, H}. Result: there are two connected components, {A, B, C, D, E, F} and {G, H}.

Complexity: with adjacency lists, each vertex is processed once and each edge is examined twice, giving O(V + E). With an adjacency matrix, the time is O(V²).

Conclusion: BFS finds shortest paths measured in number of edges. DFS is the basis for cycle detection and for finding articulation points. Both find connected components in linear time.

4 What are biconnected components and articulation points? Explain how DFS numbers and low values identify articulation points, and apply the method to the graph with edges 1–2, 2–3, 3–1, 2–4, 4–5, 5–6, 6–4. 10 marks
Model answer

A connected undirected graph is biconnected if it has no articulation point, that is, no single vertex whose removal disconnects the graph. A biconnected component is a maximal biconnected subgraph. Different components may share articulation points, but every edge belongs to exactly one component.

Method using DFS: 1. Run DFS and give each vertex a number dfn(u) in the order it is first visited. Each edge then becomes either a tree edge or a back edge to an ancestor. 2. Compute low(u) = min{ dfn(u), low(w) for every child w of u, dfn(x) for every back edge (u, x) }. In words, low(u) is the smallest dfn that u can reach by going down tree edges and then using at most one back edge. 3. A non-root vertex u is an articulation point if it has a child w with low(w) ≥ dfn(u). In that case the subtree of w cannot reach above u without passing through u. 4. The root is an articulation point only if it has two or more tree children. 5. To list the biconnected components, push edges onto a stack during the DFS. Whenever the condition in step 3 holds, pop edges down to and including (u, w); the popped edges form one component.

Graph with two triangles joined by edge 2–4Diagram in words: Vertices 1, 2 and 3 form a triangle with edges 1–2, 2–3 and 3–1. Vertex 2 is joined to vertex 4 by a single edge. Vertices 4, 5 and 6 form a second triangle with edges 4–5, 5–6 and 6–4.132456
Graph with two triangles joined by edge 2–4

DFS from vertex 1, taking neighbours in ascending order:

  • 1 (dfn 1) → 2 (dfn 2) → 3 (dfn 3). Edge 3–1 is a back edge.
  • Back at 2, go to 4 (dfn 4) → 5 (dfn 5) → 6 (dfn 6). Edge 6–4 is a back edge.

Low values, computed as the DFS returns:

  • low(3) = min(3, dfn(1) = 1) = 1
  • low(6) = min(6, dfn(4) = 4) = 4
  • low(5) = min(5, low(6) = 4) = 4
  • low(4) = min(4, low(5) = 4) = 4
  • low(2) = min(2, low(3) = 1, low(4) = 4) = 1
  • low(1) = 1

Testing each vertex:

  • Vertex 2: its child 4 has low 4 ≥ dfn(2) = 2, so 2 is an articulation point.
  • Vertex 4: its child 5 has low 4 ≥ dfn(4) = 4, so 4 is an articulation point.
  • Vertex 5: its child 6 has low 4 < dfn(5) = 5, so 5 is not an articulation point.
  • Vertices 3 and 6 are leaves of the DFS tree. The root 1 has only one tree child. None of these is an articulation point.

Biconnected components: {1, 2, 3}, {2, 4} (the single bridge edge 2–4) and {4, 5, 6}.

Applications: finding single points of failure in computer and power networks, designing fault-tolerant communication links, and identifying critical junctions in road networks.

Conclusion: A single DFS pass that computes dfn and low values finds all articulation points and biconnected components in O(V + E) time.

5 Explain the divide and conquer strategy as used in quick sort. Write the quick sort algorithm, trace it on 35, 10, 50, 25, 60, 5, 40, and analyse its best, average and worst case time complexity. 10 marks
Model answer

The divide and conquer method has three steps. It divides a problem into smaller subproblems, solves (conquers) them recursively, and combines their solutions. In quick sort, the divide step does all the work by partitioning the array around a pivot, and the combine step needs no work at all.

Algorithm (the pivot is the first element):

QuickSort(a, low, high):
  if low < high:
    p = Partition(a, low, high)
    QuickSort(a, low, p-1)
    QuickSort(a, p+1, high)

Partition(a, low, high):
  pivot = a[low]; i = low + 1; j = high
  loop:
    while i <= high and a[i] <= pivot: i++
    while a[j] > pivot: j--
    if i < j: swap a[i], a[j]
    else break
  swap a[low], a[j]
  return j

Trace for [35, 10, 50, 25, 60, 5, 40], indices 0 to 6: 1. The pivot is 35. i stops at 50 (index 2) and j stops at 5 (index 5). Swap them → [35, 10, 5, 25, 60, 50, 40]. 2. i moves past 25 and stops at 60 (index 4). j stops at 25 (index 3). Now i > j, so swap the pivot with a[3] → [25, 10, 5, 35, 60, 50, 40]. 35 is now in its final place. 3. Left part [25, 10, 5]: the pivot is 25. i runs past the end and j stops at 5. Swap 25 and 5 → [5, 10, 25]. In the sub-part [5, 10], the pivot is 5 and j stops at 5 itself, so nothing changes. 4. Right part [60, 50, 40]: the pivot is 60 and j stops at 40. Swap them → [40, 50, 60]. The sub-part [40, 50] stays unchanged. Sorted array: [5, 10, 25, 35, 40, 50, 60].

Analysis:

  • Partitioning n elements takes about n comparisons.
  • Best case: the pivot splits the array evenly. T(n) = 2T(n/2) + cn, which gives O(n log n).
  • Worst case: the array is already sorted, so the pivot is always the smallest or largest element. T(n) = T(n − 1) + cn, which gives about n(n − 1)/2 comparisons, that is O(n²).
  • Average case: O(n log n), roughly 1.39 n log₂ n comparisons.
  • Space: the recursion stack uses O(log n) on average and O(n) in the worst case. The sort is in place but not stable.
  • Choosing a random pivot or the median of three elements makes the worst case very unlikely.

Conclusion: Quick sort is usually the fastest practical internal sorting method because its inner loop is simple and it needs no extra array. Its worst case, however, is quadratic.

6 Explain merge sort as a divide and conquer algorithm. Write the algorithm, trace it on 38, 27, 43, 3, 9, 82, 10, 19, and derive its time complexity by solving the recurrence. 10 marks
Model answer

Merge sort applies divide and conquer directly. It divides the list into two halves, sorts each half recursively, and combines the results by merging the two sorted halves into one.

Algorithm:

MergeSort(a, low, high):
  if low < high:
    mid = (low + high) / 2
    MergeSort(a, low, mid)
    MergeSort(a, mid+1, high)
    Merge(a, low, mid, high)

Merge(a, low, mid, high):
  i = low; j = mid+1; k = low
  while i <= mid and j <= high:
    if a[i] <= a[j]: b[k++] = a[i++]
    else: b[k++] = a[j++]
  copy remaining a[i..mid] or a[j..high] into b
  copy b[low..high] back to a[low..high]

Trace for [38, 27, 43, 3, 9, 82, 10, 19]: 1. Divide into [38, 27, 43, 3] and [9, 82, 10, 19]. 2. Divide again into [38, 27], [43, 3], [9, 82] and [10, 19], and then into single elements. 3. Merge pairs: [27, 38], [3, 43], [9, 82], [10, 19]. 4. Merge into fours: [3, 27, 38, 43] and [9, 10, 19, 82]. 5. Final merge: [3, 9, 10, 19, 27, 38, 43, 82].

Merge sort trace on 38, 27, 43, 3, 9, 82, 10, 19Diagram in words: The figure is a tree. The root box is [38, 27, 43, 3, 9, 82, 10, 19]. Downward arrows go from the root to two boxes, [38, 27, 43, 3] and [9, 82, 10, 19]. Under the left box, downward arrows go to [38, 27] and [43, 3]. Under the right box, downward arrows go to [9, 82] and [10, 19]. Each two-element box has downward arrows to its two single elements. Upward arrows labelled merge then lead from the single elements to [27, 38], [3, 43], [9, 82] and [10, 19].38, 27, 43, 3,9, 82, 10, 19[38, 27, 43, 3][9, 82, 10, 19][38, 27][43, 3][9, 82][10, 19][38] [27][43] [3][9] [82][10] [19][27, 38][3, 43][9, 82][10, 19][3, 27, 38, 43][9, 10, 19, 82]3, 9, 10, 19,27, 38, 43, 82mergemergemergemergemergemergemergemergemergemerge
Merge sort trace on 38, 27, 43, 3, 9, 82, 10, 19

Analysis: Merging two lists with n elements in total takes at most n − 1 comparisons. So T(1) = c1 and T(n) = 2T(n/2) + cn.

Let n = 2^k and substitute repeatedly: T(n) = 2T(n/2) + cn = 4T(n/4) + 2cn = 8T(n/8) + 3cn = 2^k T(n/2^k) + k·cn = n·c1 + cn log₂ n, since 2^k = n and k = log₂ n. Therefore T(n) = O(n log n) in the best, average and worst cases.

Properties:

  • It needs an auxiliary array of size n, so its space requirement is O(n).
  • It is stable: equal keys keep their original order.
  • It suits linked lists and the external sorting of large files.
  • Compared with quick sort, it guarantees O(n log n) time but uses extra memory.

Conclusion: Merge sort is a clear example of divide and conquer. Its running time is O(n log n) whatever the order of the input.

Unit 3

Greedy Method and Dynamic Programming

Syllabus: Greedy method: the general method; Job sequencing with deadlines; Knapsack problem; Minimum cost spanning trees; Single-source shortest paths; Dynamic programming: the general method; All-pairs shortest paths; Single-source shortest paths with general weights (Bellman-Ford algorithm); Optimal binary search trees; 0/1 knapsack; String editing; Travelling salesperson problem

One-page revision summary

  • The greedy method builds a solution one input at a time using a selection rule and a feasibility check, and never revises a choice; it is optimal only when the greedy-choice property and optimal substructure hold.
  • Job sequencing with deadlines: sort jobs by decreasing profit and put each job in the latest free slot not after its deadline; the simple method takes O(n^2) time.
  • Fractional knapsack: taking objects in decreasing p/w order is optimal, and at most one object is taken fractionally.
  • A spanning tree of n vertices has n−1 edges; Prim's algorithm grows one tree in O(n^2), and Kruskal's algorithm adds the cheapest edge that forms no cycle, in O(e log e).
  • Dijkstra's algorithm solves single-source shortest paths for non-negative edge costs by repeatedly fixing the nearest unfinished vertex; it takes O(n^2) with an adjacency matrix.
  • Dynamic programming solves overlapping subproblems once, stores their answers in a table and combines them, relying on the principle of optimality; greedy commits to one decision sequence, while dynamic programming effectively compares many.
  • Floyd's all-pairs algorithm runs in Θ(n^3) time and handles negative edges as long as there is no negative cycle.
  • Bellman-Ford handles general weights: it computes dist^k (paths of at most k edges) for k up to n−1, takes O(ne) time with adjacency lists, and reports a negative cycle if an extra pass still lowers a distance.
  • An optimal binary search tree is found by filling the w, c and r tables for increasing j−i in O(n^3) time; restricting the root to r(i,j−1) ≤ k ≤ r(i+1,j) reduces this to O(n^2).
  • The 0/1 knapsack problem can be solved with an n × m table in O(nm) time, or with sets of (profit, weight) pairs from which dominated pairs are purged.
  • String editing fills an (n+1) × (m+1) cost table with cost(0,j) = j·I and cost(i,0) = i·D in O(nm) time, then traces back through the table to recover the edit operations.
  • The dynamic programming solution to TSP uses g(i,S) and takes O(n^2·2^n) time and O(n·2^n) space.
  • Worked OBST example: for success weights p = (3, 3, 1) and failure weights q = (2, 3, 1, 1), the tables give w(0,3) = 14, c(0,3) = 25 and r(0,3) = 2, because the best split is c(0,1) + c(2,3) = 8 + 3 = 11, so the second key is the root.
  • Worked 0/1 knapsack table: for p = (1, 2, 5), w = (2, 3, 4) and m = 6, the rows f_1, f_2 and f_3 over capacities 0 to 6 are (0,0,1,1,1,1,1), (0,0,1,2,2,3,3) and (0,0,1,2,5,5,6), so f_3(6) = 6 and the chosen objects are 1 and 3.
  • Worked edit distance with unit costs: converting sunday into saturday costs 3, by inserting a and t after s and changing n to r, and the bottom-right table entry cost(6, 8) is 3.
  • Worked Bellman-Ford example: from source 1 with edges 1→2 (4), 1→3 (5), 3→2 (−2), 2→4 (3) and 3→4 (6), dist^1 = (0, 4, 5, ∞), dist^2 = (0, 3, 5, 7) and dist^3 = (0, 3, 5, 6), so the negative edge 3→2 lowers the distances to vertices 2 and 4.

Learn these by heart

  • Principle of optimality: whatever the first decision, the remaining decisions must be optimal for the state that decision produces.
  • Floyd: A^k(i,j) = min{A^(k−1)(i,j), A^(k−1)(i,k) + A^(k−1)(k,j)}
  • Bellman-Ford: dist^k[u] = min{dist^(k−1)[u], min over edges (i,u) of dist^(k−1)[i] + cost(i,u)}
  • OBST: w(i,j) = w(i,j−1) + p(j) + q(j); c(i,j) = w(i,j) + min over i<k≤j of {c(i,k−1) + c(k,j)}
  • 0/1 knapsack: f_i(y) = max{f_(i−1)(y), f_(i−1)(y − w_i) + p_i}
  • Edit distance: cost(i,j) = min{cost(i−1,j)+D, cost(i,j−1)+I, cost(i−1,j−1)+C(xi,yj)}
  • TSP: g(i,S) = min over j∈S of {c(i,j) + g(j, S−{j})}, with g(i,∅) = c(i,1)
  • Fractional knapsack: sort by p_i/w_i; a minimum spanning tree has exactly n−1 edges.

2-mark questions

1 Explain the greedy method in brief. 2 marks
Model answer

The greedy method builds a solution one input at a time. At each step it picks the input that looks best by a selection rule. It keeps that input only if the partial solution stays feasible, and it never undoes a choice. A feasible solution satisfies the constraints. A feasible solution that maximises or minimises the objective function is an optimal solution.

2 State the principle of optimality used in dynamic programming. 2 marks
Model answer

An optimal sequence of decisions has this property: whatever the initial state and first decision, the remaining decisions must be optimal for the state produced by that first decision. Dynamic programming depends on this principle. It solves overlapping subproblems only once, stores their answers in a table and combines them into the final answer.

3 How does the Bellman-Ford algorithm find single-source shortest paths when edge weights may be negative, and how does it detect a negative cycle? 2 marks
Model answer

Let dist^k[u] be the shortest distance from the source to u using at most k edges, starting from dist^1[u] = cost(v,u) for source v. Then dist^k[u] = min{dist^(k−1)[u], min over edges (i,u) of dist^(k−1)[i] + cost(i,u)}, computed for k = 2 to n−1. If one extra pass still lowers some distance, a negative cycle is reachable from the source.

4 Write the recurrences for w(i,j) and c(i,j) used to build an optimal binary search tree. 2 marks
Model answer

Let p(1..n) be the success probabilities and q(0..n) the failure probabilities. Start with w(i,i) = q(i) and c(i,i) = 0. Then w(i,j) = w(i,j−1) + p(j) + q(j), and c(i,j) = w(i,j) + min over i < k ≤ j of {c(i,k−1) + c(k,j)}. The minimising k is the root r(i,j), and c(0,n) is the optimal cost.

5 Define the string editing problem and find the edit cost of converting cat into cut with unit costs. 2 marks
Model answer

String editing turns X = x1…xn into Y = y1…ym using insertions (I), deletions (D) and changes (C) at minimum total cost. The recurrence is cost(i,j) = min{cost(i−1,j)+D, cost(i,j−1)+I, cost(i−1,j−1)+C(xi,yj)}, where C = 0 if xi = yj. For cat → cut, only a changes to u, so the cost is 1.

6 Write the dynamic programming recurrence for the 0/1 knapsack problem. 2 marks
Model answer

Let f_i(y) be the maximum profit using objects 1..i with capacity y. Then f_0(y) = 0 for y ≥ 0, and f_i(y) = −∞ for y < 0. In general f_i(y) = max{f_(i−1)(y), f_(i−1)(y − w_i) + p_i}. The answer is f_n(m). Each object is either taken whole or left out.

10-mark questions

1 Explain the job sequencing with deadlines problem and its greedy solution. Find an optimal schedule for six jobs with profits (p1,…,p6) = (20, 60, 40, 100, 20, 50) and deadlines (d1,…,d6) = (2, 1, 3, 2, 1, 3). Each job takes one unit of time. 10 marks
Model answer

Introduction: We have n jobs and a single machine. Each job needs one unit of time. Job i has a deadline d_i and a profit p_i, and the profit is earned only if the job finishes by its deadline. A feasible solution is a set of jobs that can all finish on time. We want the feasible set with the largest total profit.

Greedy strategy: 1. Sort the jobs in non-increasing order of profit. 2. Consider the jobs one by one. Place each job in the latest free slot t with t ≤ d_i, so that earlier slots stay open for jobs with tighter deadlines. 3. If no such slot is free, reject the job. 4. Stop when every job has been examined or every slot is full.

JS(d, p, n)
  sort jobs so that p[1] >= p[2] >= ... >= p[n]
  for t = 1 to maxd: slot[t] = empty
  for i = 1 to n
    for t = min(d[i], maxd) down to 1
      if slot[t] is empty
        slot[t] = i; break
  return slot

Worked example: The maximum deadline is 3, so there are three slots (1, 2, 3) and at most three jobs can be done.

Step 1: Sorted order is J4(100, d=2), J2(60, d=1), J6(50, d=3), J3(40, d=3), J1(20, d=2), J5(20, d=1).

Step 2: Assign slots.

  • J4: the latest free slot ≤ 2 is slot 2. Accept.
  • J2: slot 1 is free. Accept.
  • J6: slot 3 is free. Accept.
  • J3: slots 3, 2 and 1 are all full. Reject.
  • J1: slots 2 and 1 are full. Reject.
  • J5: slot 1 is full. Reject.
Optimal schedule: J2, J4, J6 in slots 1 to 3Diagram in words: A time line of three boxes from left to right. Slot 1 (time 0 to 1) holds J2, slot 2 (time 1 to 2) holds J4, and slot 3 (time 2 to 3) holds J6. An arrow labelled time runs from the slot 1 box to the slot 3 box.Slot 1 (0-1): J2Slot 2 (1-2): J4Slot 3 (2-3): J6time
Optimal schedule: J2, J4, J6 in slots 1 to 3

Result: The selected set is {J2, J4, J6}. The processing order is J2 → J4 → J6. Total profit = 60 + 100 + 50 = 210. Only three slots exist, and these are the three most profitable jobs, so no schedule can earn more. The profit 210 is therefore optimal.

Complexity: Sorting takes O(n log n). Searching for a slot takes O(n) per job, so the worst case is O(n^2). Using disjoint sets to find the latest free slot makes each search almost constant time on average, and then sorting dominates.

Conclusion: Job sequencing shows the parts of the greedy method clearly. The selection rule is maximum profit, the feasibility test is a free slot on or before the deadline, and the result is an optimal schedule.

2 Explain the greedy method for the fractional knapsack problem and justify the choice of selection rule. Solve the instance n = 4, capacity m = 18, profits (40, 50, 48, 18), weights (5, 10, 8, 6). 10 marks
Model answer

Introduction: The knapsack has capacity m, and there are n objects. Object i has weight w_i and profit p_i. In the fractional version we may place a fraction x_i of an object, with 0 ≤ x_i ≤ 1, and earn p_i·x_i. The aim is to maximise Σ p_i·x_i subject to Σ w_i·x_i ≤ m.

Greedy method: 1. Compute the profit per unit weight, p_i/w_i, for each object. 2. Sort the objects in non-increasing order of this ratio. 3. Take whole objects in this order as long as they fit. 4. When the next object does not fit, take the fraction (remaining capacity)/w_i of it and stop.

GreedyKnapsack(m, n)   // objects sorted by p[i]/w[i]
  for i = 1 to n: x[i] = 0
  U = m
  for i = 1 to n
    if w[i] > U then break
    x[i] = 1; U = U - w[i]
  if i <= n then x[i] = U / w[i]

Worked example:

Step 1: The ratios are object 1 = 40/5 = 8, object 2 = 50/10 = 5, object 3 = 48/8 = 6 and object 4 = 18/6 = 3.

Step 2: The order is object 1, object 3, object 2, object 4.

Step 3: Fill the knapsack.

  • Object 1: weight 5 ≤ 18, so x1 = 1. Profit 40, remaining capacity 13.
  • Object 3: weight 8 ≤ 13, so x3 = 1. Profit 48, remaining capacity 5.
  • Object 2: weight 10 > 5, so x2 = 5/10 = 0.5. Profit 0.5 × 50 = 25, remaining capacity 0.
  • Object 4: x4 = 0.

Result: x = (1, 0.5, 1, 0). Total weight = 5 + 5 + 8 = 18. Total profit = 40 + 25 + 48 = 113.

Comparison with other greedy rules:

  • Largest profit first: object 2 (profit 50, weight 10), then object 3 (profit 48, weight 8) fills the 18 units exactly. Profit = 98.
  • Smallest weight first: object 1 (40), then object 4 (18), then 7/8 of object 3 (42). Profit = 100.

Only the ratio rule reaches 113.

Justification: Suppose an optimal solution uses less of a higher-ratio object and more of a lower-ratio object. Move an equal amount of weight from the lower-ratio object to the higher-ratio one. Profit cannot decrease. Repeating this exchange turns any optimal solution into the greedy solution, so the greedy profit is optimal. At most one object ends up fractional.

Complexity: Sorting costs O(n log n) and filling costs O(n).

Conclusion: For the fractional knapsack, the profit-per-unit-weight rule is provably optimal. The rule fails for the 0/1 knapsack, where objects cannot be split. That version needs dynamic programming.

3 Define a minimum cost spanning tree. Explain Kruskal's algorithm and apply it to the graph with vertices A to F and edges A–B 4, A–C 3, B–C 2, B–D 5, C–D 7, C–E 8, D–E 6, D–F 9, E–F 1. 10 marks
Model answer

Introduction: Let G be a connected undirected graph with n vertices. A spanning tree of G is a subgraph that is a tree and contains all n vertices, so it has exactly n − 1 edges. A minimum cost spanning tree (MST) is a spanning tree with the least total edge weight. MSTs are used to design road, cable and pipeline networks at minimum cost.

Kruskal's algorithm (greedy): 1. Sort all edges in non-decreasing order of weight. 2. Start with a forest in which every vertex is a separate tree. 3. Examine the edges in sorted order. If an edge joins two different trees, add it to the MST and merge the two trees with a union operation. If both ends are already in the same tree, the edge would form a cycle, so discard it. 4. Stop when n − 1 edges have been accepted. A union-find structure is used to test whether two vertices are in the same tree.

Kruskal's algorithm: input graph and resulting minimum cost spanning treeDiagram in words: Six vertices A, B, C, D, E and F joined by undirected edges: A–B weight 4, A–C weight 3, B–C weight 2, B–D weight 5, C–D weight 7, C–E weight 8, D–E weight 6, D–F weight 9 and E–F weight 1. Diagram in words: The resulting tree has links A–C (3), C–B (2), B–D (5), D–E (6) and E–F (1). These form a single path A, C, B, D, E, F.Input graphMST (cost 17)ACBEDFACBDEF43257869132561
Kruskal's algorithm: input graph and resulting minimum cost spanning tree

Sorted edges: E–F 1, B–C 2, A–C 3, A–B 4, B–D 5, D–E 6, C–D 7, C–E 8, D–F 9.

Trace:

  • E–F (1): accept. Sets are {E,F}, {A}, {B}, {C}, {D}.
  • B–C (2): accept. Sets now include {B,C}.
  • A–C (3): accept. Sets now include {A,B,C}.
  • A–B (4): A and B are already in the same set. Reject, since it would form the cycle A–B–C.
  • B–D (5): accept. Sets now include {A,B,C,D}.
  • D–E (6): accept. All vertices are now in {A,B,C,D,E,F}.

Five edges = n − 1 have been accepted, so the algorithm stops.

Result: The MST edges are E–F, B–C, A–C, B–D and D–E. Cost = 1 + 2 + 3 + 5 + 6 = 17.

Check with Prim's algorithm starting from A: it picks A–C (3), C–B (2), B–D (5), D–E (6) and E–F (1). The total is the same, 17.

Complexity: Sorting e edges takes O(e log e). Each union-find operation takes almost constant time, so Kruskal's algorithm runs in O(e log e). Prim's algorithm with an adjacency matrix takes O(n^2) and suits dense graphs. Kruskal's algorithm suits sparse graphs.

Conclusion: Kruskal's algorithm is greedy because it always picks the cheapest edge that does not form a cycle. The cut property guarantees that such an edge belongs to some MST, so the final tree is a minimum cost spanning tree.

4 Explain Dijkstra's algorithm for the single-source shortest paths problem. Apply it from vertex 1 to the directed graph with edges 1→2 (10), 1→3 (3), 3→2 (4), 3→4 (8), 3→5 (2), 2→4 (2), 5→4 (5). 10 marks
Model answer

Introduction: In the single-source shortest paths problem we are given a directed graph with non-negative edge costs and a source vertex v. We must find the shortest path from v to every other vertex. Dijkstra's algorithm solves this greedily: it fixes vertices in increasing order of their distance from the source.

Steps: 1. Set dist[v] = 0 and dist[u] = ∞ for every other vertex u. Let S be empty; S holds the vertices whose distance is final. 2. Choose the vertex u not in S with the smallest dist[u], and add u to S. 3. Relax every edge u → w with w not in S: if dist[u] + cost(u,w) < dist[w], set dist[w] = dist[u] + cost(u,w) and pred[w] = u. 4. Repeat steps 2 and 3 until every vertex is in S.

Dijkstra(v, cost, n)
  for i = 1 to n: S[i] = false; dist[i] = ∞
  dist[v] = 0
  repeat n times
    choose u with S[u] = false and minimum dist[u]
    S[u] = true
    for each edge u→w with S[w] = false
      if dist[u] + cost[u][w] < dist[w]
        dist[w] = dist[u] + cost[u][w]; pred[w] = u
Dijkstra's algorithm: input graph and shortest-path tree from vertex 1Diagram in words: Five vertices numbered 1 to 5 with directed edges 1→2 cost 10, 1→3 cost 3, 3→2 cost 4, 3→4 cost 8, 3→5 cost 2, 2→4 cost 2 and 5→4 cost 5. Vertex 1 is the source. Diagram in words: The shortest-path tree is rooted at vertex 1 and has the directed edges 1→3, 3→2, 3→5 and 2→4.Directed graphShortest-path tree1 (source)23451325410348225
Dijkstra's algorithm: input graph and shortest-path tree from vertex 1

Trace (dist values of vertices 1, 2, 3, 4, 5):

  • Initial: 0, ∞, ∞, ∞, ∞.
  • Select 1 (dist 0): dist[2] = 10, dist[3] = 3. Values: 0, 10, 3, ∞, ∞.
  • Select 3 (dist 3): dist[2] = min(10, 3+4) = 7; dist[4] = 3+8 = 11; dist[5] = 3+2 = 5. Values: 0, 7, 3, 11, 5.
  • Select 5 (dist 5): dist[4] = min(11, 5+5) = 10. Values: 0, 7, 3, 10, 5.
  • Select 2 (dist 7): dist[4] = min(10, 7+2) = 9. Values: 0, 7, 3, 9, 5.
  • Select 4 (dist 9): it has no outgoing edges. Done.

Final shortest paths:

  • 1 to 2: 1→3→2, cost 7
  • 1 to 3: 1→3, cost 3
  • 1 to 4: 1→3→2→4, cost 9
  • 1 to 5: 1→3→5, cost 5

Complexity: With an adjacency matrix and a linear search for the minimum, the time is O(n^2). With adjacency lists and a binary heap, it is O((n + e) log n).

Conclusion: Dijkstra's greedy choice is correct only when all edge costs are non-negative. When edges can be negative, the Bellman-Ford dynamic programming algorithm must be used instead.

5 Explain the dynamic programming approach to the all-pairs shortest paths problem. Derive the recurrence used and apply Floyd's algorithm to the directed graph with edges 1→2 (3), 1→4 (7), 2→1 (8), 2→3 (2), 3→1 (5), 3→4 (1), 4→1 (2). 10 marks
Model answer

Introduction: The all-pairs shortest paths problem asks for the shortest distance between every ordered pair of vertices in a directed graph. Floyd's algorithm uses dynamic programming. Let A^k(i,j) be the length of the shortest path from i to j whose intermediate vertices all have index ≤ k.

Derivation: By the principle of optimality, such a path either does not pass through vertex k, or it passes through k exactly once. In the second case both parts, i to k and k to j, are optimal paths that use only vertices ≤ k−1. Hence: A^k(i,j) = min{ A^(k−1)(i,j), A^(k−1)(i,k) + A^(k−1)(k,j) } A^0 is the cost matrix, with 0 on the diagonal and ∞ where there is no edge.

AllPaths(cost, A, n)
  for i, j: A[i][j] = cost[i][j]
  for k = 1 to n
    for i = 1 to n
      for j = 1 to n
        A[i][j] = min(A[i][j], A[i][k] + A[k][j])
Directed graph for Floyd's all-pairs shortest pathsDiagram in words: Four vertices 1, 2, 3 and 4 with directed edges 1→2 cost 3, 1→4 cost 7, 2→1 cost 8, 2→3 cost 2, 3→1 cost 5, 3→4 cost 1 and 4→1 cost 2.12343782512
Directed graph for Floyd's all-pairs shortest paths

Each row below lists the distances to vertices 1, 2, 3, 4.

A^0:

  • row 1: 0, 3, ∞, 7
  • row 2: 8, 0, 2, ∞
  • row 3: 5, ∞, 0, 1
  • row 4: 2, ∞, ∞, 0

Step 1 (k = 1): A(2,4) = min(∞, 8+7) = 15; A(3,2) = min(∞, 5+3) = 8; A(4,2) = min(∞, 2+3) = 5. A^1: row 1: 0, 3, ∞, 7; row 2: 8, 0, 2, 15; row 3: 5, 8, 0, 1; row 4: 2, 5, ∞, 0.

Step 2 (k = 2): A(1,3) = min(∞, 3+2) = 5; A(4,3) = min(∞, 5+2) = 7. A^2: row 1: 0, 3, 5, 7; row 2: 8, 0, 2, 15; row 3: 5, 8, 0, 1; row 4: 2, 5, 7, 0.

Step 3 (k = 3): A(1,4) = min(7, 5+1) = 6; A(2,1) = min(8, 2+5) = 7; A(2,4) = min(15, 2+1) = 3. A^3: row 1: 0, 3, 5, 6; row 2: 7, 0, 2, 3; row 3: 5, 8, 0, 1; row 4: 2, 5, 7, 0.

Step 4 (k = 4): A(2,1) = min(7, 3+2) = 5; A(3,1) = min(5, 1+2) = 3; A(3,2) = min(8, 1+5) = 6.

Final matrix A^4:

  • row 1: 0, 3, 5, 6
  • row 2: 5, 0, 2, 3
  • row 3: 3, 6, 0, 1
  • row 4: 2, 5, 7, 0

Check: the path 3→4→1→2 costs 1 + 2 + 3 = 6, which matches A(3,2).

Complexity: Three nested loops give Θ(n^3) time. The matrix can be updated in place, so the space needed is O(n^2).

Conclusion: Floyd's algorithm is a clean use of dynamic programming. It works with negative edge costs as long as there is no negative cycle. A negative entry on the diagonal of the final matrix reveals such a cycle.

6 Explain how dynamic programming solves the travelling salesperson problem. Find an optimal tour starting at city 1 for the cost matrix with rows (from) and columns (to): city 1: 0, 12, 10, 19; city 2: 8, 0, 6, 9; city 3: 11, 7, 0, 5; city 4: 14, 10, 4, 0. 10 marks
Model answer

Introduction: In the travelling salesperson problem (TSP), a salesperson starts at city 1, visits every other city exactly once and returns to city 1. We need the tour with the least total cost. Checking all (n−1)! tours is too slow, so we use dynamic programming.

Formulation: Let g(i, S) be the length of the shortest path that starts at city i, visits every city in the set S exactly once and ends at city 1. Here 1 ∉ S and i ∉ S. By the principle of optimality:

  • g(i, ∅) = c(i,1)
  • g(i, S) = min over j ∈ S of { c(i,j) + g(j, S − {j}) }
  • Optimal tour cost = g(1, V − {1})

Step 1 (|S| = 0): g(2,∅) = 8, g(3,∅) = 11, g(4,∅) = 14.

Step 2 (|S| = 1):

  • g(2,{3}) = 6 + 11 = 17; g(2,{4}) = 9 + 14 = 23
  • g(3,{2}) = 7 + 8 = 15; g(3,{4}) = 5 + 14 = 19
  • g(4,{2}) = 10 + 8 = 18; g(4,{3}) = 4 + 11 = 15

Step 3 (|S| = 2):

  • g(2,{3,4}) = min(6 + 19, 9 + 15) = min(25, 24) = 24; next city 4
  • g(3,{2,4}) = min(7 + 23, 5 + 18) = min(30, 23) = 23; next city 4
  • g(4,{2,3}) = min(10 + 17, 4 + 15) = min(27, 19) = 19; next city 3

Step 4 (|S| = 3): g(1,{2,3,4}) = min(12 + 24, 10 + 23, 19 + 19) = min(36, 33, 38) = 33; next city 3.

Tracing the tour: From city 1 go to city 3. For g(3,{2,4}) the best next city was 4. For g(4,{2}) only city 2 remains. Then return to city 1.

Optimal tour: 1 → 3 → 4 → 2 → 1, with cost 10 + 5 + 10 + 8 = 33.

Optimal TSP tour 1 → 3 → 4 → 2 → 1 (cost 33)Diagram in words: Four city nodes 1, 2, 3 and 4. The tour arrows are 1→3 labelled 10, 3→4 labelled 5, 4→2 labelled 10 and 2→1 labelled 8. Together they form one closed cycle through all four cities.City 1City 3City 4City 2105108
Optimal TSP tour 1 → 3 → 4 → 2 → 1 (cost 33)

Verification: The other tours cost 37 (1-2-3-4-1), 36 (1-2-4-3-1), 40 (1-3-2-4-1), 46 (1-4-2-3-1) and 38 (1-4-3-2-1). So 33 is indeed the minimum.

Complexity: There are (n−1)·2^(n−2) values g(i,S) with i ≠ 1, and each needs at most n−1 comparisons. So the time is O(n^2·2^n) and the space is O(n·2^n). This is still exponential, but much faster than (n−1)! for moderate n.

Conclusion: The dynamic programming solution guarantees an optimal tour because it stores subpath costs and reuses them. It shows how dynamic programming avoids recomputing overlapping subproblems.

Unit 4

Backtracking and Branch and Bound

Syllabus: Backtracking: the general method; 8-queens problem; Sum of subsets problem; Graph colouring; 0/1 knapsack by backtracking; Branch and bound: the general method; 0/1 knapsack by branch and bound; Travelling salesperson problem by branch and bound

One-page revision summary

  • Backtracking builds a solution vector one component at a time, searching the state space tree depth-first and killing nodes whose bounding function fails.
  • Explicit constraints give the allowed values of each xi, and implicit constraints relate the xi to one another.
  • In n-queens, xi is the column of the queen in row i, and the Place test rejects equal columns and equal absolute differences of rows and columns.
  • The 4-queens problem has two solutions, (2,4,1,3) and (3,1,4,2), and the 8-queens problem has 92 solutions, one of which is (1,5,8,6,3,7,2,4).
  • Sum of subsets uses weights sorted in ascending order and keeps a node alive only if s + w[k] ≤ m and s + r ≥ m.
  • In m-colouring, NextValue gives a vertex the next colour not used by any adjacent coloured vertex, and the state space tree has m^n leaves.
  • The chromatic number is the least m for which the m-colouring algorithm finds a colouring.
  • 0/1 knapsack by backtracking sorts items by pi/wi in decreasing order and prunes a node when its fractional upper bound cannot beat the best profit fp found so far.
  • Bound(cp, cw, k) starts from the current profit cp, adds whole items k+1, k+2, ... while they fit, and then adds the fitting fraction of the first item that does not fit.
  • BKnap(k, cp, cw) takes the left child (xk = 1) whenever cw + wk ≤ m without a bound test, because its bound equals the parent's, and explores the right child (xk = 0) only if Bound(cp, cw, k) ≥ fp.
  • At each leaf BKnap compares the current profit with fp and, if it is larger, records the new fp and copies the current vector as the best solution.
  • For w = (2, 3, 4), p = (12, 15, 16) and m = 6, BKnap first reaches x = (1,1,0) with profit 27, then the node excluding item 2 has bound 12 + 16 = 28 ≥ 27 and yields x = (1,0,1) with profit 28.
  • In the same trace, the root's right child (item 1 excluded) has bound 15 + (3/4)·16 = 27 < 28, so it is pruned and the optimum is profit 28 with x = (1,0,1).
  • Branch and bound generates all children of the E-node before choosing the next E-node from the live-node list.
  • FIFO branch and bound uses a queue, LIFO branch and bound uses a stack, and LC search picks the live node with the least ĉ(x) = f(h(x)) + ĝ(x).
  • In minimisation, a live node is killed when its lower bound is at least the cost of the best answer already found.
  • 0/1 knapsack by LC branch and bound uses the fractional greedy value as an upper bound and the integral greedy value as a feasible lower bound, often written as ĉ = -upper bound.
  • In TSP branch and bound, the root's lower bound is the total subtracted when each row and column of the cost matrix is reduced to contain a zero, but a child S reached from R by edge (i, j) has bound c(R) + A(i, j) + r, with r the reduction of its own matrix.
  • Backtracking needs only O(n) memory for the current path, while branch and bound may store many live nodes.

Learn these by heart

  • Place(k, i) succeeds only if, for every j < k, x[j] ≠ i and |x[j] - i| ≠ |j - k|.
  • Sum of subsets bounding: s + w[k] ≤ m and s + Σ(i=k..n) w[i] ≥ m.
  • LC cost function: ĉ(x) = f(h(x)) + ĝ(x); expand the live node with the least ĉ.
  • TSP root bound: total amount subtracted by reducing every row and then every column of the original cost matrix.
  • TSP child bound: c(S) = c(R) + A(i, j) + r, after setting row i, column j and entry (j, 1) to ∞ and reducing the result by r.
  • Knapsack upper bound: current profit + greedy whole items + (remaining capacity / wk)·pk for the first item k that does not fit, with items sorted by pi/wi in decreasing order.
  • BKnap: take the left child whenever cw + wk ≤ m; explore the right child only when Bound(cp, cw, k) ≥ fp; update fp at an improving leaf.
  • Live node: generated but not fully expanded. E-node: the node being expanded. Dead node: killed or fully expanded.

2-mark questions

1 What are explicit and implicit constraints in backtracking? Illustrate with the n-queens problem. 2 marks
Model answer

Explicit constraints restrict each component xi of the solution vector to a given set Si. In n-queens, xi ∈ {1, …, n} is the column of the queen in row i. Implicit constraints are rules linking the components: no two queens may share a column or a diagonal.

2 Define live node, E-node and dead node in a state space tree. 2 marks
Model answer

A live node has been generated but not all of its children have been generated yet. The E-node (expanding node) is the live node whose children are currently being generated. A dead node is either killed by the bounding function or has had all its children generated, so it is never expanded again.

3 State the bounding function used when solving the 0/1 knapsack problem by backtracking. 2 marks
Model answer

Sort the items so that p1/w1 ≥ p2/w2 ≥ … ≥ pn/wn. At a node, add to the current profit the profits of the remaining items taken greedily, plus a fraction of the first item that does not fit. If this upper bound is not greater than the best profit found so far, the node is killed.

4 Define the chromatic number of a graph and give its value for a cycle of 5 vertices. 2 marks
Model answer

The chromatic number χ(G) is the smallest number of colours that can colour the vertices of G so that no two adjacent vertices share a colour. A 5-vertex cycle is an odd cycle, so two colours cannot work and χ(C5) = 3.

5 Give two differences between backtracking and branch and bound. 2 marks
Model answer
  • Backtracking searches the state space tree depth-first and expands a child as soon as it is generated. Branch and bound generates all children of the E-node before choosing the next E-node, using FIFO, LIFO or least-cost order.
  • Backtracking mainly solves decision and enumeration problems. Branch and bound mainly solves optimisation problems using cost bounds.
6 Reduce the TSP cost matrix row [∞, 7, 3, 12]. What does this row contribute to the lower bound? 2 marks
Model answer

The minimum entry of the row is 3. Subtracting 3 from every entry gives [∞, 4, 0, 9]. The row therefore contributes 3 to the reduction, and so 3 to the lower bound on the cost of any tour.

10-mark questions

1 Explain the general method of backtracking with its control abstraction. Apply it to the sum of subsets problem for w = {3, 5, 6, 7} and m = 15, and trace the search. 10 marks
Model answer

Backtracking builds a solution vector (x1, x2, …, xn) one component at a time. It searches a state space tree depth-first and abandons a node as soon as a bounding function shows that no answer can lie below it.

1. Each xi must come from a set Si (explicit constraints), and the components must satisfy relations among themselves (implicit constraints). 2. Every node of the state space tree is a problem state. The leaves that satisfy the explicit constraints are solution states, and those that also satisfy the implicit constraints are answer states. 3. A bounding function Bk is applied to each new node. If Bk is false, the node is killed and the search backs up to its parent.

Backtrack(k):
  for each v in T(x[1..k-1]):
     x[k] = v
     if Bk(x[1..k]) is true:
        if x[1..k] is an answer: output it
        if k < n: Backtrack(k + 1)

Sum of subsets: sort the weights in ascending order and set xi = 1 if wi is chosen. Let s be the sum chosen so far and r the sum of w[k..n]. A node can lead to an answer only if s + r ≥ m and s + w[k] ≤ m.

SumOfSub(s, k, r):
  x[k] = 1
  if s + w[k] == m: print x[1..k]
  else if s + w[k] + w[k+1] <= m: SumOfSub(s+w[k], k+1, r-w[k])
  if s + r - w[k] >= m and s + w[k+1] <= m:
     x[k] = 0; SumOfSub(s, k+1, r-w[k])

Take w[n+1] = ∞ as a sentinel. The initial call is SumOfSub(0, 1, 21).

Trace: 1. Set x1 = 1. Since 0+3+5 = 8 ≤ 15, call (3, 2, 18). 2. Set x2 = 1. Since 3+5+6 = 14 ≤ 15, call (8, 3, 18-5 = 13). 3. Set x3 = 1. The sum 14 ≠ 15 and 14+7 = 21 > 15, so including w3 dies. Test for x3 = 0: 8+13-6 = 15 ≥ 15 and 8+7 = 15 ≤ 15, so call (8, 4, 7). 4. Set x4 = 1. Since 8+7 = 15, print (1, 1, 0, 1). 5. Back at level 2, x2 = 0 gives (3, 3, 13). Including w3 gives 9, and 9+7 = 16 > 15. Excluding w3 gives 3+13-6 = 10 < 15. Both branches die. 6. Back at the root, x1 = 0 gives (0, 2, 18). The path with x2 = 1 reaches 11 and cannot be extended. Excluding w2 gives 0+18-5 = 13 < 15, so it dies.

Sum of subsets state space tree for w = {3, 5, 6, 7}, m = 15Diagram in words: The root (s=0) has a left edge x1=1 to node s=3 and a right edge x1=0 to node s=0. Node s=3 has edge x2=1 to s=8 and edge x2=0 to s=3, which is killed. Node s=8 has edge x3=1 to s=14, which is killed, and edge x3=0 to s=8. That node has edge x4=1 to s=15, the answer node. The right subtree under x1=0 ends in killed nodes.s=0s=3s=0 (subtreekilled)s=8s=3 (killed)s=14 (killed)s=8s=15 (answer)x1=1x1=0x2=1x2=0x3=1x3=0x4=1
Sum of subsets state space tree for w = {3, 5, 6, 7}, m = 15

Conclusion: the only subset is {3, 5, 7}. The bounding conditions pruned most of the 2^4 = 16 leaves.

2 Explain the general method of branch and bound. Describe FIFO, LIFO and least-cost (LC) search, the cost function used in LC search, and give the control abstraction. 10 marks
Model answer

Branch and bound is a state space search method. All children of the current E-node are generated before any other live node becomes the E-node. Bounding functions kill nodes that cannot lead to an answer, or to a better answer than the one already known.

1. Terminology. A live node is generated but not yet fully expanded, the E-node is the node being expanded, and a dead node is never expanded again. The live nodes are kept in a list, and the search strategy is decided by how the next E-node is taken from this list.

2. FIFO branch and bound. The live nodes form a queue, and the oldest live node becomes the next E-node. The tree is explored level by level, like breadth-first search.

3. LIFO branch and bound. The live nodes form a stack, and the most recently generated node becomes the next E-node. This is called D-search. It differs from backtracking because all children are still generated before one of them is expanded.

4. LC search. FIFO and LIFO are blind, because they ignore how close a node is to an answer. LC search gives every node x an estimated cost ĉ(x) = f(h(x)) + ĝ(x). Here h(x) is the cost of reaching x from the root, f is a non-decreasing function, and ĝ(x) estimates the extra cost from x to an answer. The live node with the least ĉ becomes the next E-node. The blind strategies appear as special cases only under extra conditions:

  • If ĝ(x) = 0 for every node and f(h(x)) is the level of x, the least-cost live node is always at the shallowest level, so LC search becomes breadth-first search.
  • If f = 0 and ĝ(x) ≥ ĝ(y) for every child y of x, children never look costlier than their parent, so the newest nodes are chosen and the search behaves as D-search (depth-first).

Keeping the f(h(x)) term stops the search from going too deep along one path just because ĝ looks small there.

5. Bounding in optimisation. Suppose ĉ(x) ≤ c(x), and an upper bound U holds the cost of the best answer found so far. Any live node with ĉ(x) ≥ U can be killed, since it cannot give a cheaper answer. U is updated whenever a better answer appears.

LCSearch(t):
  if t is an answer node: output t; return
  E = t; make the live-node list empty
  loop
     for each child X of E:
        if X is an answer node: output path X..t; return
        X.parent = E; Add(X)
     if live list is empty: print "no answer"; return
     E = Least()      // remove live node with smallest ĉ
Branch and bound: E-node expansion, live-node list and LC selectionDiagram in words: The root R is the first E-node. Arrows go from R to its children A, B and C, which all join the live-node list. An arrow from the list labelled "choose least ĉ" points to B, the new E-node. Arrows from B go to its children D and E, which are added to the list. A node whose ĉ ≥ U has an arrow labelled "killed" to a dead-node box.R (firstE-node)AB (new E-node)CLive-node listDENode with ĉ ≥ UDead nodejoinjoinjoinchoose least ĉaddedaddedkilled
Branch and bound: E-node expansion, live-node list and LC selection

6. Comparison with backtracking. Backtracking expands a child immediately in depth-first order. Branch and bound expands a node completely and then chooses the next node by queue, stack or cost order.

Conclusion: branch and bound combines systematic node generation with cost-based selection and pruning. This makes it suitable for optimisation problems such as 0/1 knapsack and the travelling salesperson problem.

3 Explain the n-queens problem and its backtracking solution. Write the Place function and the NQueens algorithm, trace the 4-queens case until the first solution, and give one solution of the 8-queens problem. 10 marks
Model answer

The n-queens problem asks us to place n queens on an n × n chessboard so that no two queens attack each other. Two queens attack if they share a row, a column or a diagonal.

1. Formulation. Put queen i in row i, so rows never clash. Let xi be the column of queen i. The explicit constraint is xi ∈ {1..n}. The implicit constraints are that all xi are distinct and that no two queens share a diagonal.

2. Diagonal test. Queens at (j, x[j]) and (k, i) lie on the same diagonal exactly when |x[j] - i| = |j - k|.

Place(k, i):            // can queen k go in column i?
  for j = 1 to k-1:
     if x[j] == i or abs(x[j] - i) == abs(j - k):
        return false
  return true

NQueens(k, n):
  for i = 1 to n:
     if Place(k, i):
        x[k] = i
        if k == n: print x[1..n]
        else NQueens(k + 1, n)

The first call is NQueens(1, n). Because every row receives a different column, the effective search space is the permutation tree with n! leaves.

3. Trace for n = 4.

  • Q1 = 1. For Q2, column 1 clashes and column 2 is diagonal, so Q2 = 3.
  • For Q3, column 1 is used and columns 2 and 4 are diagonal to Q2. Column 3 is used. Backtrack.
  • Q2 = 4. For Q3, column 2 is safe, since |2-1| ≠ 2 and |2-4| ≠ 1.
  • For Q4, columns 2 and 4 are used, and column 3 is diagonal to Q3. Column 1 is used. Backtrack.
  • Q3 = 3 is diagonal to Q2, and Q2 has no columns left. Backtrack to Q1.
  • Q1 = 2. For Q2, column 2 is used and columns 1 and 3 are diagonal, so Q2 = 4.
  • Q3 = 1 is safe, since |1-2| = 1 ≠ 2 and |1-4| = 3 ≠ 1.
  • Q4 = 3 is safe. Against row 1: |3-2| = 1 ≠ 3. Against row 2: |3-4| = 1 ≠ 2. Against row 3: |3-1| = 2 ≠ 1.
  • The first solution is (2, 4, 1, 3).
Backtracking tree for 4-queens up to the first solutionDiagram in words: The root has a branch x1=1 to node A and a branch x1=2 to node B. From A, branch x2=3 leads to a dead node. Branch x2=4 leads to a node whose child x3=2 is dead. From B, branch x2=4 leads to a node with child x3=1, which has child x4=3, marked as the answer.RootABDeadNodeDeadNodeNodeAnswer (2,4, 1, 3)x1=1x1=2x2=3x2=4x3=2x2=4x3=1x4=3
Backtracking tree for 4-queens up to the first solution

4. 8-queens. The same algorithm with n = 8 first finds (1, 5, 8, 6, 3, 7, 2, 4).

  • Check: the row-minus-column values are 0, -3, -5, -2, 2, -1, 5, 4 and the row-plus-column values are 2, 7, 11, 10, 8, 13, 9, 12.
  • All values in each list are distinct, so no diagonal is shared.
  • The 8-queens problem has 92 solutions in total.

Conclusion: the Place test prunes a branch as soon as a conflict appears. Backtracking therefore examines only a small part of the 8! = 40320 permutations.

4 Explain the m-colouring problem and write the backtracking algorithm with the NextValue procedure. Apply it to the graph with vertices 1, 2, 3, 4 and edges (1,2), (2,3), (3,4), (4,1), (1,3), using m = 3. 10 marks
Model answer

Graph colouring asks whether the vertices of a graph G can be coloured with at most m colours so that adjacent vertices get different colours. This is the m-colourability decision problem. The smallest such m is the chromatic number of G.

1. Formulation. Let x[i] ∈ {1..m} be the colour of vertex i, with 0 meaning "not yet coloured". G is stored as an adjacency matrix. The state space tree has degree m and height n, so it has m^n leaves.

2. NextValue(k) gives x[k] the next colour that differs from every adjacent coloured vertex. If no colour is left, it sets x[k] = 0.

NextValue(k):
  loop
     x[k] = (x[k] + 1) mod (m + 1)
     if x[k] == 0: return              // colours exhausted
     ok = true
     for j = 1 to n:
        if G[k][j] == 1 and x[j] == x[k]: ok = false
     if ok: return

mColoring(k):
  loop
     NextValue(k)
     if x[k] == 0: return
     if k == n: print x[1..n]
     else mColoring(k + 1)

All x[i] start at 0 and the first call is mColoring(1).

Graph G for 3-colouring: square 1-2-3-4 with diagonal 1-3Diagram in words: There are four vertex circles labelled 1, 2, 3 and 4 arranged as a square, with 1 top-left, 2 top-right, 3 bottom-right and 4 bottom-left. Undirected lines join 1–2, 2–3, 3–4 and 4–1, and a diagonal line joins 1–3. Vertices 1, 2 and 3 form a triangle, and so do vertices 1, 3 and 4.1234
Graph G for 3-colouring: square 1-2-3-4 with diagonal 1-3

3. Trace with m = 3.

  • Vertex 1 receives colour 1.
  • Vertex 2 cannot take colour 1, because it is adjacent to vertex 1, so x2 = 2.
  • Vertex 3 is adjacent to vertices 1 and 2, so colours 1 and 2 fail and x3 = 3.
  • Vertex 4 is adjacent to vertices 3 and 1, so colours 1 and 3 fail and x4 = 2.
  • The first colouring is (1, 2, 3, 2).
  • The algorithm continues and lists every colouring: (1,2,3,2), (1,3,2,3), (2,1,3,1), (2,3,1,3), (3,1,2,1) and (3,2,1,2).
  • This makes 6 colourings in total. Vertex 1 has 3 choices and vertex 2 has 2, which forces vertex 3. Vertex 4 must then take the colour of vertex 2.

4. Chromatic number. With m = 2, the triangle 1-2-3 cannot be coloured, because vertex 3 finds both colours used by its neighbours. NextValue returns 0 on every path and no colouring is printed. Hence χ(G) = 3.

5. Complexity. NextValue takes O(n) time per call, and the state space tree has O(m^n) nodes, so there are O(m^n) NextValue calls and the worst case is O(n·m^n). Pruning makes the actual search much smaller.

Conclusion: backtracking with NextValue finds all valid m-colourings. Running it for increasing m gives the chromatic number.

5 Solve the 0/1 knapsack instance n = 4, m = 10, profits (40, 42, 25, 12), weights (4, 7, 5, 3) using least-cost branch and bound. Show the bounds at each node. 10 marks
Model answer

The 0/1 knapsack problem chooses xi ∈ {0, 1} to maximise Σ pi·xi subject to Σ wi·xi ≤ m. In LC branch and bound, each node fixes x1..xk and gets two bounds.

  • The upper bound UB is the current profit plus a greedy fill of the remaining items, with a fraction of the first item that does not fit.
  • The lower bound LB is the current profit plus a greedy fill using whole items only. LB is a profit that can actually be achieved.
  • best is the largest LB seen so far.
  • A node is killed if it is infeasible or if UB < best.
  • The live node with the largest UB is expanded next. This is the same as least ĉ when the textbook form ĉ = -UB is used.

The ratios pi/wi are 10, 6, 5 and 4, so the items are already in decreasing ratio order.

1. Root A (P = 0, W = 0).

  • UB: take item 1 (W 4, P 40), leaving capacity 6. Item 2 needs 7, so take 6/7 of it, worth 36. UB = 76.
  • LB: take items 1 and 3, so W = 9 and P = 65. LB = 65, so best = 65.

2. Expand A.

  • B (x1 = 1): P = 40, W = 4, UB = 76, LB = 65.
  • C (x1 = 0): take item 2 (42), leaving capacity 3, then 3/5 of item 3, worth 15. UB = 57 < 65, so C is killed.

3. Expand B.

  • D (x2 = 1): W = 11 > 10, so D is infeasible and killed.
  • E (x2 = 0): P = 40 with capacity 6. Take item 3 to reach 65, leaving capacity 1, then 1/3 of item 4, worth 4. UB = 69, LB = 65.

4. Expand E.

  • F (x3 = 1): P = 65, W = 9, UB = 65 + 4 = 69, LB = 65.
  • G (x3 = 0): P = 40, then item 4 gives 52. UB = 52 < 65, so G is killed.

5. Expand F.

  • H (x4 = 1): W = 12, so H is infeasible.
  • I (x4 = 0): a leaf with profit 65 = best. It is an answer node.

No live node with UB > 65 remains, so the search stops.

LC branch and bound tree for 0/1 knapsack (n = 4, m = 10)Diagram in words: Root A (UB 76, LB 65) has an edge x1=1 to B (UB 76) and an edge x1=0 to C (UB 57, killed). B has an edge x2=1 to D (infeasible) and an edge x2=0 to E (UB 69). E has an edge x3=1 to F (UB 69) and an edge x3=0 to G (UB 52, killed). F has an edge x4=1 to H (infeasible) and an edge x4=0 to I (profit 65, answer).A: UB 76, LB 65B: UB 76C: UB 57, killedD: infeasibleE: UB 69F: UB 69G: UB 52, killedH: infeasibleI: profit65, answerx1=1x1=0x2=1x2=0x3=1x3=0x4=1x4=0
LC branch and bound tree for 0/1 knapsack (n = 4, m = 10)

Result: x = (1, 0, 1, 0), total weight 9 and maximum profit 65. Only 9 nodes were generated out of the 31 nodes of the full tree, which shows how much the two bounds prune.

6 Solve the travelling salesperson problem for the cost matrix below using LC branch and bound with reduced cost matrices, starting at city 1. Rows: 1: (∞, 12, 8, 15), 2: (10, ∞, 6, 11), 3: (9, 7, ∞, 14), 4: (13, 10, 5, ∞). 10 marks
Model answer

In LC branch and bound for TSP, each node has a reduced cost matrix. Its lower bound is the cost of the path so far plus the total reduction.

For a child S of node R that uses edge (i, j), the matrix is updated in three steps:

  • set row i and column j to ∞;
  • set entry (j, 1) to ∞, so the tour cannot return to city 1 too early;
  • reduce the matrix again by an amount r.

The child's bound is then c(S) = c(R) + A(i, j) + r.

1. Root reduction. The row minima are 8, 6, 7 and 5, which sum to 26. After row reduction the column minima are 2, 0, 0 and 5, which sum to 7. The root bound is c(1) = 33, and the reduced matrix A is:

      1   2   3   4
1     ∞   4   0   2
2     2   ∞   0   0
3     0   0   ∞   2
4     6   5   0   ∞

2. Children of the root.

  • Edge 1→2: the matrix is already reduced (r = 0), so c = 33 + 4 + 0 = 37.
  • Edge 1→3: row 4 becomes (6, 5, ∞, ∞), which needs a reduction of 5. Column 1 then needs a reduction of 1, so r = 6 and c = 33 + 0 + 6 = 39.
  • Edge 1→4: r = 0, so c = 33 + 2 + 0 = 35. This is the least cost, so 1→4 becomes the E-node.

3. Expand path 1-4. The current matrix has row 2 = (2, ∞, 0, ∞), row 3 = (0, 0, ∞, ∞) and row 4 = (∞, 5, 0, ∞).

  • Edge 4→2: r = 0, so c = 35 + 5 + 0 = 40.
  • Edge 4→3: row 2 becomes (2, ∞, ∞, ∞), which needs a reduction of 2, so r = 2 and c = 35 + 0 + 2 = 37.

4. The live nodes now have costs 37 (path 1-2), 39 (path 1-3), 40 (path 1-4-2) and 37 (path 1-4-3). Expanding path 1-4-3 leaves only edge 3→2 and then 2→1. Both have reduced cost 0, so the leaf has cost 37 and gives the tour 1-4-3-2-1. Set the upper bound U = 37.

5. Pruning. The nodes with costs 39 and 40 have bounds ≥ U and are killed. Node 1-2 has a bound equal to 37, so it cannot give a cheaper tour.

LC branch and bound state space tree for TSPDiagram in words: Root node 1 (bound 33) has edges labelled 1→2 to node 2 (37), 1→3 to node 3 (39) and 1→4 to node 4 (35). Node 4 has an edge 4→2 to node 5 (40) and an edge 4→3 to node 6 (37). Node 6 has an edge 3→2 to node 7 (37), which closes the tour back to city 1.Node 1 (33)Node 2 (37)Node 3 (39)Node 4 (35)Node 5 (40)Node 6 (37)Node 7 (37)1→21→31→44→24→33→2
LC branch and bound state space tree for TSP

Verification: the tour 1-4-3-2-1 costs 15 + 5 + 7 + 10 = 37. The tour 1-2-4-3-1 also costs 12 + 11 + 5 + 9 = 37, so it is an equally cheap alternative.

Conclusion: the minimum tour cost is 37, for example along 1→4→3→2→1. The search generated only 7 nodes instead of examining all paths.

Unit 5

NP-Hard and NP-Complete Problems

Syllabus: Basic concepts of NP-hard and NP-complete problems; Cook's theorem; Clique decision problem (CDP); Chromatic number decision problem (CNDP); Travelling salesperson decision problem; Scheduling identical processors; Job shop scheduling

One-page revision summary

  • A deterministic algorithm has a unique result for every step, while a nondeterministic algorithm uses Choice, Success and Failure and always takes a successful path if one exists.
  • P is the class of decision problems solvable deterministically in polynomial time; NP is the class solvable nondeterministically in polynomial time, which is the same as having polynomially verifiable certificates; P ⊆ NP.
  • L1 ∝ L2 means every instance of L1 can be converted in polynomial time into an instance of L2 with the same answer, and the relation is transitive.
  • To prove a problem L NP-complete, show L ∈ NP, then reduce a known NP-complete problem to L.
  • An NP-hard problem need not be in NP; the halting problem is NP-hard but not NP-complete.
  • If any NP-complete problem has a deterministic polynomial algorithm, then P = NP.
  • Cook's theorem says SAT ∈ P if and only if P = NP, and its proof encodes any polynomial-time nondeterministic computation as a formula Q(A, I).
  • The formula Q(A, I) uses variables for memory bits and for the statement executed at each time step up to p(n), and can be written in CNF, which makes CNF-SAT NP-complete.
  • In the clique reduction, each literal occurrence becomes a vertex, and vertices from different clauses are joined unless their literals are complementary; F is satisfiable if and only if there is a clique of size equal to the number of clauses.
  • The chromatic number reduction uses vertices xi, x̄i, yi and Cj with n+1 colours, where colour n+1 means false and a clause vertex is colourable only if it contains a true literal.
  • The TSP decision problem is NP-complete via Hamiltonian cycle: edges of G cost 1, non-edges cost 2, and the bound is n.
  • On identical processors, minimum mean finish time is polynomial (shortest processing time first), while minimum finish time and minimum weighted mean finish time are NP-hard by reduction from partition.
  • Partition asks whether a set of integers with sum T has a subset summing to exactly T/2.
  • In a job shop, each job is an ordered sequence of tasks on specified processors, and minimum finish time is NP-hard even for two processors with preemption.
  • Optimisation versions are at least as hard as their decision versions, so an NP-complete decision problem means the matching optimisation problem is NP-hard.

Learn these by heart

  • NP-complete = NP-hard ∩ NP.
  • If L1 ∝ L2 and L2 ∈ P, then L1 ∈ P; if L1 is NP-hard and L1 ∝ L2, then L2 is NP-hard.
  • Cook's theorem: Satisfiability ∈ P ⇔ P = NP.
  • CNF-SAT ∝ CDP: F with k clauses is satisfiable ⇔ the constructed graph has a clique of size k.
  • 3-literal SAT ∝ CNDP: F is satisfiable ⇔ the constructed graph is (n+1)-colourable.
  • HC ∝ TSP: c(u,v) = 1 if (u,v) ∈ E, otherwise 2; G has a Hamiltonian cycle ⇔ there is a tour of cost ≤ n.
  • Partition ∝ 2-processor scheduling: a nonpreemptive schedule with FT ≤ T/2 exists ⇔ a partition into halves of sum T/2 exists.

2-mark questions

1 Define NP-hard and NP-complete problems. 2 marks
Model answer

A decision problem L is NP-hard if satisfiability, and hence every problem in NP, reduces to L in polynomial time. Such an L is at least as hard as any NP problem. L is NP-complete if it is NP-hard and also belongs to NP. Example: the clique decision problem is NP-complete. The halting problem is NP-hard but not NP-complete.

2 State Cook's theorem and its significance. 2 marks
Model answer

Cook's theorem states that satisfiability (SAT) is in P if and only if P = NP. Its proof shows that every problem in NP can be reduced in polynomial time to the satisfiability of a Boolean formula. Hence SAT was the first problem proved NP-complete, and it serves as the starting point for proving other problems NP-complete.

3 What is the clique decision problem (CDP)? 2 marks
Model answer

A clique is a set of vertices in which every pair is joined by an edge, that is, a complete subgraph. The clique decision problem asks: given an undirected graph G and an integer k, does G contain a clique of size at least k? CDP is NP-complete, because CNF-satisfiability reduces to it.

4 Define the chromatic number decision problem (CNDP). 2 marks
Model answer

Given a graph G and an integer k, CNDP asks whether the vertices of G can be coloured with at most k colours so that no two adjacent vertices get the same colour. It is NP-complete for k ≥ 3. The case k = 2 is solvable in polynomial time, because it only requires checking whether G is bipartite.

5 Define the travelling salesperson decision problem and say why it is in NP. 2 marks
Model answer

Given a weighted complete graph on n vertices and a bound M, the TSP decision problem asks whether some tour visits every vertex exactly once, returns to the start, and has total cost at most M. It is in NP because a guessed tour can be checked for validity and for cost ≤ M in O(n) time.

6 What is job shop scheduling? 2 marks
Model answer

A job shop has m processors of different types. Each job is an ordered sequence of tasks, and each task must run on a specified processor for a given time. The tasks of a job must follow their order, and a processor runs only one task at a time. The goal is a schedule with minimum finish time, which is NP-hard even for two processors when preemption is allowed.

10-mark questions

1 Distinguish deterministic and nondeterministic algorithms. Define the classes P and NP, polynomial reducibility, NP-hard and NP-complete problems, and show their relationship with a diagram. 10 marks
Model answer

Introduction: Some problems have polynomial-time algorithms, while for others only exponential-time algorithms are known. The theory of NP-hard and NP-complete problems lets us prove that a new problem is as hard as problems already known to be difficult.

1. Deterministic algorithm: the result of every operation is uniquely defined, so a given input produces exactly one execution path.

2. Nondeterministic algorithm: it may use three extra primitives.

  • Choice(S) picks any element of the set S.
  • Failure() ends the computation unsuccessfully.
  • Success() ends the computation successfully.

The machine is assumed to always make a choice that leads to success whenever such a choice exists. Its running time is the length of the shortest successful computation. A nondeterministic search looks like this:

Algorithm NSearch(A, n, x)
{
  j := Choice(1, n);
  if (A[j] = x) then { write(j); Success(); }
  write(0); Failure();
}

This takes O(1) nondeterministic time, whereas any deterministic search of an unsorted array needs Ω(n) time.

3. Decision and optimisation problems: a decision problem has a yes/no answer, while an optimisation problem asks for a best value. The theory is stated for decision problems. If the decision version is hard, the optimisation version is at least as hard.

4. Class P: decision problems solvable by a deterministic algorithm in polynomial time.

5. Class NP: decision problems solvable by a nondeterministic algorithm in polynomial time. Equivalently, a proposed yes-certificate can be verified in polynomial time. P ⊆ NP, since a deterministic algorithm is a special case of a nondeterministic one. Whether P = NP is still an open question.

6. Reducibility: L1 ∝ L2 if every instance of L1 can be converted in polynomial time into an instance of L2 with the same answer. A polynomial algorithm for L2 then gives one for L1. The relation ∝ is transitive.

7. NP-hard: L is NP-hard if satisfiability ∝ L, so every NP problem reduces to L.

8. NP-complete: L is NP-complete if L is NP-hard and L ∈ NP. Examples are CNF-satisfiability and the clique decision problem. The halting problem is NP-hard but undecidable, so it is not in NP and not NP-complete.

Relationship between P, NP, NP-hard and NP-completeA Venn diagram of NP and NP-hard drawn assuming P is not equal to NP. The overlap of the two sets is NP-complete, the class P sits in the part of NP outside NP-hard, and the halting problem lies in NP-hard outside NP.Universe: Drawn assuming P ≠ NPNPContains PNP-hardExtends outside NPP lies inthis partNP-completeHaltingproblem
Relationship between P, NP, NP-hard and NP-complete

Conclusion: NP-complete problems are the hardest problems in NP. If any one of them is solved in deterministic polynomial time, then P = NP.

2 State Cook's theorem and explain the outline of its proof. Why is the theorem important? 10 marks
Model answer

Introduction: Satisfiability (SAT) asks whether a Boolean formula has a truth assignment that makes it true. Cook's theorem links SAT to the whole class NP.

Statement: Satisfiability is in P if and only if P = NP.

Part 1 (if P = NP, then SAT ∈ P): A nondeterministic algorithm uses Choice(true, false) to guess a value for each of the n variables. It then evaluates the formula in time polynomial in the formula's length and calls Success() if the value is true. Hence SAT ∈ NP, so if P = NP then SAT ∈ P.

Part 2 (if SAT ∈ P, then P = NP): Let L be any problem in NP, decided by a nondeterministic algorithm A in time p(n) on inputs of size n. For an input I, we construct a formula Q(A, I) that is satisfiable exactly when A has a successful computation on I.

1. Variables: B(i, t) is true when memory bit i holds 1 at time t. S(j, t) is true when statement j is executed at time t. Here 1 ≤ t ≤ p(n), and at most p(n) memory locations are used. 2. Subformula C: the memory at time 1 holds the input I. 3. Subformula D: statement 1 is executed at time 1. 4. Subformula E: exactly one statement is executed at each time step. 5. Subformula F: if statement j runs at time t, then the memory and the next statement at time t + 1 obey the meaning of j. A Choice statement may take any allowed value. 6. Subformula H: locations not changed by a statement keep their values. 7. Subformula G: a Success statement is reached by time p(n).

Then Q = C ∧ D ∧ E ∧ F ∧ G ∧ H. A satisfying assignment of Q describes a successful computation step by step, and a successful computation gives a satisfying assignment.

Q has polynomially many variables and clauses. It can therefore be built, and written in CNF, deterministically in time polynomial in n, so L ∝ SAT. If SAT has a deterministic polynomial algorithm, we can decide I by building Q and testing it. This puts L in P, so NP ⊆ P and P = NP.

Using a polynomial SAT algorithm to decide any problem L in NPDiagram in words: a left-to-right flow of four boxes. Box 1, "Input I of problem L in NP", has an arrow labelled "polynomial transformation" to Box 2, "Formula Q(A, I)". An arrow from Box 2 goes to Box 3, "Polynomial SAT algorithm". An arrow labelled "satisfiable / not satisfiable" goes from Box 3 to Box 4, "Answer yes / no for I".Input I ofproblem L in NPFormula Q(A, I)PolynomialSAT algorithmAnswer yes/ no for Ipoly.transformationtest Qsatisfiable/ not
Using a polynomial SAT algorithm to decide any problem L in NP

Importance:

  • SAT, and in fact CNF-satisfiability, became the first NP-complete problem.
  • Other problems are proved NP-complete by reduction chains from it, for example SAT → clique, SAT → chromatic number, and Hamiltonian cycle → TSP.

Conclusion: Cook's theorem gives the starting point for the whole theory of NP-completeness.

3 Prove that the clique decision problem is NP-complete by reducing CNF-satisfiability to it. Illustrate with F = (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3). 10 marks
Model answer

Introduction: CDP asks whether an undirected graph G has a clique (a complete subgraph) of size at least k. We show that CDP ∈ NP and that CNF-SAT ∝ CDP.

Step 1, CDP ∈ NP: Nondeterministically choose k vertices and check that all k(k−1)/2 pairs are edges. This takes O(k²) time with an adjacency matrix.

Step 2, construction: Let F = C1 ∧ C2 ∧ ... ∧ Ck be in CNF.

  • Vertices: one vertex <σ, i> for every literal σ that occurs in clause Ci.
  • Edges: <σ, i> and <δ, j> are joined when i ≠ j and σ ≠ ¬δ, that is, when the two literals come from different clauses and are not complementary.
  • The target clique size is k, the number of clauses.

G has at most as many vertices as F has literal occurrences, so it is built in polynomial time.

Step 3, F satisfiable ⇒ clique of size k: From each clause pick one literal that is true under the satisfying assignment. The k chosen vertices come from different clauses. Since all chosen literals are true, no two of them are complementary. Every pair is therefore adjacent, and the k vertices form a clique.

Step 4, clique of size k ⇒ F satisfiable: Vertices from the same clause are never adjacent, so the clique has exactly one vertex from each clause. No two of its literals are complementary, so we can set all of them true without conflict. Unused variables are set arbitrarily. Every clause then contains a true literal, and F is satisfied.

Step 5, example: F has k = 3 clauses. Name the vertices a = <x1,1>, b = <x2,1>, c = <¬x1,2>, d = <x3,2>, e = <¬x2,3> and f = <¬x3,3>.

  • Pairs across clauses that are complementary, and so not joined: a–c, b–e and d–f.
  • Edges: a–d, b–c, b–d, a–e, a–f, b–f, c–e, c–f and d–e, giving 9 edges.
Clique reduction graph for F = (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3)Diagram in words: three columns of vertices. Column Clause 1 holds a and b, column Clause 2 holds c and d, and column Clause 3 holds e and f. Undirected edges join a–d, b–c, b–d, a–e, a–f, b–f, c–e, c–f and d–e. There are no edges inside a column and none between a–c, b–e or d–f.Clause 1Clause 2Clause 3a = x1, 1b = x2, 1c = ¬x1, 2d = x3, 2e = ¬x2, 3f = ¬x3, 3
Clique reduction graph for F = (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3)

The clique {a, d, e} has edges a–d, a–e and d–e. It gives x1 = true, x3 = true and x2 = false, which makes all three clauses true. A second clique, {b, c, f}, gives x2 = true, x1 = false and x3 = false, another satisfying assignment.

Conclusion: F is satisfiable if and only if G has a clique of size k, and the construction takes polynomial time. CNF-SAT is NP-complete, so CDP is NP-hard. Together with Step 1, CDP is NP-complete.

4 Define the chromatic number decision problem (CNDP). Prove that it is NP-hard by reducing satisfiability with at most three literals per clause to it. 10 marks
Model answer

Introduction: A colouring of a graph G = (V, E) gives each vertex a colour so that adjacent vertices differ. CNDP asks whether G can be coloured with at most k colours. Satisfiability with at most three literals per clause is NP-complete, so reducing it to CNDP proves CNDP NP-hard.

Step 1, CNDP ∈ NP: Guess a colour from 1..k for each vertex and check every edge in O(|V| + |E|) time.

Step 2, input: F = C1 ∧ ... ∧ Cr over variables x1..xn, with every clause having at most three literals. Assume n ≥ 4. If n < 4, add unused variables, which does not change satisfiability.

Step 3, construction of G: The vertices are x1..xn, x̄1..x̄n, y1..yn and C1..Cr, which is 3n + r in total. The edges are:

  • (xi, x̄i) for every i;
  • (yi, yj) for every i ≠ j;
  • (yi, xj) and (yi, x̄j) for every i ≠ j;
  • (xi, Cj) if xi does not occur in Cj, and (x̄i, Cj) if x̄i does not occur in Cj.

Set k = n + 1. There are O(n² + nr) edges, so the construction is polynomial.

Graph G built from F for the CNDP reduction (representative i ≠ j)Diagram in words: In the top row draw y1..yn, with every pair joined by an edge (a complete graph). In the middle row draw n pairs xi, x̄i, each pair joined by an edge. Each yi is joined to every literal vertex except xi and x̄i. In the bottom row draw C1..Cr. Each Cj is joined to every literal vertex that does not occur in Cj. There are no edges among the clause vertices and none from clause vertices to y vertices.y1..yn (complete graph)Literal verticesClause vertices C1..Cryiyjxix̄ixjx̄jCjcliqueif xinot in Cjif x̄inot in Cjif xjnot in Cjif x̄jnot in Cj
Graph G built from F for the CNDP reduction (representative i ≠ j)

Step 4, forced colours: The yi form a clique of size n, so they need n different colours; call the colour of yi colour i. The vertices xi and x̄i are adjacent to every yj with j ≠ i, so each of them can only take colour i or colour n+1. Because xi and x̄i are adjacent, one gets colour i and the other gets n+1. We read colour i as true and colour n+1 as false.

Step 5, clause vertices: Cj has at most 3 literals. So for at least n − 3 ≥ 1 values of i, neither xi nor x̄i occurs in Cj, and Cj is adjacent to both of them. One of these two has colour n+1, so Cj cannot use colour n+1 and must take some colour i ≤ n. Colour i is available to Cj only if the literal coloured i, the true literal of variable i, is not adjacent to Cj. That happens exactly when this literal occurs in Cj.

Step 6, equivalence:

  • If F is satisfied, colour yi with i, the true literal of xi with i and the false literal with n+1. Give each Cj the index of any true literal it contains. This is a valid (n+1)-colouring.
  • Conversely, take any (n+1)-colouring and set true the literals coloured i. By Step 5, every clause contains a true literal, so F is satisfied.

Conclusion: G is (n+1)-colourable if and only if F is satisfiable, and G is built in polynomial time. Hence CNDP is NP-hard, and with Step 1 it is NP-complete.

5 Define the travelling salesperson decision problem and prove that it is NP-complete by reducing the Hamiltonian cycle problem to it. Illustrate with a four-vertex example. 10 marks
Model answer

Introduction: The travelling salesperson optimisation problem looks for a minimum-cost tour. Its decision version asks: given a complete weighted graph G' on n vertices and a bound M, is there a tour that visits every vertex exactly once and returns to the start with cost at most M? The Hamiltonian cycle (HC) problem asks whether an undirected graph G contains a simple cycle through all its vertices. HC is known to be NP-complete.

Step 1, TSP decision ∈ NP: Nondeterministically guess a permutation of the n vertices. Then check that it is a valid tour and that its cost is at most M. Both checks take O(n) time.

Step 2, construction (HC ∝ TSP): Given G = (V, E) with |V| = n, build the complete graph G' on the same vertex set.

  • c(u, v) = 1 if (u, v) ∈ E.
  • c(u, v) = 2 if (u, v) ∉ E.
  • Set M = n.

G' has n(n−1)/2 edges, so the construction takes O(n²) time.

Step 3, G has an HC ⇒ G' has a tour of cost ≤ n: Each of the n edges of the Hamiltonian cycle lies in E and costs 1. The same cycle is a tour in G' with cost exactly n.

Step 4, G' has a tour of cost ≤ n ⇒ G has an HC: Any tour uses exactly n edges, each costing at least 1, so its cost is at least n. A cost of at most n is therefore exactly n, which means every edge used costs 1. Every such edge belongs to E, so the tour is a Hamiltonian cycle in G.

Step 5, example: Let G have vertices 1, 2, 3, 4 and edges (1,2), (2,3), (3,4), (4,1) and (1,3). The only missing pair is (2,4), so in G' c(2,4) = 2 and all other costs are 1, with M = 4. The three distinct tours are:

  • 1-2-3-4-1: cost 1 + 1 + 1 + 1 = 4.
  • 1-2-4-3-1: cost 1 + 2 + 1 + 1 = 5.
  • 1-3-2-4-1: cost 1 + 1 + 2 + 1 = 5.

The tour 1-2-3-4-1 has cost 4 ≤ 4, so the answer is yes. This matches the Hamiltonian cycle 1-2-3-4-1 in G.

Four-vertex example: G' with costs, tour 1-2-3-4-1Diagram in words: place vertex 1 at the top-left, 2 at the top-right, 3 at the bottom-right and 4 at the bottom-left of a square. Solid undirected edges labelled 1 join 1–2, 2–3, 3–4, 4–1 and the diagonal 1–3. A dashed diagonal labelled 2 joins 2–4; this edge exists only in G'. The tour 1→2→3→4→1 is highlighted.12341 (tour)1 (tour)1 (tour)1 (tour)12 (only in G')
Four-vertex example: G' with costs, tour 1-2-3-4-1

Conclusion: G has a Hamiltonian cycle if and only if G' has a tour of cost at most n, and G' is built in polynomial time. Hence the TSP decision problem is NP-hard, and with Step 1 it is NP-complete. The optimisation version is NP-hard, because solving it also answers the decision version.

6 Show that finding a minimum finish time nonpreemptive schedule on two identical processors is NP-hard by reducing the partition problem to it. Also explain the job shop scheduling problem and state its complexity. 10 marks
Model answer

Introduction: In scheduling identical processors, n jobs with times t1..tn must be run on m identical processors. A nonpreemptive schedule runs each job to completion on one processor. The finish time FT(S) is the time at which the last processor finishes. The mean finish time is the average completion time of the jobs.

  • Minimum mean finish time can be found in polynomial time by running jobs in shortest-processing-time order.
  • Minimum finish time is NP-hard, even for m = 2.

Partition problem: given positive integers a1..an with sum T, is there a subset whose sum is exactly T/2? Partition is NP-complete.

Step 1, construction: Take m = 2 processors and n jobs with ti = ai. Ask whether a nonpreemptive schedule with FT ≤ T/2 exists. The construction takes O(n) time.

Step 2, partition ⇒ schedule: Run the jobs of the subset A1 (sum T/2) on P1 and the remaining jobs on P2 (also sum T/2). Both processors finish at T/2.

Step 3, schedule ⇒ partition: The total work is T and each processor can do at most T/2 of it. Both processors must therefore be loaded with exactly T/2. The jobs on P1 then form a subset with sum T/2.

Step 4, example: a = {3, 1, 1, 2, 2, 1}, so T = 10 and the target is 5. Put jobs of times 3 and 2 on P1, finishing at time 5. Put jobs of times 1, 1, 2 and 1 on P2, also finishing at time 5. FT = 5 corresponds to the partition {3, 2} and {1, 1, 2, 1}.

Gantt chart: two-processor schedule with FT = 5Diagram in words: a Gantt chart with time running from 0 to 5 on the horizontal axis. Row P1 holds bar J1 over [0,3] and bar J4 over [3,5]. Row P2 holds bars J2 over [0,1], J3 over [1,2], J5 over [2,4] and J6 over [4,5].P1P2J1 [0,3]J4 [3,5]J2 [0,1]J3 [1,2]J5 [2,4]J6 [4,5]
Gantt chart: two-processor schedule with FT = 5

Thus Partition ∝ two-processor minimum finish time scheduling, so that scheduling problem is NP-hard. A similar argument shows that minimum weighted mean finish time is also NP-hard.

Job shop scheduling: there are m processors of different kinds, and each job is an ordered list of tasks. Each task must run on a specified processor for a given time. A task may start only after the previous task of its job is complete, and a processor runs one task at a time. The goal is a schedule with minimum finish time.

Complexity: job shop scheduling is NP-hard even for two processors with preemption allowed. A sketch of the reduction from partition, assuming T is even:

  • Each ai becomes a job with a task of time ai on P1 followed by a task of time ai on P2.
  • One extra job has four tasks of length T/2, run in the order P2, P1, P2, P1.
  • The target finish time is 2T.

Each processor carries exactly 2T of work, so there can be no idle time. The extra job then occupies fixed windows, and the jobs whose first tasks fit in P1's window [0, T/2] must have a total of exactly T/2.

Conclusion: Both minimum finish time problems are NP-hard. In practice they are handled with heuristics or approximation algorithms.

Public sources that settled doubtful points

Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.

4 pages

Further reading

Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.

  • Fundamentals of Data Structures in C++ · Ellis Horowitz, Sartaj Sahni and Dinesh Mehta
  • Computer Algorithms in C++ · Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran
  • Data Structures and Program Design in C · Robert Kruse
  • An Introduction to Data Structures with Applications · J.-P. Tremblay and P. G. Sorenson
  • The Art of Computer Programming, Vol. 1: Fundamental Algorithms · Donald E. Knuth
  • Data Structures Using C and C++ · Y. Langsam, M. J. Augenstein and A. M. Tenenbaum