算法导论

动态规划算法的设计可以分为如下四个步骤： 1 描述最优解的结构。 2 递归定义最优解的值。 3 按自底向上的方式计算最优解的值。 4 由计算出的结果构造一个最优解。

考虑对数组A中的n个数进行排序：首先找出A中的最小元素，并将其与A[1]中的元素进行交换。接着找出A中的次小元素，并将其与A[2]中的元素进行交换。对A中头n-1个元素继续这一过程。写出这个算法的伪代码，该算法称为选择排序（selection sort）。对这个算法来说，循环不变式是什么？为什么它仅需要在头n-1个元素上运行，而不是在所有n个元素上运行？以Θ形式写出选择排序的最佳和最坏情况下的运行时间。

如果一个节点是红的，则它的两个儿子都是黑的。

如果一个节点是红的，那它的父亲一定是黑的

红黑树的节点至少是红黑相间

We can easily make each of them run in time O using ordinary binary heaps. By using Fibonacci heaps, Prim’s algorithm runs in time O(E+VlgV ), improves over the binary-heap implementation if |V| is much smaller than |E|.

在程序的每一步中，从A[i]、 A[LEFT(i)和A[RIGHT(i)]中选出最大的，并将其下标存储在largest中。如果A[i]是最大，那么以i为结点的子树已经是最大堆，程序结束。否则，最大元素是的某个孩子结点，则交换[i]和原来的A[largest]的值。从而使i及其孩子都满足最大堆的性质。在交換，下标为 largest的结点的值是原来的A[i]，于是以该结点为根的子树又有可能会违反最大堆的性质。因此，需要对该子递归调用MAX- HEAPIFY。

The bug in the argument is that the "constant" hidden by the "big-oh" grows with n and thus is not constant. We have not shown that the same constant works for all n.

Describe a‚.nlgn/-time algorithm that, given a setSofnintegers and another integer x, determines whether or not there exist two elements in Swhose sum is exactly x.

We start with insertion sort

the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation

对一种数据结构的扩张过程可分为四个步骤： 1 选择基础数据结构 2 确定要在基础数据结构中添加哪些信息 3 验证可用基础数据结构上的基本修改操作来维护这些新添加的信息 4 设计新的操作

这样的一个函数组称为是全域的(universal)，如果对每一对不同的关键字$k,l\in{}U$...

It also makes a case that we should consider algorithms as a technology, along- side technologies such as fast hardware, graphical user interfaces, object-oriented systems, and networks.

A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them.

对于每个顶点v，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计。

算法是任何良定义的计算过程。

Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms ...

What are algorithms? Why is the study of algorithms worthwhile? What is the role of algorithms relative to other technologies used in computers? In this chapter, we will answer these questions.

Since the number of atoms in the observable universe is estimated to be about 10 ^ 80, which is much less than 2 ^ 65536, we rarely encounter an input size such that lg*n > 5.

A dynamic programming approach runs in polynomial time when the number of distinct subproblems involved is polynomial in the input size and we can solve each such subproblem in polynomial time.

Unlike dynamic programming, which solves the subproblems before making the first choice, a greedy algorithm makes its first choice before solving any subproblems.

A problem exhibits optimal substructure if an optimal soluton to the problem contains within it optimal solutions to subproblems. This property is a key ingredient of assessing the applicability of dynamic programming as well as greedy algorithms.

Many database systems use B-trees, or variants of B-trees, to store information.

van Emde Boas Tree

Subpaths of shortest paths are shortest paths.

Although the functionality of dynami-multithreading environments is still evolving, almost all support two features: neseted parallelism (spawn) and parallel loops.

Work Law: Tp > T1/P Span Law: Tp > T∞

Famous race bugs include the Therac-25 radiation therapy machine, which killed three people and injured several others, and the North American Blackout of 2003, which left over 50 million people without power.

For our purposes, we shall simply ensure that strands that operate in parallel are independent: they have no determincy races among them.