One of the oldest applications used on the Internet is FTP, the file transfer pr

Question

One of the oldest applications used on the Internet is FTP, the file transfer protocol.
The definition for this protocol traces its roots back to 1971, before the
Internet even existed, and its formulation for the Internet was given in 1980. Its
primary purpose is for transferring files from one computer to another over the
Internet. Suppose you are writing an Internet file transfer application, similar
to FTP, and it is your job to write the code that takes a raw sequence of network
packets that were sent from one computer and reassembles that sequence
to reconstitute the file at the receiving computer. The n packets in the input are
numbered by their sequence numbers, which starts at some value, N, and goes incrementally in order to N + n 1. The packets are usually not received in
this order, however. Thus, to reconstruct the file at the receiving computer, your
method must re-order the packets so that they are sorted by their sequence numbers.
In studying example inputs, you notice that the input sequence of packets
is usually not that far from being sorted. That is, you notice in the examples you
studied that each input packet is proximate to its output position, which means
that if a packet is at position i in the input sequence, then its position in the sorted
output sequence is somewhere in the range [i50, i+50]. Describe a method for
sorting a sequence of n such packets by their sequence numbers in O(n) time,
assuming that every input packet is proximate to its output position.

Please use psudeocode.

Explanation / Answer

Solution:

The FTP packets are rearranged by sorting them. Generally they are passed as items with in queue. So for large data packet sort is best suitable. Packet sort is similar to insertion sort. It is stable and inplace algorithm which is very efficient in large lists. The Pseudocode sorts each element in every iteration.

Pseudocode:

for p = 1 to length(Arr)
temp = Arr[p]
q = p - 1
while q >= 0 and Arr[q] > temp
Arr[q+1] = Arr[q]
q = q - 1
end while
Arr[q+1] = temp[3]
end for

If n packets are there in the queue, then it will take n iterations to sort since in every iteration one element is sorted and placed in perfect place.

So complexity will be O(n)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.