How JustAnswer Works:
  • Ask an Expert
    Experts are full of valuable knowledge and are ready to help with any question. Credentials confirmed by a Fortune 500 verification firm.
  • Get a Professional Answer
    Via email, text message, or notification as you wait on our site.
    Ask follow up questions if you need to.
  • 100% Satisfaction Guarantee
    Rate the answer you receive.
Ask ATLPROG Your Own Question
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
Type Your Programming Question Here...
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
[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
xc  head of 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 ::

Task 1:
For each of std::list, std::map , std::unordered_map document and
explain the guaranteed performance for
 element insertion
 element lookup
Task 2:
Assume that the std::containers of C++ on a typical installation can manage datasets of the
suggested magnitude (~3 x 10
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.
Task 3:
Establish that your installation will cope with 3 x 10 ^6individuals^2

Task 4:
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.

Task 5:
Implement the solution suggested by the Answers in TAOCP and compare its performance
a) the claimed performance of the book solution
b) your naïve implementation
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.

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!

Customer: replied 4 years ago.

Yes Please I would like another expert to look at it

Expert:  Lindie-mod replied 4 years ago.

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

Expert:  Lindie-mod replied 4 years ago.
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?

Thank you for your patience,
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.


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,


Related Programming Questions