1.  Consider the following list:

[6, 2, 4, 7, 1, 3, 8, 5]

Use it as input to the following sort algorithms:
a.	Show the results of each pass of Insertion Sort.

[6, 2, 4, 7, 1, 3, 8, 5]
[2, 6, 4, 7, 1, 3, 8, 5]
[2, 4, 6, 7, 1, 3, 8, 5]
[2, 4, 6, 7, 1, 3, 8, 5]
[1, 2, 3, 4, 6, 7, 8, 5]
[1, 2, 3, 4, 6, 7, 8, 5]
[1, 3, 2, 4, 6, 7, 8, 5]
[1, 3, 2, 4, 6, 7, 8, 5]







b.	Show the results of each pass of Bubble Sort.
[6, 2, 4, 7, 1, 3, 8, 5]
[2, 6, 4, 7, 1, 3, 8, 5]
[2, 4, 6, 7, 1, 3, 8, 5]
[2, 4, 7, 6, 1, 3, 8, 5]
[2, 4, 7, 1, 6, 3, 8, 5]
[2, 4, 7, 1, 3, 6, 8, 5]
[2, 4, 7, 1, 3, 8, 6, 5]
[2, 4, 7, 1, 3, 8, 5, 6]


2.  What are the main purposes of sorting?

Answer :
Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists. Sorting is also often useful for cannibalizing data and for producing human-readable output.

3.  When choosing a sorting method, what criteria influence our decision?
Answer:
Significant factors include past experiences, a variety of cognitive biases, an escalation of commitment and sunk outcomes, individual differences, including age and socioeconomic status, and a belief in personal relevance. These things all impact the decision making process and the decisions made.

4.  Quick Sort is characterized by “hard division, easy combination”. Merge Sort is characterized by “easy division, hard combination”. What do we mean by these descriptions?
Answer:
Merge sort requires a temporary array to merge the sorted arrays and hence it is not in-place giving Quick sort the advantage of space. Worst Cases: The worst case of quicksort O(n2) can be avoided by using randomized quicksort. It can be easily avoided with high probability by choosing the right pivot

5.  Give a natural language description of Bubble and Selection Sort. Illustrate your descriptions using an unsorted list of your choice, such as [5, 7, 13, 8, 9, 2, 4, 27].
Answer:
Bubble sort essentially exchanges the elements whereas selection sort performs the sorting by selecting the element. Another considerable difference between the two is that bubble sort is stable algorithm while selection sort is an unstable algorithm.


6.  In a programming language of your choice, specify the algorithm for Bubble Sort. If you need to remind yourself of the algorithm’s structure, do so with reference to a natural language description, then specify the algorithm in detail.

7.  In a programming language of your choice, specify the algorithm for Shell Sort with a gap size of 2. If you need to remind yourself of the algorithm’s structure, do so with reference to a natural language description, then specify the algorithm in detail.

8.  Using pseudo code and/or natural language descriptions specify Dijkstra’s shortest path algorithm. Annotate your algorithm to describe the algorithmic process.

9.  Supply the missing word or phrase:
a.  Trees are a form of _______ data structure
b.  Quick Sort makes O(n log n) comparisons to sort ___ items
c.  Linked lists are a form of ___________ data structure.
d.  Nearly all vertices are connected in a ______ graph.
e.  ________ is used by programmers to informally specify the structure of an algorithm.
f.  A digraph is a collection of nodes connected by ______ edges.
g.  An adjacency matrix is an n x n ______ matrix.
h.  Selection Sort uses _____ problem-solving.

10.  Indicate whether the following statements are true (T) or false (F):
a.  Vertices are adjacent if they are endpoints of the same edge. T or F
b.  In stack processing, only the last item in the sequence can be retrieved or deleted. T or F
c.  A complete graph is one in which every pair of vertices is connected by an edge. T or F
d.  Moving data items in a linked list has a time complexity of 0(n). T or F
e.  Shortest paths must be unique. T or F


11. Give the primary and secondary operations associated with the STACK ADT.

12. Give the primary and secondary operations associated with the QUEUE ADT.

13. What is the difference between a complete and a dense graph?
14. When is a graph traversal most efficient?
15. Consider the following unsorted list:

1   12  5  26  7  14  3  7  2

Apply Quick Sort up to the fist partition that places the pivot value in the correct position. The pivot is the first value 7.

16. Applying the median of three method, which value would become the pivot?