1. Given a linked list of integer elements, construct a SELECTION SORT algorithm that puts the integer elements into ascending order. Note that a selection sort does O(n) copies. On each pass, the smallest element is placed into its proper position. For example, on the third pass:
Before: 5 10 55 22 65 12 75
After : 5 10 12 22 65 55 75
The code should NOT re-link nodes - just copy elements. Do not create a new list. The list does not have a dummy/header node.
Write code in the language of your choice. Here is the declaration of the data structure and the prototype in C:
typedef struct node *node_ptr;
struct node {
int element;
node_ptr next;
};
void selection_sort(node_ptr p);
2. A FULL node in a binary tree is a node that has exactly two non-null children. Declare a suitable data structure for a binary tree node and write a RECURSIVE function, in the language of your choice, that returns the number of full nodes in a binary tree.
3. Consider the following problems and their algorithmic solutions in the worst case. State the tightest BIG-OH performance of each algorithm, i.e., THETA (Q). Do not include any proofs, just list the results.
a) Sorting: use n, the number of elements to sort.
1) Quicksort
2) Mergesort
3) Radix sort
b) Graphs: use n, the number of nodes, and m, the number of edges, appropriately.
4) Depth-First Search Spanning Tree
5) Dijkstra's Shortest Path
6) Dijkstra's/Prim's Minimum-Weight Spanning Tree
7) Kruskal's Minimum-Weight Spanning Tree
c) Matrix Multiplication: use n, the size of the square matrices.
d) Longest Common Subsequence Problem (String Matching): use m, the length of the substring, and n, the length of the string being searched.
9) Straightforward (Brute Force) Comparison
10) Knuth-Morris-Pratt Algorithm
4. Recall these definitions:
HC (Hamiltonian Circuit)
Instance: Undirected graph G = (V,E)
Question: Does G contain a Hamiltonian circuit (a path that begins at some vertex, passes through each other vertex exactly once, and returns to the starting vertex)?
TSP (Traveling Salesman)
Instance: Set C of m cities, with a positive integer distance d(ci, cj) for each pair of cities ci,cj, in C, and a positive integer B.
Question: Is there a tour of C having length B or less? (A tour is a circuit that starts and ends at some cstart visiting each city exactly once and then returns to cstart. )
a) Prove carefully and completely: HC <=p TSP
b) If it is known that HC is NP-complete, what can be said about TSP? Explain carefully and completely.
c) If it is known that TSP is NP-complete, what can be said about HC? Explain carefully and completely.
