【文件属性】:
文件名称:算法上机!!
文件大小:16.54MB
文件格式:ZIP
更新时间:2016-06-19 10:43:40
凡哥 算法 代码
Practice 1
Date: Monday, March 18th, 2013
We highly encourage being environment friendly and trying all problems on your own.
Implement exercise 2.3-7.
Implement priority queue.
Implement Quicksort and answer the following questions. (1) How many comparisons will Quicksort do on a list of n elements that all have the same value? (2) What are the maximum and minimum number of comparisons will Quicksort do on a list of n elements, give an instance for maximum and minimum case respectively.
Give a divide and conquer algorithm for the following problem: you are given two sorted lists of size m and n, and are allowed unit time access to the ith element of each list. Give an O(lg m + lgn) time algorithm for computing the kth largest element in the union of the two lists. (For simplicity, you can assume that the elements of the two lists are distinct).
Practice 2
Date: Monday, April 1st, 2013
We highly encourage being environment friendly and trying all problems on your own.
Matrix-chain product. The following are some instances.
<3, 5, 2, 1,10>
<2, 7, 3, 6, 10>
<10, 3, 15, 12, 7, 2>
<7, 2, 4, 15, 20, 5>
Longest Common Subsequence (LCS). The following are some instances.
X: xzyzzyx Y: zxyyzxz
X:MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCALLAAQANKESSSESFISRLLAIVAD
Y:MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCTLLAAQANKENSNESFISRLLAIVAG
Longest Common Substring. The following are some instances.
X: xzyzzyx Y: zxyyzxz
X:MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCALLAAQANKESSSESFISRLLAIVAD
Y:MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCTLLAAQANKENSNESFISRLLAIVAG
Max Sum. The following is an instance.
(-2,11,-4,13,-5,-2)
Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph.
A multistage graph is a graph (1) G=(V,E) with V partitioned into K >= 2 disjoint subsets such that if (a,b) is in E, then a is in Vi , and b is in Vi+1 for some subsets in the partition; and (2) | V1 | = | VK | = 1.
Practice 3
Date: Monday, April 15th, 2013
We highly encourage being environment friendly and trying all problems on your own.
Knapsack Problem. There are 5 items that have a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem both as fractional knapsack and 0/1 knapsack.
A simple scheduling problem. We are given jobs j1, j2… jn, all with known running times t1, t2… tn, respectively. We have a single processor. What is the best way to schedule these jobs in order to minimize the average completion time. Assume that it is a nonpreemptive scheduling: once a job is started, it must run to completion. The following is an instance.
(j1, j2, j3, j4) : (15,8,3,10)
Single-source shortest paths. The following is the adjacency matrix, vertex A is the source.
A B C D E
A -1 3
B 3 2 2
C
D 1 5
E -3
All-pairs shortest paths. The adjacency matrix is as same as that of problem 3.(Use Floyd or Johnson’s algorithm)
Practice 4
Date: Monday, May 8th, 2013
We highly encourage being environment friendly and trying all problems on your own.
0/1 Knapsack Problem. There are 5 items that have a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem using back-tracking algorithm and try to draw the tree generated.
Solve the 8-Queen problem using back-tracking algorithm.
网友评论
- 很有参考价值 学到了
- 希望有用吧
- 实在不错,解决了我的大难题了
- 题目有部分变了,不过依旧很给力
- 大爱凡哥!给力!
- 写的很好,很有参考价值!
- 非常给力,可以用来参考思路哈哈哈
- 给力,确实是正需要的,作为算法的实现来说 ,特别有效
- 挺好的,但是有些题不太一样了
- 实在是不错,支持···
- 凡哥今年代码变难了。。。。。这个主要是c++,
- 凡哥给力,哈哈,今年的题目有所变化了。
- 凡哥很给力