uiz Space

September 2024 term · Advanced Algorithms · BSCS4021

Advanced Algorithms Quiz 1: 27 October 2024 (September 2024 term)

The IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 27 Oct 2024, in the September 2024 term: 28 questions for 50 marks in 120 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.

Questions
28
Marks
50
Duration
120 min
MCQ
24
Numerical
4
Take as mock testPractise with answers

Updated

Official paper: IIT M DEGREE AN EXAM QDB2 27 Oct 2024 · No negative marking.

Question 1

+2 marksOne correct option

What is the treewidth of the following graph?

  1. A

    1

  2. B

    2

  3. C

    3

  4. D

    4

Show answer

Correct answer

  • C

    3

Question 1 on its own page

Question 2

+3 marksOne correct option
  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • D
Question 2 on its own page

Question 3

+3 marksOne correct option

Consider the following graph, which is a path on five vertices:

  1. A
  2. B
  3. C
  4. D
  5. E
Show answer

Correct answer

  • A
Question 3 on its own page

Question 4

+4 marksOne correct option

Consider the following instance of Maximum Weight Independent Set problem:

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
Question 4 on its own page

Question 5

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of man 1?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
Question 5 on its own page

Question 6

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of man 2?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • C
Question 6 on its own page

Question 7

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of man 3?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
Question 7 on its own page

Question 8

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of man 4?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • C
Question 8 on its own page

Question 9

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of woman A?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • C
Question 9 on its own page

Question 10

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of woman B?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • C
Question 10 on its own page

Question 11

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of woman C?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
Question 11 on its own page

Question 12

+2 marksOne correct option

Below are the observed proposals from the traditional male propose-and-reject algorithm. After the algorithm terminates, only B is married to the man she likes the most. Also, it is known that A has the same preferences as B and every man likes C better than A. Reconstruct the complete preference lists of men and women in the given information.

RoundWomenMenRoundWomenMen
1A-5A-
B1,2B4
C3C2
D4D1,3
2A-6A-
B1B3,4
C2,3C2
D4D1
3A-7A-
B1B3
C2C2,4
D3,4D1
4A-8A2
B1,4B3
C2C4
D3D1

Based on the above data, answer the given subquestions.

What is the preference ordering of woman D?

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
Question 12 on its own page

Question 13

+2 marksOne correct option
  1. A

    Yes

  2. B

    No

Show answer

Correct answer

  • A

    Yes

Question 13 on its own page

Question 14

+2 marksOne correct option
  1. A

    Yes

  2. B

    No

Show answer

Correct answer

  • A

    Yes

Question 14 on its own page

Question 15

+1 markOne correct option
  1. A

    Yes

  2. B

    No

Show answer

Correct answer

  • B

    No

Question 15 on its own page

Question 16

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • A

    TRUE

Question 16 on its own page

Question 17

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • B

    FALSE

Question 17 on its own page

Question 18

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • B

    FALSE

Question 18 on its own page

Question 19

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • A

    TRUE

Question 19 on its own page

Question 20

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • A

    TRUE

Question 20 on its own page

Question 21

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • A

    TRUE

Question 21 on its own page

Question 22

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • A

    TRUE

Question 22 on its own page

Question 23

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • B

    FALSE

Question 23 on its own page

Question 24

+1 markOne correct option

For each of the statements in the given subquestions, identify whether it is true or false.

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • B

    FALSE

Question 24 on its own page

Question 25

+1 markNumerical answer

Based on the above data, answer the given subquestions.

What is the minimum number of steps required to produce the integer 1024?

Show answer

Correct answer: 10

Question 25 on its own page

Question 26

+2 marksNumerical answer

Based on the above data, answer the given subquestions.

What is the minimum number of steps required to produce the integer 32768?

Show answer

Correct answer: 15

Question 26 on its own page

Question 27

+2 marksNumerical answer

Based on the above data, answer the given subquestions.

What is the minimum number of steps required to produce the integer 189?

Show answer

Correct answer: 12

Question 27 on its own page

Question 28

+3 marksNumerical answer

Based on the above data, answer the given subquestions.

What is the minimum number of steps required to produce the integer 750?

Show answer

Correct answer: 15

Question 28 on its own page