All students are required to do all three programming projects
and present the results
Students should team up (maximum 2 students per team )
to work collaboratively.
- Project 1. Sorting and Median Finding. (due March 1, 2016)
-
(a) Implement selection sort, insertion sort, bubble sort.
Run these 3 sorting codes on arrays with
sizes=1000, 3000, 10000, 30000, 100000
generated by random numbers (using integers).
(You need to run 10 times for each size to get the average)
(b) Implement quicksort
On quicksort algorithm, investigate the following options:
(i) implement random pivot find, and
(ii) when n is small, stop recursion and invoke the insertion sort.
(c)
Implement heapsort including heap data structures; update the structures
once the key values are changed.
(d) Implement count sort.
(e)
Run these 3 sorting codes (heap, quick, count) on arrays with
sizes=1000, 3000, 10000, 30000, 100000, 300000,
generated by random numbers (using integers).
(You need to run 10 times for each size to get the average)
(f) Implement the median finding "random_select()" (Section 9.2).
(g) Implement the median finding "worst case linear algorithm" (Section 9.3).
(h)
Run these median finding codes on arrays with
sizes=1000, 3000, 10000, 30000, 100000, 300000,
generated by random numbers (using integers).
(You need to run 10 times for each size to get the average)
- Project 2. Graph basic algorithms:
graph generation, DFS, Connected Components,
Minimum Spanning Tree, bridges.
(due May 3 2016)
-
(a) Generate graphs using adjacency matrix representation.
1. Generate undirected graph with unit weight and N=30.
Use any plot software to plot the graph.
2. Generate directed graph with unit weight and N=30.
Use any plot software to plot the graph.
(b)
Implement the DFS algorithm.
Test this code on a random graph with N=100.
(c)
Modify the DFS algorithm to make it able to detect/find
connected components (CC) of a graph.
Test this code on a random graph with N=100.
(d)
Implement the Union-join data structure for joining disjoint sets.
Use this to find connected components (CC) of a graph.
Test this code on a random graph with N=100 with several CCs.
(e)
Implement Kruskal's Algorithm, using the data structure in (b).
(f)
Implement heap data structures, including heapsort, and update the structures
once the key values are changed.
(g)
Implement Prim's Algorithm,
using the min-heap data structure in "extract-min(Q)".
(h)
Run the two algoriths on several graphs, with graph sizes (# of nodes) 100,
200, 400, 800, 1600, 3200.
(You need to run 5 times for each size to get the average)
Measure the time and plot them.
What is the complexity ?
(i)
Modify DFS to compute all bridges in a graph.
Test this code on a random graph with N=1000.