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.