CE2001/CZ2001 Algorithms
General Notes for Example Classes 2 – 4
The next three example classes intend to reinforce your understanding of algorithms
through hands-on experience of implementation and empirical analysis.
Before an example class, each group should have finished the coding and testing of
Java program on your own computers, and written a report describing the
implementation and experiments. The first 30 – 40 minutes of the example class may be
used to test and finalize the programs and presentation materials. Then, representatives
are chosen by each group to give a demo of their program and experimental results. By
the end of the example class, each group should submit to tutor: (1) the report (in
softcopy or hardcopy); (2) source code, executable and testing data (in softcopy).
Each member of the group should know the program and presentation materials well
enough to be able to act as a backup presenter or to help answer questions in the
class.Thus if someone is suddenly ill, someone else should be able to step forward and
do the presentation for their sick group mate. Otherwise, the performance of the group
will suffer and therefore the grade.
Example Class Two (Week 6 – Week 7)
Applications and Empirical Analysis of Searching Algorithms
Study and identify examples where binary search and/or hashing algorthms are
used in the process to solve a problem. If real world data sets are not available,
you may generate synthetic data sets for use in your experiments.
Implement the algorithms of binary search and at least one variation of hashing
methods in Java programs.Your programs should include a counter that tracks
the number of comparisons in searching.
Your presentation and report should include
1. Description of the problem domain and data sets
2. Demo of your implementation of binary search and hashing algorithms to
search for an entity in the data sets
3. Statistics on number of comparisons and average CPU time taken to
search in data sets of various sizes, ranging from 1000 to 1,000,000 (be
sure to consider both successful and unsuccessful cases)
4. Conclusion on time complexity comparison between binary search and
hashing algorthms
CE2001/CZ2001 Algorithms
Example class
Fall
2014
2
Example Class Three (Week 9 – Week 10)
Integration of Mergesort and Insertion Sort
As a divide-and-conquer algorithm, Mergesort breaks the input array into sub-arrays
and recursively sort them. When the sizes of sub-arrays are small, the overhead of
many recursive calls makes the algorithm inefficient. This problem can be remedied by
choosing a small value of S as a threshold for the size of sub-arrays. When the size of a
sub-array in a recursive call is less than or equal to the value of S, the algorithm will
switch to Insertion sort, which is efficient for small input. A pseudocode of the modified
Mergesort is given below:
void mergeSort(Element E[], int first, int last, int S)
{
if (last – first > S) {
int mid = (first + last)/2;
mergeSort(E, first, mid, S);
mergeSort(E, mid + 1, last, S);
merge(E, first, mid, last);
} else {
insertionSort(E, first, last);
}
}
Implement the original version of Mergesort (as learned in lecture) and the above
modified version of Mergesort. Compare their performances in the numbers of key
comparisons and CPU times. A suggested value of S is 10, but you can also try other
values for S.
For simplicity, suppose the input elements are integers and the goal is to sort input
numbers into the increasing order. Your report and presentation should include (but not
limited to):
1. Generate your own input data sets of various sizes, ranging from 1000 to
1,000,000 random integers. Then, count the numbers of key comparisons and
CPU times taken by your Java program on the data sets. Describe how running
times increases with input sizes when running the two versions of Mergesort
algorithm.
2. Carry out experiments to study how the different values of S will affect the
performance of the modified algorithm.
CE2001/CZ2001 Algorithms
Example class
Fall
2014
3
Example Class Four (Week 11 – Week 12)
Application of Breadth-first search Algorithm
Construct an undirected graph to represent non-stop airline flights between cities in the
world (a hypothetical graph for Asia Pacific is given below). In your graph, please add
more cities and flights to make it more realistic. It should contain at least one pair of
cities, between which there is no non-stop flight, but there is at least one route (or path)
between them.
Implement the Breadth-first search (BFS) algorithm to find a route between two cities
with the minimum number of stops. That is, when user inputs the names of two cities,
your program should return one route with the smallest possible number of stop(s). If a
non-stop flight is avialble, it will just return the start city and end city.
In your report and presentation, please include (but not limited to):
1. Measure the CPU times of your program on graphs of different sizes, and
analyze how the running times depend on the numbers of cities and non-stop
flights.
2. Explain whether Depth-first search (DFS) algorithm can be used in place of BFS,
why or why not.
Note for Example class 4
Any student who has not done any presentation for his/her group must present.