Indian Institute of Technology Madras
BS Degree Programme · Examination & Study Paper
Programming, Data Structures and Algorithms using Python
Linear programming & network flow
Examination Instructions & Guidelines
- Solve on notebook/paper first before checking solutions.
- MCQ: Exactly 1 option is correct. Negative marking applies.
- MSQ: One or more options correct. Select all to score.
- Scientific calculator allowed for all calculations.
- Official answer key is sealed at the end of this sheet.
End Term · 31 Aug 2025 (FN)End Term
- Q1MCQ4 Marks·Choose one option
- A14
- B15
- C13
- D16
- Q2MSQ4 Marks·Choose all correct options
- A
- B
- C
- D
- E
- F
- A
End Term · 31 Aug 2025 (AN)End Term
- Q3MCQ4 Marks·Choose one option
- AEdges {cd, bd}
- BEdges {cb, cd, bt}
- CEdges {ab, cd, cb}
- DEdges {bt, bd}
- Q4MSQ4 Marks·Choose all correct options
- A
- B
- C
- D
- E
- F
- A
End Term · 13 Apr 2025 (AN)End Term
- Q5MSQ4 Marks·Choose all correct options
- A
- B
- C
- D
- E
- A
End Term · 22 Dec 2024 (FN)End Term
- Q6MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q7MCQ4 Marks·Choose one option
Which of the following is true about a minimum cut in a network? 1. It is the cut that separates the source and the sink with the minimum number of edges. 2. It is the cut that separates the source and the sink with the minimum sum of capacities of the edges.
- AOnly statement 1 is true.
- BOnly statement 2 is true.
- CBoth statement 1 and 2 are true.
- DBoth statement 1 and 2 are not true.
End Term · 22 Dec 2024 (AN)End Term
- Q8MCQ4 Marks·Choose one option
A popular conference is being held, and there are several types of seats: VIP, Regular, and Economy. Each type of seat has a limited number of available spots. Each attendee has a preference for the type of seat they want, and the total number of attendees is greater than the number of available seats. The goal is to allocate the seats to attendees such that each attendee is assigned to their preferred seat type, and no seat type exceeds its capacity. How can the given problem of allocating seats to attendees based on their preferences and seat type capacities be effectively solved?
- AUsing a greedy algorithm to assign seats based on attendee preferences.
- BModeling the problem as a maximum flow network with capacities representing seat limits and flows representing the number of attendees assigned to each seat type.
- CImplementing a first-come, first-serve approach without considering the preferences or seat type capacities.
- DAssigning all attendees to the VIP seats first and distributing the remaining attendees among Regular and Economy seats.
- Q9MSQ4 Marks·Choose all correct options
- A
- B
- C
- D
- A