582484 Algorithm Libraries

Exercise 3

• wed 8.2.2006 10-12 | B119
• wed 8.2.2006 16-18 | B119

1. Verify experimentally that

   1. For vector, inserting in the end is fast but inserting in the beginning is slow.
   2. For deque, inserting in the beginning is fast but inserting in the middle is slow.
   3. For list, inserting even in the middle is fast.

   Use a timing method of your choice. The simplest is probably the Unix command time:

   > time your_program arguments
   

2. The three container adaptors stack, queue and priority_queue are implemented on top of a sequence.

   1. Explain why queue cannot be implemented on top of vector, and priority_queue cannot be implemented on top of list.
   2. Explain the default choice of the underlying container for each adaptor.

3. You and your friends often borrow money from each other. For each of your transactions (loan or payback), you write a line in a file containing the name of your friend (single word) and the sum (positive if you got money and negative if you gave money). For example:

   Ann 20
   Bob -50
   Ann -10
   

   Write a program that reads the file (hint: while (cin >> name >> sum)) and outputs your balance with each of your friends. For example:

   Ann 10
   Bob -50
   

4. Present a plan for your programming project

   • planned features, modules, etc.
     • possibly optional features (implemented if time allows)
   • who does what in the group
   • other relevant issues, for example, non-standard libraries used

   The plan should be detailed enough for estimating the difficulty. You will receive further advice based on the plan.

   Present the plan on paper or by sending email before the exercises. The format is free.

   The plan does not affect the grading of the project, but a timely return of the plan counts as an exercise.