GATE IT 2007 | Question: 83

Question

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. 

What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are $2048$ and the head can start from any track?

• A. $9$
• B. $10$
• C. $11$
• D. $12$

Comments

yes ABHINEET, it will be independent.

You can start with any track, do zig zag, you will erach 2047 in 11 steps only.

---

@Aalok8523 @Skscool007

Initially head will be at some position or moving in some specific direction then we should not take current position of head in cardinality of the request because if we do so then head will not change it's direction if request come at track on which it is currently there.

So that's why you are getting 12.

Because of above reason you should remove one track (initial position of head) and answer should be 11.

I hope it will help others who are confused in the battle of 11 and 12.

---

good question

 

(0+1) + (1+2) + (3+4) + (7+8) + (15+16) + ( 31+32) + (63+64) + (127+128)  + (255+256) + (511+512) + (1023+1024)

Hence 11 will be the answer.

Answer 1

correct answer C

Answer 2

We can start from any track.

$1366\overset{-1}{\rightarrow}1365\overset{+(1+2)}{\rightarrow}1368\overset{-(3+4)}{\rightarrow}1361\overset{+(7+8)}{\rightarrow}1376\overset{-(15+16)}{\rightarrow}1345\overset{+(31+32)}{\rightarrow}$$1408\overset{-(63+64)}{\rightarrow}1281\overset{+(127+128)}{\rightarrow}1536\overset{-(255+256)}{\rightarrow}1025\overset{+(511+512)}{\rightarrow}2048\overset{-(1023+1024)}{\rightarrow}1$

 

$-$ indicates we are going in left direction

$+$ indicates we are going in right direction.

$new\ distance = previous\ distance +( previous\ distance + 1)$

$+1$ is used to remove ambiguity when choosing next track.

 

Hence Option $D. \ 12 $ is correct answer.

Comments

@Arjun Sir, please read the 2nd comment.

Why we are not counting the first one ?  I have considered $1366$  also as a request. Please explain.

 

---

Let We are at some track, can't we have request to same track again?

If yes, then we have to count the initial one too...

After servicing this request, head move to either left or right which is indirectly meaning, head changes it's direction.

---

We can have request to same track but then the head won't change its direction and this violate the condition given in question.

Answer 3

video explanation .…………………

https://youtu.be/aEytXqw7_sI?t=688

 

Answer 4

Answer: B

Let the head start from 1024.

Requests are: 344, 854, 982, 1014, 1022, 1025, 1028, 1045, 1109, 1364

Cardinality: 10

Comments

1024 itself can be included in the set right? Then we start at 1024, first serve request for 1024 and then move to 1025 and so on. That will make the cardinality 11.

---

1024 should not be included in the set. Even in the first part of the question, 180th track which was the head was not included in the request set.

@Vaibhav