English
资源说明：Experiment 1 The QuickSort Algorithm
1.Introduction to the quicksort algorithm
In order to sort the input data sequence S, we can do like below:
1)Select one number q and then divide the sequence S into three sub-suquences: S1 in which all of elements are less than q, S2 in which all of elements are equal to q, and S3 in which all of elements are larger than q;
2)Then to sort S1 and S3 with the same algorithm using recursive call itself.
2. Experimental Purposes
（1）Learn the sorting algorithms.
（2）Understand the difference between the quicksort algorithm and other sorting algorithms, such as: insertion sorting algorithm, straight selection algorithm, etc..
（3）Simulate these algorithms using computer with high-level languages.
（4）Solve some sorting problem with different sort algorithms.
3. Abstract of Experiment contents
Use QuickSort algorithm to sort the array S that has n elements and constructed by the random() function. To compare the result with ones solved by other sorting algorithms, such as Straight selection sort, insert sort, etc., and understand the difference among them and know how to select some better sorting algorithm while solving some sorting problem.
4. Experimental Requirements
1)The template should be used for all kinds of data type, such as: integer, real, double, etc. in the program;
2)Programs should be made by Object-Oriented Programming (OOP) method;
3)The results should be compared with ones of other algorithms, such as: Straight selection sort, insert sort, Heapsort, etc., and draw the graph to find their differences.
Figure 1 The difference between quicksort and insertion sort
4)Write down the report in which there should be the execution results of the program.
5. Example code with C++
……….
void myquicksort(int* A, int l,int r)
{
if(l>=r)
return ;
int i=l,j=r;
int temp; //Use it to divide A into S1, S2,and S3
…….
//Partition S into S1, S2 and S3 here
…….
myquicksort(A,l,i-1); //recursive call for the left part
myquicksort(A,i+1,r); //recursive call for the right part
}
…………….
Experiment 2 The Knapsack Problem Solved by Greedy Algorithm
1.Introduction to the Greedy algorithm
(1)Suppose that a problem can be solved by a sequence of decisions.
(2)The greedy method has that each decision is locally optimal.
(3)These locally optimal solutions will finally add up to a globally optimal solution.
2.Experimental Purposes
（1）Understand what is the knapsack problem and the 0/1 knapsack problem;
（2）Learn what is the greedy selection strategy and the greedy algorithm;
（3）Learn how to solve some optimal problem with greedy algorithm;
（4）Compare the greedy algorithm with some other algorithms such as: tree search algorithm.
3. Experimental contents
（1）Given a knapsack with the capacity M and some items with its weight and profit, to solve it using Greedy method and Search tree method.
（2）Then compare this results with ones of 0/1 Knapsack problem based on the capacity of M.
（3）These items could be given likes:
•M = 30,
•(P1, P2, P3, P4, P5, P6)=(25,24,15,18,22,35)
•(W1, W2, W3, W4, W5, W6) = (12, 15, 10, 8, 9, 11)
（4）These items could constructed by the ramdom() function in some range, such as:
(Wmin, Wmax) and (Pmin, Pmax) and the number of item could be more.
4. Experimental Requirements
1)The template should be used for all kinds of data type, such as: integer, real, double, etc. in the program;
2)Programs should be made by Object-Oriented Programming (OOP) method;
3)Use Greedy method and Search tree method to solve this problem.
4)And compare the results between the knapsack problem and the 0/1 knapsack problem.
5)Write down the report in which there should be the execution results of the program.
Experiment 3 The Prim Algorithm for MST
1.Introduction to the Prim Algorithm for MST
(1) The definition of Minimum spanning trees (MST):
•G = (V, E) is a weighted connected undirected graph;
•Spanning tree is S = (V, T), T E, undirected tree;
•Minimum spanning tree (MST) is a spanning tree with the smallest total weight.
(2) The Prim Algorithm for finding MST:
Step 1: x V, Let A = {x}, B = V - {x}.
Step 2: Select (u, v) E, u A, v B such that (u, v) has the smallest weight between A and B.
Step 3: Put (u, v) in the tree. A = A {v}, B = B - {v}
Step 4: If B = , stop; otherwise, go to Step 2.
2. Experimental Purpose
(1)Understand what is the Minimum spanning trees (MST);
(2)Learn what kinds of algorithms can be used to find MST, such as: Kruskal and Prim algorithms;
(3)Compare the difference between these two algorithms;
3. Experimental Contents
(1) Given a undirected Graph G=(V, E) like below, to calculate the minimum spanning tree using Kruskal’s algorithm and Prim’s algorithm.
4. Experimental Requirement
1)The template should be used for all kinds of data type, such as: integer, real, double, etc. in the program;
2)Programs should be made by Object-Oriented Programming (OOP) method;
3)Use using Kruskal’s algorithm and Prim’s algorithm to solve this problem.
4)And compare the results between these two algorithms and the difference of selection processes.
5)Write down the report in which there should be the execution results of the program.
Experiment 4 The Tree Search Algorithm
1.Introduction to the Tree Search Algorithm
The solutions of many problems may be represented by trees and therefore solving them becomes a tree searching problems. We can search this tree to get the solution for this problem.
2.Experimental Purpose
（1）Understand the Tree Search algorithm.
（2）Learn the solution expression of some problems by A Tree data structure.
（3）Understand what kinds of problems can be solved by this algorithm.
（4）Realize the source code for this algorithm.
（5）Understand different search strategies, such as: the Breadth-first search(BFS) ,the Depth-first search(DFS) and the Best-first search(BFS) Search strategies etc., and compare the difference of results solved by them.
3. Abstract of Experiment contents
Given a random initial node with 8 numbers from 1 to 8 and then use the tree search algorithm to find if there is the goal node or not after moving them.
Figure 2 The initial node and goal node for the tree search algorithm
4.Experimental Requirements
1)The template should be used for all kinds of data type, such as: integer, real, double, etc. in the program;
2)Programs should be made by Object-Oriented Programming (OOP) method;
3)Use different strategies to perform this algorithm, such as: the Breadth-first search(BFS) ,the Depth-first search(DFS) and the Best-first search(BFS) Search strategies etc..
4)And compare the result difference solved by them.
5)Write down the report in which there should be the execution results of the program.
Experiment 5 A Shortest-Path problem solved by Dynamic programming Algorithm
1.Introduction to the Shortest-Path Problem and Dynamic programming Algorithm
1)Given a set V of vertices and a set E of edges with weights in a multistage undirected graph G=(E,V), please find the shortest path between any two vertices.
2)Dynamic Programming is an algorithm design method that can be used when the solution to a problem may be viewed as the result of a sequence of decisions and this algorithm is a very useful technique to solve many combinatorial optimization problems. In order to solve a problem by using dynamic programming, we should know how to:
Find out the recurrence relations.
Represent the problem by a multistage graph.
2. Experimental Purpose
（1）Know the shortest-path problem for multistage undirected graph can be solved by the dynamic programming algorithm.
（2）Learn what is the dynamic programming strategy and the method of this algorithm.
（3）Learn how to find out the recurrence relations.
（4）Learn how to represent the problem by a multistage graph.
3. Abstract of Experiment contents
1) Given a set V of vertices and a set E of edges with weights in a multistage undirected graph G=(E,V) like below, please find the shortest path between any two vertices using dynamic programming algorithm.
Figure 3 The multistage undirected graph G
2) Define a function d(V1, V2): the minimum distance between vertex V1 and V2.
4. Experimental Requirements
1)The template should be used for all kinds of data type, such as: integer, real, double, etc., in the program;
2)Programs should be made by Object-Oriented Programming (OOP) method;
3)Use the backward and forward approaches to perform this algorithm.
4)And compare the efficiency between the backward and forward approaches.
5)Write down the report in which there should be the execution results of the program.
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
