=====================================================
 582484 Algorithm Libraries
=====================================================

--------------------
Exercise 3 solutions
--------------------



1.
   Note that we cannot use ``front_insert_iterator`` for vector because
   it doesn't have ``push_front()`` as a member. So, for uniformity, we 
   haven't used insert_iterators at all.

   .. include:: teht1.cpp
      :literal:


   In the following table 100000 integers were inserted in the three
   containers in different positions. The times are in seconds.

   .. include:: timing.txt
      :literal:


2. 

   a.
   
	The essential operations of a queue are insertion at the back
	and removal from the front. The vector container doesn't allow
	insertion and removal from the front (at least, not efficiently).
	Therefore deque is used instead.

	List is not a random access container. Usually, priority queues
	are implemented as heaps (like binary heap), and a heap is represented
	as a tree, which is stored in an array for efficiency. Therefore
	random access property is needed.

   b. 
   
	A ``stack`` can be implemented in terms of list, deque or vector.
	A deque is the default choice. It is obviously more efficient
	than list. In addition, deque is able to automatically decrease
	its capacity; in vector one can only increase capacity, not
	decrease it.

	As said in the first part of the question, using vector to
	implement a ``queue`` is out of the question. But list and
	deque are possible candidates since they both are front
	and back insertion sequences. Deque is chosen for default value
	because of efficiency.

	``Priority queue`` needs to have a random access container as its
	underlying sequence, therefore a list will not do. A vector
	is preferred over deque for efficiency reasons. Speed is more
	essential here than with stack because all stack operations
	are *constant time*, but in a priority queue a ``push``-operation can 
	have *logarithmic complexity*. Therefore the individual random
	access operations used in performing the priority queue operations
	need to be fast. A deque is a more complicated data structure
	than a vector, and that is why its random access operations
	are also a bit slower.


3. Accounting

   .. include:: teht3.cpp
      :literal: