• 100% Satisfaction Guarantee

ATLPROG, Computer Software Engineer
Category: Programming
Satisfied Customers: 7260
Experience:  MS in IT.Several years of programming experience in Java C++ C C# Python VB Javascript HTML
44910485
ATLPROG is online now

# a Soft eng question problem .. The incomparable Professor

### Customer Question

a Soft eng question problem ..

The incomparable Professor Knuth in (Knuth, 1998)(pp.9) eloquently describes the problem of sorting when the ordering of keys is not obvious; this is reproduced below.

Three million men with distinct names were laid end-to-end, reaching from New York to XXXXX participant was given a slip of paper on which he wrote down his own name
and the name of the person immediately west of him in the line. The man at the extreme
western end of the line didn’t understand what to do, so he threw his paper away; the
remaining 2,999,999 slips of paper were put in a huge basket and taken to the National
Archives in Washington, D.C. Here the contents of the basket were shuffled completely and
transferred to magnetic tapes.
At this point an information scientist observed that there was enough information on the tapes
to reconstruct the list of people in their original order. And a computer scientist discovered a
way to to do the reconstruction with fewer than 1000 passes through the data tapes, using only
sequential accessing of tapes and a small amount of random-access memory. How was this
possible?
[In other words, given the pairs (xi, xi+1) for 1 ≤ i < N, in random order, where the xi are
distinct, how can the sequence x1 x2….xN be obtained, restricting all operations to serial
techniques, suitable for use on magnetic tapes. This is the problem of sorting into order when
there is no easy way to to tell which of two given keys precedes the other;

A naïve solution is easy to conceive, viz:
Consider the papers to be a collection of (Name, Name) tuples, both the successor (westerly
neighbour) and the predecessor (easterly neighbour) can be established from these tuples.
identify an individual xc
append xc to empty list
while xc has westerly neighbour
xc  westerly neighbour of xc
append xc to list
while xc has easterly neighbour
xc  easterly neighbour of xc
prepend xc to list

If these tuples are arranged in a searchable data structure, the performance of the solution depends
on the building and the searching of the data structure.

here what I want ::

For each of std::list, std::map , std::unordered_map document and
explain the guaranteed performance for
 element insertion
 element lookup
Assume that the std::containers of C++ on a typical installation can manage datasets of the
suggested magnitude (~3 x 10
6
tuples); predict (& explain your reasoning) the performance
of each of the containers in the context of the naïve solution to the Knuth problem. Choose
and justify the container you consider best.
Establish that your installation will cope with 3 x 10 ^6individuals^2

Implement a C++ version using your chosen container and use it to generate empirical
performance data. Interpret the results in the context of your predicted performance.

Implement the solution suggested by the Answers in TAOCP and compare its performance
with
a) the claimed performance of the book solution
For this task, you should respect, if possible, the “file operations only” constraint, but you
can interpret it to allow the use of sequence containers as long as they do not support
random access iterators.
Submitted: 4 years ago.
Category: Programming
Expert:  Russell H. replied 4 years ago.
I notice that your question has not received a response for some hours, and would like to check as to several points about your question:

- Do you still need assistance with the issue you are asking about?

- Is it true that your question is basically a request to complete (or assist you in completing) the Task 1 through Task 5 listed in your question? [ - If so, I cannot assist you with Task 4 at all, since I have insufficient knowledge of C++ programming.]
- Or is it that your question is about something else? let me know, thanks.

Customer: replied 4 years ago.
Hello,

Thanks for reply, yes i do
Ok you can help me with task 1,2,3 and 5 if you could with reference if possible.. And i will do task 4 my self..

Thank you
Expert:  Russell H. replied 4 years ago.
Upon further examination I doubt I can help you with any of the questions, for it's all about C++ and the specific terms do some of them mean nothing to me - indicating that my experience level is unsuited to any part of this question.

I hope I have at least helped to clarify the question and what you wish to have done as an answer to it, for the next Expert to consider taking up this question. I am Opting Out (opening it to any other Expert who has something to contribute toward an answer to your question.)
Expert:  Lindie-mod replied 4 years ago.
Hi, I’m a moderator for this topic. It seems the Professional has left this conversation. This happens occasionally, and it's usually because the Professional thinks that someone else might be a better match for your question. I've been working hard to find a new Professional to assist you right away with your Programming issue, but sometimes finding the right Professional can take a little longer than expected.

I wonder whether you're OK with continuing to wait for an answer. If you are, please let me know and I will continue my search. If not, feel free to let me know and I will cancel this question for you. Thank you!

Lindie
Customer: replied 4 years ago.

Yes Please I would like another expert to look at it

Expert:  Lindie-mod replied 4 years ago.
Hi

Thank you for your continued patience. We will continue the search for a Professional for you.

Lindie
Expert:  Lindie-mod replied 4 years ago.
Hello,
I apologize as we have not yet been able to find another Professional to assist you. Would you like me to continue to search for someone to assist you or would you like for me to close your question at this time?

Lindie
Customer: replied 4 years ago.
Yes please i would be happy to look for sm one else to help..
Thank you
Expert:  Rachel-Mod replied 4 years ago.

Hello,

Please understand it is rare for us not to be able to find the right Professional to assist our customers. We can either return your good faith deposit to the original funding source, or we can keep your deposit on your account here for future questions.

Please let me know how you wish to proceed and again I apologize for any inconvenience this may have caused.

I hope you will give JustAnswer a try again in the future,

Rachel

### What Customers are Saying:

• My Expert answered my question promptly and he resolved the issue totally. This is a great service. I am so glad I found it I will definitely use the service again if needed. One Happy Customer
< Previous | Next >
• My Expert answered my question promptly and he resolved the issue totally. This is a great service. I am so glad I found it I will definitely use the service again if needed. One Happy Customer
• Wonderful service, prompt, efficient, and accurate. Couldn't have asked for more. I cannot thank you enough for your help. Mary C.
• This expert is wonderful. They truly know what they are talking about, and they actually care about you. They really helped put my nerves at ease. Thank you so much!!!! Alex
• Thank you for all your help. It is nice to know that this service is here for people like myself, who need answers fast and are not sure who to consult. GP
• I couldn't be more satisfied! This is the site I will always come to when I need a second opinion. Justin
• Just let me say that this encounter has been entirely professional and most helpful. I liked that I could ask additional questions and get answered in a very short turn around. Esther
• Wonderful service, prompt, efficient, and accurate. Couldn't have asked for more. I cannot thank you enough for your help. Mary C.

• ### ATLPROG

#### Satisfied Customers:

7260
MS in IT.Several years of programming experience in Java C++ C C# Python VB Javascript HTML
< Previous | Next >

### ATLPROG

#### Satisfied Customers:

7260
MS in IT.Several years of programming experience in Java C++ C C# Python VB Javascript HTML

### LogicPro

#### Satisfied Customers:

5514
Expert in C, C++, Java, DOT NET, Python, HTML, Javascript, Design.

### lifesaver

#### Satisfied Customers:

936
Several years of intensive programming and application development experience in various platforms.

### ehabtutor

#### Satisfied Customers:

766
Bachelor of computer science, 5+ years experience in software development, software company owner

### Eljon

#### Satisfied Customers:

558
Founder of StockCanvas.com

### Rafael Martins

#### Satisfied Customers:

446
Desktop, Mobile and Web Developer. 7+ years of experience. Creative solutions provider.

### The-PC-Guy

#### Satisfied Customers:

320
Extensive Knowledge in PHP, MYSQL, CSS & Javascript