代写C++代码 代做C++程序 C++辅导 C++教学

C++网络家教 远程写代码 在线Debug 讲解答疑 不是中介,本人直接写

微信: ittutor QQ: 14061936 Email: ittutor@qq.com

导航

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 

 

 

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 

 

 

 

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. 

 


相关推荐