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

Did you mean 1366 also included ?

But note that, it is start of the sequence you assumed.. So it is not counted as request.

---

I have assumed that $1366$ is the 1st request and coincidentally head was also pointing to it.

Request are generated as $1366,1365,1368,1361,1376,1345,1408,1281,1536,1025,20148,1$ and the head is pointing to $1366$ initally.

---

Convincing point, but still have doubt about that request.

---

@Satbir then it violate the requirement that head changes its direction after every request. 

I just modified the question to remove the part which was actually meant for question number 82.

---

@Arjun Sir, in my answer the directions are denoted by + and - signs and they are changing after processing every request.

Please correct me if wrong.

---

The question is whether to count the first one or not -- it shouldnt be

---

@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