华南理工大学[算法设计]实验报告

华南理工大学《算法设计》实验报告

【Experiment requirement】

Use many sorting algorithm to sort the array that has n items. These items should be generated randomly. Use template to specify their types.

Given a binary tree T which has n elements, and a number called a, search if a exists in T or not.

Given a set of vertex and edges with weight in a directed graph G=(E,V), find the shortest path between two vertex in this graph.

Given some things with weight and profit, to finish the program to solve it using Greedy method and Search tree method.

Given a undirected Graph G=(V, E), to calculate the minimum spanning tree.

Initial the 9 grids with number 1 2 3 4 5 6 7 8, they are located randomly at these grids. Rearrange them such that they distributed like this {1 2 3 ; 8 4 ; 7 6 5}. Use MFC or C# to implement it.

【Experiment Implementation】

1. Quick Sort

2. Selection Sort

3. Bubble Sort

4. Insertion Sort

5. Shell Sort

Also, every sorting function are declared as a template. So the input of these functions can be int, double or other comparable type.

The size and elements are generated randomly.

Result:

All the sorting algorithm successfully sort the elements.

Binary search tree is a tree structure that the element of parent node is always larger than its left children and smaller than its right children. To define such a structure,

we first define a node structure:

Every node has an element and two children. There are some functions to get or set their value.

Then we define the binary search tree structure:

The tree has a root and node count. Functions in this class include: When we insert an element, we will first point to the root. Then compare with it. If it’s larger than this node, pass it to the right children, otherwise to left children. Compare

recursively until add it to the leaf.

determine whether a given node is leaf node or no.Just find that whether it has children. It’s not a leaf if so.

or not. It’s implemented by a recursion. Start from the root. If the element of this node equals to the given

element,

return true. If the element of this node is larger than the given element, pass it to the left children. Pass it to right children otherwise. If the leaf node is also not equal to the given elements, return false;

Result:

We can set the size to the tree, and all the elements are generated randomly. Now it’s 93 68 84 90 60. When we search 60, it shows that 60 exist. For 1, it shows that 1

does not exist.

Given a directed graph, the task of this problem is to find a shortest path from a given point x to a given point y.It can be implemented by Dijkstra algorithm or Floyd algorithm. I used Dijkstra in the experiment.

I define two structure to store the information of the graph. One for the weight, the other for the size.

To create a graph, I provide a auto way and a by-hand way. For the auto-way, the graph in P89 of our text book will be used. For by hand way , you can input the size of

the

graph and also their edges. I only shows the auto-way for convenient:

The Dijkstra algorithm is translated by the pseudo-code in the text book. :

Result: First automatically generate the graph and show it as a adjacency matrix. The start from Vo, this result is the same as in the text book. Then I can get that this function

works well.

This problem should be done for two case: 0/1 and non 0/1.For 0/1 case, I use Branch and bound method. For non 0/1 case, I use greedy method.

Non 0/1 case: I sort the packages by profit/weight, and select them form largest to smallest until current capacity will be larger than the given capacity if one more package is add. Then add the last one with a percentage that make

current capacity=capacity.

0/1 case: First I design a heap structure to represent the queue, there are build,shift,sort,insert,delete functions in it.

Also two node structure are designed to represent the search tree.

This algorithm follows the algorithm in the text book:

Data of packages can be generated automatically or by

hand:

And they will be sorted in terms of profit/weight:

Result shows that these two algorithms works well:

I reuse the graph structure in lab3(Shortest path problem). We should note that the graph is directed in lab5 but undirected in this lab, so I change graph[b][a] when we change graph[a][b] to make it undirected:

To build a minimal spanning tree, I follow the algorithm in the textbook:

I use a bool array to denote a set, true means exist, false means not exist.

Result: In this time, I generate the graph in page87 automatically, and you can see in the adjacency

matrix

that it is an undirected graph. The minimal spanning tree in the result is the same as in the textbook, and they follow the same order. So these functions work well.

I have done a part of it, but failed :-(

【Summary 】

After finishing this experiment I feel a great sense of relief. I spend a lot of time to do this experiment, and it is worth to do

so.

To be honesty, after I have learned the whole textbook of complier construction, I just know the definition of many

algorithms conceptually, but not sure about how to use them. By coding them on the computer, I am much more familiar with these algorithms and appreciate the essence inside them. This course is one of the most meaningful one. It is a combination of discrete mathematics, data structure, advanced

mathematics and so on, which can be applied to many fields of computer science. It help us to write more efficient and accurate code because we know more about efficient algorithm

This experience is an interestingone. In the past, we only need to write program on the computer. But this time, we

should design it well and write the structure on the paper and analysis it. The design part is much more important than the coding part in this experiment. For example, to find a shortest path you should think that how to represent a graph structure and how to apply the Dijkarst algorithm. You should use your brain and combine the knowledge we learn in the textbook to solve it. You should also know how to translate pseudo-code into other language.

All in all, I benefit a lot from this experiment. It not only help me understand some excellent algorithms but also improve my learning skills and practical ability.