计算机基础理论_计算机类_最新资料_得益网

中学几何研究

2008-08-27 18:04:15

本书是“数学教育系列教材”（普通高等教育“十五”国家级规划教材）之一，是关于中学几何内容及其教学理论与实践的概述，包括绪论、度量几何学、欧氏几何的公理化体系、平面几何证题方法、平面几何名题欣赏、中学几何教学的综述、立体几何研究与解题、解析几何研究与解题、球面几何学初步以及几何定理的机器证明等内容。
教材从内容上努力体现当代数学的核心观念，破除过度形式化的体系，返璞归真，平实近人；在叙述上紧密配合国家数学课程改革的需要，为一线教师的数学教学服务。
本书由来自全国多所高等师范院校的专家、学者共同完成，其读者对象是高等师范院校的数学系学生以及有志于从事数学教育的大学生，也十分适合作为中小学教师培训和继续教育用书。

目录
第一章　绪论：几何学——时间与空间的数学
第一节　几何学的进步概说
第二节　欧氏几何与非欧几何
第三节　欧氏空间和坐标几何
第四节　微分几何与黎曼几何
第五节　四维时空、Einstein狭义相对论、广义相对论
第二章　度量几何学
第一节　线段和圆弧的长度
第二节　面积和体积
第三节　球的体积和表面积
第四节　从长度到测度
第五节　三角学：定量化的几何
第六节　分形几何概观
第三章　欧氏几何的公理化方法
　第一节　公理化思想方法的内涵与价值
　第二节　直观性公理化时期——《几何原本》
　第三节　思辨性的公理化时期——非欧几何
　第四节　形式主义的公理化时期——希尔伯特的《几何基础》
　第五节　结构主义的公理化时期——布尔巴基的《数学原本》
　第六节　张景中欧氏几何公理体系
　第七节　中学数学教材中的公理系统
第四章　平面几何名题欣赏
　第一节　几个著名定理
　第二节　几个著名不等式
第五章　平面几何问题的证明
　第一节　证题的一般思路
　第二节　面积法与面积坐标
　第三节　向量法与复数法
　第四节　几类问题的证明方法
　第五节　几何轨迹与尺规作图
第六章　中学几何教学综述
　第一节　国际视野：平面几何教学的历史变迁
　附录用投影法证明勾股定理
　第二节　半个世纪以来的中国平面几何教学
　第三节　平面几何教学与理性思维能力的培养
　第四节　范·希尔的6个几何思维水平
　第五节　变换几何与几何教学改革
　附录一中学里的几何变换
　附录二矩阵与变换
第七章　立体几何研究与解题
　第一节　立体图形、截面图形、投影图形的画法
　第二节　直线、平面的平行、垂直关系的对偶性
　第三节　空间向量的数量积和向量积
　第四节　求解立体几何问题的向量法与综合法
　第五节　立体几何的教学
　第六节　求解立体几何问题的算法化表述
　第七节　立体几何例题求解及点评
第八章　平面解析几何研究与解题
　第一节　坐标系和坐标变换
　第二节　曲线、方程、函数
　第三节　曲线的生成与类型的判别
　第四节　射影几何与平面解析几何
　第五节　平面解析几何的教学
　第六节　二次曲线的实际应用
　第七节　解析几何例题求解与点评
第九章　球面几何学初步
　第一节　球面几何的有关概念
　第二节　球面三角
　第三节　球面坐标
　第四节　球面几何与双曲几何
第十章　几何定理的机器证明
　第一节　数学机械化与我国数学家所取得的成就
　第二节　吴文俊几何定理证明的机械经方法
　第三节　张景中消点算法

《电脑常见故障处理》视频教程

2008-08-26 21:57:52

新电脑课堂－－《电脑常见故障处理》，分3部分，第一部分计算机硬件基础(掌握处理故障时，必须的硬件知识，动漫人物伴学)，第二部分详解故障实例(实战演练，手把手的教，同样是动漫人物伴学)，第三部分电子书一套。（普及国人计算机实用水平，低价10分放送）

超级容易学电脑——电脑故障恢复简易行

2008-08-26 21:01:11

用电脑时，谁能保证不发生电脑故障呢？有了故障怎么办？拿去维修吗？其实很多时候都没有那个必要。有了本教学光盘，电脑故障恢复没有你想象的那么难，自己DIY就OK！在长达4个小时的超清晰多媒体教学视频中，详细阐述了电脑故障概述，死机故障处理，BIOS与主板故障原理与解决，CPU、内存、硬盘、显卡、声卡、软驱、光驱、外围设备、电源等故障原理与相应解决方案。由0基础晋升到各大计算机维修中心专业工作人员的水平！（普及国人计算机维修DIY，本视频资料超低价5分送给大家！觉得好的话，顶一下，大家赚点积分也不容易，很多人一天才加一分，更多计算机实用精彩视频超低价甚至免费放送...敬请期待>>.）

组合数学（北大版）

2008-08-23 20:17:56

本书系统地介绍了组合数学知识。主要内容有排列与组合、生成排列和组合、二项式系数、容斥原理与鸽巢原理、递推关系和母函数、特殊计数序列、图与网络、Pólya 计数法、线性规划和组合最优化等。此外，每章后均提供了一定数量的习题，并附了习题的参考答案。
　　本书省略了部分理论上的证明，突出对结论的应用，特别侧重于将组合数学方法过渡到计算机算法，故比较适合于高职高专院校计算机专业学生选用，同时，也可作为高职高专学校选作数学建模教材。
目录
第1章排列与组合
1.1 加法法则与乘法法则
1.2 排列与组合
1.3 多重集的排列与组合
1.4 习题
第2章生成排列和组合
2.1 生成排列
2.2 生成组合
2.3 习题
第3章二项式系数
3.1 二项展开式
3.2 牛顿二项式定理和多项式定理
3.3 习题
第4章容斥原理
4.1 容斥原理
4.2 容斥原理的应用
4.3 鸽巢原理
4.4 Ramsey定理
4.5 习题
第5章递推关系与母函数
5.1 递推关系与Fibonaeei数列
5.2 常系数线性齐次递推关系
5.3 常系数线性非齐次递推关系
5.4 用母函数法求解递推关系
5.5 习题
第6章特殊计数序列
6.1 Catalan数
6.2 差分序列和stiding数
6.3 分拆数和Ferrer图象
6.4 习题
第7章图与网络
7.1 基本概念
7.2 欧拉图
7.3 哈米尔顿图
7.4 最短路问题
7.5 最小树问题
7.6 最大流问题
7.7 匹配
7.8 习题
第8章 P6IFa计数法
8.1 置换群与对称群
8.2 Burnside定理
8.3 p61ya计数公式
8.4 习题
第9章线性规划
9.1 线性规划基本概念
9.2 单纯形法
9.3 初始基本可行解的确定与退化情形的处理
9.4 修正单纯形法
9.5 对偶理论
9.6 习题
第10章组合最优化
10.1 运输问题
10.2 分派问题
10.3 背包问题
10.4 车辆调度问题
10.5 习题
参考文献

上海交大2007年微机原理(27完结)

2008-08-20 11:21:55

上海交大2007年微机原理(27完结),交大精品课程,高清晰,无杂音.

上海交大2007年微机原理(23)

2008-08-20 10:55:05

上海交大2007年微机原理(23)

上海交大2007年微机原理(26)

2008-08-19 13:48:00

上海交大2007年微机原理(26),共27集,每集60分钟-120分钟.

上海交大2007年微机原理(25)

2008-08-19 13:31:06

上海交大2007年微机原理(25)

上海交大2007年微机原理(24)

2008-08-19 13:22:10

上海交大2007年微机原理(24)

上海交大2007年微机原理(22)

2008-08-19 13:06:39

上海交大2007年微机原理(22)

上海交大2007年微机原理(21)

2008-08-19 09:36:49

上海交大2007年微机原理(21)

上海交大2007年微机原理(20)

2008-08-19 09:18:30

上海交大2007年微机原理(20)

上海交大2007年微机原理(19)

2008-08-18 20:01:49

上海交大2007年微机原理(19)

上海交大2007年微机原理(18)

2008-08-18 19:45:38

上海交大2007年微机原理(18)

上海交大2007年微机原理(17)

2008-08-18 16:56:47

上海交大2007年微机原理(17)

上海交大2007年微机原理(16)

2008-08-18 16:35:25

上海交大2007年微机原理(15)

2008-08-18 16:18:23

上海交大2007年微机原理(15)

上海交大2007年微机原理(14)

2008-08-18 16:05:25

上海交大2007年微机原理(14),交大精品课程.

上海交大2007年微机原理(13)

2008-08-18 15:53:37

上海交大2007年微机原理(13)，精品课程。

上海交大2007年微机原理(12)

2008-08-18 15:41:49

上海交大2007年微机原理(12)

上海交大2007年微机原理(11)

2008-08-15 00:03:25

上海交大2007年微机原理(11),上传的文件为rar格式.

上海交大2007年微机原理(10)

2008-08-14 23:52:02

上海交大2007年微机原理(10),上传的资料为rar格式,解压后40多Mb.

上海交大2007年微机原理(9)

2008-08-14 23:42:33

上海交大2007年微机原理(9)

上海交大2007年微机原理(8)

2008-08-14 09:44:27

交大精品课程,超清晰.

上海交大微机原理(7)

2008-08-13 21:47:34

微机原理一直被全国高校，包括清华北大，认为是很有难度的计算机专业课程，上海交大的王春香老师却不这么认为，她带的班级，也就是2006界计算机系,在她诙谐幽默而不失专业性的讲解下，全班期末成绩全过80，班级平均成绩过90！王春香老师很早就说，微机原理非常简单，担心同学们稍微认真听课后，都考100分怎么办？也正因为这个教学奇迹，王春香老师的微机原理课程被评为交大精品课程。本套视频课程再现了王春香老师当年教学的点滴风采。老师不仅课讲的精彩幽默，声音也很悦耳。

Wavelets in Medical Image Processing Denoising,Segmentation,and Registration

2008-08-09 11:15:26

Wavelet transforms and other multi-scale analysis functions have been used for compact signal and image representations in de-noising, compression and feature detection processing problems for about twenty years. Numerous research works have proven that space-frequency and space-scale expansions with this family of analysis functions provided a very efficient framework for signal or image data.
The wavelet transform itself offers great design flexibility. Basis selection, spatial-frequency tiling, and various wavelet threshold strategies can be optimized for best adaptation to a processing application, data characteristics and feature of interest. Fast implementation of wavelet transforms using a filter-bank framework enable real time processing capability. Instead of trying to replace standard image processing techniques, wavelet transforms offer an efficient representation of the signal, finely tuned to its intrinsic properties. By combining such representations with simple processing techniques in the transform domain, multi-scale analysis can accomplish remarkable performance and efficiency for many image processing problems. 1
Multi-scale analysis has been found particularly successful for image de-noising and enhancement problems given that a suitable separation of signal and noise can be achieved in the transform domain (i.e. after projection of an observation signal) based on their distinct localization and distribution in the spatial-frequency domain. With better correlation of significant features, wavelets were also proven to be very useful for detection {jin_Mallat_1992a} and matching applications {jin_Strickland_1995}.
One of the most important features of wavelet transforms is their multi-resolution representation. Physiological analogies have suggested that wavelet transforms are similar to low level visual perception. From texture recognition, segmentation to image registration, such multi-resolution analysis gives the possibility of investigating a particular problem at various spatial-frequency (scales). In many cases, a “coarse to fine” procedure can be implemented to improve the computational efficiency and robustness to data variations and noise.
Without trying to cover all the issues and research aspects of wavelet in medical imaging, we focus our discussion in this chapter to three topics: image de-noising/enhancement, image segmentation and image registration using wavelet transforms. We will introduce the wavelet multi-scale analysis framework and summarize related research work in this area and describe recent state-of-the-art techniques.

数据结构与算法（Java语言版）

2008-08-07 23:47:05

【内容简介】
　　在C语言作为教学语言时期，数据结构几乎都是用C语言来描述其算法。Java语言诞生后，以其功能完备及跨平台等特性，逐渐为计算机领域广大科技工作者所偏爱。因此，用Java语言来描述数据结构及其算法，有着很重要的现实意义。本书顺应了计算机科学发展的需要，以面向对象的方式描述了数据结构的设计和实现范例，在数据结构的实现中用Java作为编程语言。本书的重点是数据结构，算法是从数据结构的角度来考虑的。本书强调了数据结构和算法之间的联系，详尽地描述了不同类型的递归，在每一章都提供了示例学习和编程作业。本书适合作为初学数据结构的学生教材，同时也为高年级学生提供了一些极富吸引力的内容。
【作者简介】
　　Adam Drozdek是Duquesne大学计算机科学教授，原籍波兰，在俄亥俄州Wright州立大学获得硕士学位，并在世界历史最悠久的大学之一波兰克拉科夫的Jagiellonian大学获得了博士学位。
【网友评价】
会员名:ybw_hz 评价等级: ★★★★

我觉得,这本书还是相当不错的,适合相关专业的本科生一读,各种基本的数据结构还有基本的算法基本上都比较全面,对JAVA语言也作了初略的介绍,而且价格也比较便宜了,出版年份也不算太早,其实对于这些基本的数据结构和算法,前人已经作了很多总结了,我觉得还是不错的一本书。
发表于:2007-12-28 最新讨论:2007-12-28

会员名:dfstephen 评价等级: ★★★★★

我有这本书闲置,是买回来没看的,保存完好,超低价出售,旨在清空书架。欢迎光临小店看看,http://shop34722059.taobao.com/

发表于:2007-9-8 最新讨论:2007-9-8

会员名:rui.zhg 评价等级: ★★★★

这本书很不错,这是我在这里买的第一本书
发表于:2006-2-19 最新讨论:2006-2-19

会员名:seabiscuit 评价等级: ★★★★★

不知道翻译的怎么样?那位大哥出来说句话,值不值得买呀?我想买!
发表于:2005-6-2 最新讨论:2005-6-2

会员名:qwetewry 评价等级: ★★★★★

这本书非常不错。原先是我一位在澳大利亚读大学的朋友推荐的,他所在的大学就是用这本书做教材。个人觉的此书最大特点是有许多实例,如果光讲原理会让你觉得苦涩难耐,如果原理和实例相结合,就能让你更好的了解各种数据结构。所以强烈推荐.
发表于:2005-1-3 最新讨论:2005-1-3

会员名:lovemyr 评价等级: ★★★★

这本书我看过了
感觉挺好的
想在编程方面有所建树的话
看看还是有很大好处的
发表于:2004-5-16 最新讨论:2004-5-23

会员名:wangdongzjk 评价等级: ★★★★★

这本书习题没有答案,我给作者写信问过了(可能教师有:)),我还问能不能出一本习题答案的书,他说这是出版社的事情。
发表于:2004-2-22 最新讨论:2004-2-22

会员名:kiwell 评价等级: ★★★★★

答案好象在作者的网站上有
发表于:2004-2-19 最新讨论:2004-2-19

【下载说明】
　　本资料为《数据结构与算法（Java语言版）》一书PDF格式的高清晰电子版，推荐使用Adobe Reader 7.0或兼容阅读工具打开！
【图书目录】
第1章 Java语言的面向对象编程
1.1 Java入门
1.1.1 变量声明
1.1.2 运算符
1.1.3 选择语句
1.1.4 循环语句
1.1.5 异常处理
1.2 Java面向对象编程
1.2.1 封装
1.2.2 抽象数据类型
1.2.3 继承
1.2.4 多态性
1.3 输入和输出
1.4 Java和指针
1.5 java.util中的向量
1.6 数据结构和面向对象编程
1.7 示??学习:随机存取文件
1.8 习题
1.9 编程作业
参考文献
第2章复杂性分析
2.1 计算复杂性和渐近复杂性
2.2 大O表示法
2.3 大O表示法的性质
2.4 和表示法
2.5 可能出现的问题
2.6 复杂性示例
2.7 寻找渐近复杂性:示例
2.8 最好的、平均的和最坏的情况
2.9 补偿复杂性
2.10 习题
参考文献
第3章链表
3.1 单向链表
3.1.1 插入
3.1.2 删除
3.1.3 查找
3.2 双向链表
3.3 循环链表
3.4 跳转表
3.5 自组织表
3.6 稀疏表
3.7 用java.util的链表
3.8 小结
3.9 示例学习:图书馆管理
3.10 习题
3.11 编程作业
参考文献
第4章堆栈和队列
4.1 堆栈
4.2 队列
4.3 优先级队列
4.4 示例学习:逃离迷宫
4.5 习题
4.6 编程作业
参考文献
第5章递归
5.1 递归定义
5.2 方法调用和递归实现
5.3 剖析一个递归调用
5.4 尾递归
5.5 非尾递归
5.6 间接递归
5.7 嵌套递归
5.8 过分递归
5.9 回溯
5.10 小结
5.11 示例学习:一个递归下降解释器
5.12 习题
5.13 编程作业
参考文献
第6章二叉树
6.1 树、二叉树和折半查找树
6.2 实现二叉树
6.3 搜索折半查找树
6.4 树的遍历
6.4.1 广度优先遍历
6.4.2 深度优先遍历
6.4.3 无堆栈深度优先遍历
6.5 插入
6.6 删除
6.6.1 归并删除法
6.6.2 拷贝删除法
6.7 树的平衡,
6.7.1 DSW算法
6.7.2 AVL树
6.8 自适应树
6.8.1 自调整树
6.8.2 扩展
6.9 堆
6.9.1 堆作为优先级队列
6.9.2 以堆形式组织数组
6.10 波兰表示法和表示树
6.11 示例学习:计算单词频率
6.12 习题
6.13 编程作业
参考文献
第7章多分树
7.1 B树家族
7.1.1 B树
7.1.2 B*树
7.1.3 B树
7.1.4 前缀B树
7.1.5 比特树
7.1.6 R树
7.1.7 2-4树
7.1.8 java.util中的集合
7.1.9 java.util中的映像
7.2 线索
7.3 小结
7.4 示例学习:拼写检查程序
7.5 习题
7.6 编程作业
参考文献
第8章图
8.1 图的表示法
8.2 图的遍历
8.3 最短路径
8.4 环路检测
8.5 生成树
8.5.1 Boruvka算法
8.5.2 Kruskal算法
8.5.3 Jarnik-Prim算法
8.5.4 Dijkstra算法
8.6 连通性
8.6.1 无向图的连通性
8.6.2 有向图的连通性
8.7 拓扑排序
8.8 网络
8.8.1 最大流
8.8.2 最小代价的最大流量
8.9 匹配
8.9.1 分配问题
8.9.2 非二部图中的匹配
8.10 欧拉图和哈密顿图
8.10.1 欧拉图
8.10.2 哈密顿图
8.11 示例学习:典型代表问题
8.12 习题
8.13 编程作业
参考文献
第9章排序
9.1 元素排序算法
9.1.1 插入排序
9.1.2 选择排序
9.1.3 起泡排序
9.2 决策树
9.3 高效排序算法
9.3.1 希尔排序
9.3.2 堆排序
9.3.3 快速排序
9.3.4 归并排序
9.3.5 基数排序
9.4 java.util中的排序
9.5 小结
9.6 示例学习:多项式加法
9.7 习题
9.8 编程作业
参考文献
第10章散列
10.1 散列函数
10.1.1 除法
10.1.2 折叠法
10.1.3 平方取中散列函数
10.1.4 提取方法
10.1.5 基数变换
10.2 冲突解决
10.2.1开放地址法
10.2.2 链
10.2.3 桶地址法
10.3 删除
10.4 理想散列函数
10.4.1 Cichelli方法
10.4.2 FHCD算法,
10.5 可扩展文件的散列函数
10.5.1 可扩展散列
10.5.2 线性散列
10.6 java.util中的散列
10.7 示例学习
10.8 习题
10.9 编程作业
参考文献
第11章数据压缩
11.1 数据压缩的条件
11.2 霍夫曼编码
11.3 Shannon-Fano码
11.4 运行长度编码
11.5 Ziv-Lempel编码
11.6 示例学习:结合运行长度编码的霍夫曼方法
11.7 习题
11.8 编程作业
参考文献
第12章存储管理
12.1 连续适应方法
12.2 非连续适应方法
12.3 无用单元收集
12.3.1 标记与清除算法
12.3.2 拷贝方法
12.3.3 增量式无用单元收集
12.4 小结
12.5 示例学习:内置无用单元收集器
12.6 习题
12.7 编程作业
参考文献
附录A 大O的计算
人名索引
名词索引

计算机系统设计与结构（第2版）

2008-08-06 20:49:29

【内容简介】
　　本书从系统结构设计师、汇编程序员和逻辑设计师的角度介绍了计算机系统结构的设计。全书从计算机系统结构设计的综述入手，讲解了机器和机器语言之间的关系，引入了有代表性且容易理解的SRC模型和RTN结构功能描述语言，并讨论了相关的逻辑设计问题；接下来作者用实例说明了CISC和RISC的区别，深入剖析了指令集和硬件之间的接口关系，介绍了CPU流水线、多指令发射计算机、微代码控制单元的设计以及算术逻辑处理单元的设计；之后作者详细介绍了存储器的层次化结构设计，并且讨论了机器输入输出系统和外围设备；最后作者讨论了一些计算机网络互连方面的论题。
　　本书可作为高校计算机、电子等相关专业本科生和研究生微机原理、系统结构和计算机设计等方面谭程的教材，对相关专业人士和研发人员也很有裨益。
【作者简介】
　　Vincent P.Heuring，美国科罗拉多大学博尔德分校电子和计算机工程系教授，研究方向包括计算机系统结构和编程语言的设计与实现，主要关注计算机硬件和软件的关系。
　　Heuring教授是Eli编译器构建系统的主要设计者之一，他还和Jordan教授合作设计了世界上第一台光学存储程序计算机。
【下载说明】
　　本资料为《计算机系统设计与结构（第2版）》一书PDF格式的清晰电子版，推荐使用Adobe Reader 7.0或兼容阅读工具打开！
【图书目录】
第1章通用计算机
1.1 通用计算机
1.2 用户眼中的计算机
1.3 机器语言与汇编语言程序员眼中的计算机
1.4 计算机架构师眼中的计算机
1.5 逻辑设计师眼中的计算机
1.6 历史回顾
1.7 研究现状与发展趋势
1.8 本书的讲解方式
小结
参考文献
习题
第2章机器，机器语言和数字逻辑
2.1 计算机及机器指令的分类
2.2 计算机指令集
2.3 简化RISC计算机的非形式化描述
2.4 使用寄存器转移标记语言对SRC机进行形式描述
2.5 使用RTN语言对寻址模式进行描述
2.6 寄存器转移与逻辑电路：从行为到硬件
小结
参考文献
习题
第3章几种真实机器
3.1 计算机功能与性能
3.2 精简指令集计算机与复杂指令集计算机的比较
3.3 CISC处理器：摩托罗拉MC68000
3.4 一种RISC计算机体系结构：SPARC机
小结
参考文献
习题
第4章处理器设计
4.1 处理器设计过程
4.2 1总线SRC计算机的微观结构
4.3 数据通道实现
4.4 2总线SRC机的逻辑设计
4.5 计算机控制单元
4.6 2总线和3总线处理器设计
4.7 机器复位
4.8 机器异常
小结
参考文献
习题
第5 章处理器设计高级议题
5.1 流水线结构
5.2 流水线冲突
5.3 指令级并行
5.4 微编码
小结
参考文献
习题
第6章计算机算法与算术单元
6.1 数字系统与基数转换
6.2 定点算术
6.3 算术单元ALU设计的半数值情形
6.4 浮点算术
小结
参考文献
习题
第7章内存系统设计
7.1 导言：内存系统的组成单元
7.2 RAM结构：逻辑设计师的视角
7.3 内存电路板和模块
7.4 双层内存架构
7.5 Cache
7.6 虚拟内存
7.7 计算机的存储子系统
小结
参考文献
习题
第8章输入和输出
8.1 I/O子系统
8.2 可编程I/O
8.3 I/O中断
8.4 直接内存访问
8.5 I/O数据格式转换和错误控制
小结
参考文献
习题
第9章外部设备
9.1 磁盘驱动器
9.2 改善磁盘系统的性能和可靠性
9.3 其他海量存储设备
9.4 视频显示设备
9.5 打印机
9.6 输入设备
9.7 与模拟世界之间的接口
小结
参考文献
习题
第10章通信，网络和Internet
10.1 计算机与计算机之间的数据通信
10.2 串行数据通信协议
10.3 局域网
10.4 现代串行总线：USB和火线
10.5 Internet
小结
参考文献
习题
附录A SRC机的RTN描述
附录B 汇编与汇编器
附录C 部分习题及解答
附录D 简单RISC计算机
附录E SRC汇编语言约
索引

数据结构（C++版）

2008-08-05 22:07:19

内容简介
　　本书全面阐述了数据结构方面的基本理论，主要内容包括线性表、栈、队列、串、数组、广义表、树、二叉树、图等基本的数据结构以及查找和排序算法。
　　本书用C++语言定义和实现数据结构及算法。全书结构清楚，内容丰富，章节安排合理。叙述深入浅出，循序渐进。示例典型实用，算法严谨规范，算法和程序全部调试通过。
　　本书适合作为计算机及相关专业本、专科学生教材，也可作为从事计算机软件开发和工程应用人员的参考书。
目录
第1章绪论
1.1数据结构的基本概念
1.1.1抽象数据类型与数据结构
1.1.2数据的逻辑结构
1.1.3数据的存储结构
1.1.4数据的操作
1.2算法与算法设计
1.2.1算法
1.2.2算法设计
1.2.3算法分析
习题1
实习1
第2章线性表
2.1线性表的概念
2.1.1线性表的抽象数据类型
2.1.2线性表的存储结构
2.2顺序表类
2.2.1顺序表类声明
2.2.2顺序表类操作
2.2.3顺序表类操作的效率分析
2.3单链表类
2.3.1单链表的概念
2.3.2单链表的节点类
2.3.3单链表类的设计与实现
2.3.4两种存储结构性能的比较
2.3.5单向循环链表类
2.4向链表类
2.4.1向链表的概念
2.4.2向链表的节点类
2.4.3向链表类的设计与实现
2.4.4向循环链表的概念
习题2
实习2
第3章排序
3.1排序的基本概念
3.2插入排序
3.2.1顺序表的直接插入排序
3.2.2单链表的直接插入排序
3.2.3希尔排序
3.3交换排序
3.3.1冒泡排序
3.3.2改进的冒泡排序
3.3.3快速排序
3.4选择排序
3.4.1顺序表的直接选择排序
3.4.2单链表的直接选择排序
3.5归并排序
3.5.1顺序表的归并排序
3.5.2单链表的归并排序
习题3
实习3
第4章串
4.1串的基本概念
4.1.1串的定义
4.1.2串的抽象数据类型
4.1.3串的存储结构
4.2顺序串类
4.2.1顺序串类声明
4.2.2顺序串类的基本操作
4.2.3顺序串类的运算符重载
4.2.4对子串的操作
4.3串的模式匹配算法
4.3.1Brute-Force算法
4.3.2替换子串操作
习题4
实习4
第5章栈和队列
5.1栈
5.1.1栈的定义
5.1.2栈的抽象数据类型
5.1.3顺序栈类
5.1.4链式栈类
5.1.5栈的应用
5.2队列
5.2.1队列的定义
5.2.2队列的抽象数据类型
5.2.3队列的存储结构
5.2.4顺序循环队列类
5.2.5链式队列类
5.2.6队列的应用
5.3递归
习题5
实习5
第6章数组和广义表
6.1数组
6.1.1一维数组
6.1.2多维数组
6.2矩阵类
6.2.1矩阵类的声明
6.2.2矩阵类的操作
6.3特殊矩阵的压缩存储
6.4稀疏矩阵
6.4.1稀疏矩阵的三元组线性表
6.4.2三元组顺序表类
6.4.3三元组链表
6.5广义表·
6.5.1广义表的概念
6.5.2广义表的存储结构
习题6
实习6
第7章初树和二叉树
7.1树
7.1.1树的定义
7.1.2树的术语
7.1.3树的表示方法
7.2叉树
7.2.1叉树的定义
7.2.2二叉树的性质.
7.2.3叉树的抽象数据类型
7.2.4二叉树的遍历
7.2.5叉树的存储结构
7.2.6树与二叉树的转换
7.3二叉树类
7.3.1叉树的节点类
7.3.2二叉树类的设计与实现
7.3.3建立二叉树的算法设计
7.3.4二叉树遍历的非递归算法
7.3.5二叉树的层次遍历
7.4线索二叉树
7.4.1线索二叉树的定义
7.4.2线索二叉树的节点类
7.4.3中序线索二叉树类
7.5堆排序
习题7
实习7
第8章查找
8.1查找的基本概念
8.2线性表的查找
8.2.111匝序查找
8.2,2折半查找
8.2.3分块查找
8.3二叉排序树及其查找算法
8.4哈希查找
8.4.1哈希表的基本概念
8.4.2设计哈希函数
8.4.3解决冲突的方法
8.4.4拉链法的哈希表类
习题8
实习8
第9章图
9.1图的基本知识
9.1.1图的定义
9.1.2节点的度
9.1.3子图
9.1.4路径、回路及连通性
9.1.5图的抽像数据类型
9.2图的存储结构
9.2.1邻接矩阵
9.2.2邻接表
9.3图的遍历
9.3.1深度优先遍历
9.3.2广度优先遍历
9.4邻接矩阵图类
9.5最小生成树
9.5.1树与图
9。5.2生成树
9.5.3最小生成树及其构造算法
9.6最短路径
习题9
实习9
第10章综合应用设计
10.1用“预见算法”解骑士游历问题
10.2综合应用实习
参考文献

注册表实用手册v5.2

2008-08-04 03:43:25

使用说明

本手册全称“注册表实用手册”，收录的是大量简单,通俗易懂而又确实实用的windows系列注册表修改技巧。经实践证明，不但对电脑初学者有很大的帮助，对"大哥级"的电脑爱好者也有很高的参考价值。毫不夸大的说，这是一本非常实用的windows系列注册表工具书，确实是您学习和维护电脑的好帮手。

试用版提供【注册表修改】部分功能试用，有(R)标记的为注册版本目录，包括win98，NT，2K，XP，2003全套注册表修改和优化技巧。本手册目前在一定程度上来说已经相当完善，各项修改都很全面。本手册会结合实际，追踪注册表最新动态，努力提供最好最全的注册表实用技术。

版权信息：本手册分注册版和试用版两种。试用版免费，你可以免费使用，自由传播，但请保留其版权；注册版本只提供给本手册注册用户使用。

更新信息：5.2版本改原来的"电脑应用技术"版块为"windows应用技巧"，主要提供各种实用的windows应用技术，涉及各种常见的电脑问题，力求能较好的解决疑难问题。

注册问题：为什么要注册？本手册是共享教学软件，您的付费注册是对作者的支持，将鼓励作者做出更多更好的电子图书，为您提供更好的服务，注册购买本手册后，也即成为本站（www.happydrips.com）的永久注册用户，可以继续免费获得本站制作的各种计算机电子图书和技术资料。

本人力求手册完美，但因有些内容涉及系统内核，所以对使用本手册可能造成的损失由使用者承担，本人不保证所有内容都准确无误。因手册内容太多，如果您在使用本手册过程中发现什么问题或错误请来信指正，欢迎交流！

华罗庚：下棋找高手

2008-07-31 15:30:25

成为一个数学家会有多难？成为一个卓有成就的数学家又会有多难？华罗庚靠自学成为了著名数学家，他说起当年读书时的境遇之难，那简直是他人生之劫。《华罗庚：下棋找高手》选编了华罗庚先生这位中国乃至世界的数学天才的随笔，从中折射出他的治学思想和精神风貌。

实现梦想
日记篇
自昆明到德黑兰
哪天亦能有我们国家传大的科学院
十位无生，神交已久
尊重科学和艺术的国度
遇害的大科学家们
感叹中外学术交流的比较
在莫斯科的社交圈中
受过教学训练的大脑，何愁没有出路
小天使们成长的文化与数学环境
乔其亚之旅
感受阿塞拜疆的文化与活力
一个制度是否有缺点，全在于公众的检举
遥听着祖国的内战的炮声，如针刺心
数学为科学之母
方法篇
数学与应用
学与识
取法乎上，公得乎中
科学是老老实实的学问
数学的用场和发展
培养学术空气，展开学术争论
讲话篇
关于统筹法的讲法
谈谈中学教学教材问题
希望我国科学新生力量很快成长
学习和研究数学的体会
体会篇
打好基础，循序渐进
独立研究，努力成“家”
写在一九五六年教学竞赛结束之后
一种科学方法的选择
在困境中要发愤求进
我从事科学研究工作的体会
理论、应用与工作的体会
时乎时首不再来
和青年谈学习
和同学们谈教学
从小钻透科技关
学·思·锲而不舍
对青年的希望
知识分子的光辉榜样
青怎样胜于蓝
聪明在于学习，天才由于积累
……
共勉篇
希望篇

Advances in Nonlinear Signal and Image Processing (超清晰版)

2008-07-28 15:53:28

1. Nonstationary stochastic differential equations,
Lorenzo Galleani and Leon Cohen 1
1.1. Introduction 1
1.2. Time-dependent power spectrum 2
1.3. The equation of motion for a nonstationary stochastic system 3
1.4. The nonstationaryWiener process 5
1.5. The Langevin equation: the full exact solution 7
1.6. Quantum Langevin equation 9
1.7. Time-variant random systems 10
1.8. Summary 13
Bibliography 13
2. Aperture filters: theory, application, and multiresolution analysis,
Roberto Hirata Jr., Marcel Brun, Junior Barrera,
and Edward R. Dougherty 15
2.1. Introduction 15
2.2. Window operators 17
2.3. Aperture operators 18
2.4. Envelope aperture 25
2.5. Multiresolution aperture 33
2.6. Summary 41
Bibliography 45
3. Finite-set signal processing, Ronald K. Pearson and Moncef Gabbouj 49
3.1. Introduction 49
3.2. Fundamental notions 51
3.3. Characterization on finite sets 56
3.4. Filters on finite sets 68
3.5. Variations and extensions 73
3.6. Summary 74
Bibliography 75
4. Nonlinear signal modeling and structure selection with applications
to genomics, Ioan Tabus, Jorma Rissanen, and Jaakko Astola 79
4.1. Introduction 79
4.2. Preliminaries: modeling and predicting gene expressions 80
4.3. Several classes of nonlinear functions and associated
design methods 83
4.4. Normalized maximum likelihood models for a class of
Boolean regressor models 92
4.5. Summary 100
Bibliography 100
5. Nonlinear methods for speech analysis and synthesis,
Steve McLaughlin and Petros Maragos 103
5.1. Introduction 103
5.2. What nonlinear methods might we use? 108
5.3. Summary 136
Bibliography 136
6. Communication system nonlinearities: challenges and some
solutions, G. Tong Zhou, Hua Qian, and Ning Chen 141
6.1. Introduction 141
6.2. Nonlinear communication system concepts 142
6.3. Nonlinear distortions 150
6.4. Digital baseband predistortion linearization 156
6.5. Summary 164
Bibliography 165
7. Nonlinear multichannel active noise control,
Giovanni L. Sicuranza and Alberto Carini 169
7.1. Introduction 169
7.2. The active noise control scenario 171
7.3. Nonlinear active noise controllers 184
7.4. A class of nonlinear feedforward active noise controllers 187
7.5. Simulation results 195
7.6. Current work and future developments 198
7.7. Summary 200
Bibliography 200
8. Chaotic sequences for digital watermarking,
Nikos Nikolaidis, Anastasios Tefas, and Ioannis Pitas 205
8.1. Introduction 205
8.2. Correlation-based watermarking schemes employing
Markov chaotic sequences 207
8.3. Watermark generation by chaotic mixing 229
8.4. Other applications of chaotic systems in digital watermarking 235
8.5. Summary 235
Bibliography 236
9. Modeling of evolving textures using granulometries,
A. J. Gray, S. Marshall, and J. McKenzie 239
9.1. Introduction 239
9.2. Textures and texture analysis 239
9.3. Granulometries 245
9.4. Parallel evolution functions 249
9.5. Application to corrosion images 252
9.6. Modeling the texture 254
9.7. Summary 263
Bibliography 266
10. Multichannel weighted medians, Yinbo Li and Gonzalo R. Arce 273
10.1. Introduction 273
10.2. Multichannel weighted median filtering structures 275
10.3. Filter optimization 279
10.4. Complex multichannelWMs and their optimization 285
10.5. Simulations 290
10.6. Summary 297
Bibliography 298
11. Color image processing: problems, progress, and perspectives,
E. R. Davies and D. Charles 301
11.1. Introduction 301
11.2. The color problem 303
11.3. Linear versus nonlinear processing 303
11.4. Color filtering 305
11.5. Color bleeding 306
11.6. The mode filter 310
11.7. Modern “switched” noise suppression filters 313
11.8. Filters with adjustable parameters 315
11.9. Distortions produced by median and other filters 316
11.10. Review of other color work 322
11.11. Summary 325
Bibliography 326
12. Nonlinear edge detection in color images, Adrian N. Evans 329
12.1. Introduction 329
12.2. Color edge detection 330
12.3. Color spaces and distance measures 331
12.4. Color edge detectors based on vector differences 333
12.5. Vector order statistics color edge detectors 337
12.6. Color morphological gradient operators 340
12.7. Results and evaluation 343
12.8. Summary 351
Bibliography 353
Index 357

电脑维护视频教程(非常实用的课程)

2008-07-24 12:42:30

简介：曙光与咖啡豆一个扮演老师，一个扮演学生，交互式互动学习电脑维护的方方面面。
视频目录：
第一章：电脑硬件介绍
第一课：电脑的硬件组成
第二课：CPU
1、 CPU的性能指标
2、 CPU的接口类型及选购原则
3、主流CPU的推荐
第三课：主板
1、主板的元件组成
2、主板的芯片组及主板选购要点
3、主流主板的推荐
第四课：硬盘
1、硬盘介绍及选购要点
2、主流硬盘推荐
第五课：内存
1、内存介绍及选购要点
2、主流内存的推荐
第六课：光驱
1、光驱的介绍及选购要点
2、主流光驱的推荐
第七课：显卡
1、显卡的介绍及选购
2、主流显卡的推荐
第八课：显示器
1、 CRT与LCD显示器的介绍及选购要点
2、主流CRT与LCD显示器的推荐
第九课：声卡与网卡
1、声卡与网卡的功能及分类
第十课：键盘和鼠标
1、键盘和鼠标的分类及选购要点
第十一课：机箱和电源
1、机箱和电源的介绍及选购要点
第二章：电脑组装过程
第十二课：电脑组装前的准备
第十三课：组装流程
1、电脑硬件设备的组装
2、连接机箱内部连线
3、电脑外部设备的连接
第三章：系统软件的安装
第十四课：轻松设置BIOS
第十五课：计算机软件介绍
第十六课：Windows XP操作系统的安装
第十七课：硬件驱动程序与常用软件的安装
1、硬件驱动程序的安装
2、常用软件的安装
第十八课：电脑上网的安装与设置
1、电脑上网的安装
2、网络连接的建立
第四章：WINXP的基本应用
第十九课： Windows-XP桌面的认识及设置
第二十课：窗口的组成及操作
第二十一课：在Windows XP中输入汉字
第二十二课：Windows-XP资源的管理
第二十三课：Windows-XP中软件的管理
第二十四课：Windows-XP附件程序应用
第二十五课：听音乐、看影片、玩游戏
第二十六课：网上冲浪
1、搜索和下载网络信息
2、申请邮箱与收发邮件
第五章：电脑的维护与故障排除
第二十七课：电脑硬件的日常维护
第二十八课：系统故障诊断
第二十九课：操作系统日常维护与故障排除
第三十课：计算机病毒防范

Computational Geometry：Algorithms and Applications Third Edition

2008-07-18 18:12:57

Contents
1 Computational Geometry 1
Introduction
1.1 An Example: Convex Hulls 2
1.2 Degeneracies and Robustness 8
1.3 Application Domains 10
1.4 Notes and Comments 13
1.5 Exercises 15
2 Line Segment Intersection 19
Thematic Map Overlay
2.1 Line Segment Intersection 20
2.2 The Doubly-Connected Edge List 29
2.3 Computing the Overlay of Two Subdivisions 33
2.4 Boolean Operations 39
2.5 Notes and Comments 40
2.6 Exercises 41
3 Polygon Triangulation 45
Guarding an Art Gallery
3.1 Guarding and Triangulations 46
3.2 Partitioning a Polygon into Monotone Pieces 49
3.3 Triangulating a Monotone Polygon 55
3.4 Notes and Comments 59
3.5 Exercises 60
4 Linear Programming 63
Manufacturing with Molds
4.1 The Geometry of Casting 64
4.2 Half-Plane Intersection 66
4.3 Incremental Linear Programming 71
4.4 Randomized Linear Programming 76 ix
CONTENTS 4.5 Unbounded Linear Programs 79
4.6* Linear Programming in Higher Dimensions 82
4.7* Smallest Enclosing Discs 86
4.8 Notes and Comments 89
4.9 Exercises 91
5 Orthogonal Range Searching 95
Querying a Database
5.1 1-Dimensional Range Searching 96
5.2 Kd-Trees 99
5.3 Range Trees 105
5.4 Higher-Dimensional Range Trees 109
5.5 General Sets of Points 110
5.6* Fractional Cascading 111
5.7 Notes and Comments 115
5.8 Exercises 117
6 Point Location 121
Knowing Where You Are
6.1 Point Location and Trapezoidal Maps 122
6.2 A Randomized Incremental Algorithm 128
6.3 Dealing with Degenerate Cases 137
6.4* A Tail Estimate 140
6.5 Notes and Comments 143
6.6 Exercises 144
7 Voronoi Diagrams 147
The Post Office Problem
7.1 Definition and Basic Properties 148
7.2 Computing the Voronoi Diagram 151
7.3 Voronoi Diagrams of Line Segments 160
7.4 Farthest-Point Voronoi Diagrams 163
7.5 Notes and Comments 167
7.6 Exercises 170
8 Arrangements and Duality 173
Supersampling in Ray Tracing
8.1 Computing the Discrepancy 175
8.2 Duality 177
8.3 Arrangements of Lines 179
x 8.4 Levels and Discrepancy 185
8.5 Notes and Comments 186 CONTENTS
8.6 Exercises 188
9 Delaunay Triangulations 191
Height Interpolation
9.1 Triangulations of Planar Point Sets 193
9.2 The Delaunay Triangulation 196
9.3 Computing the Delaunay Triangulation 199
9.4 The Analysis 205
9.5* A Framework for Randomized Algorithms 208
9.6 Notes and Comments 214
9.7 Exercises 215
10 More Geometric Data Structures 219
Windowing
10.1 Interval Trees 220
10.2 Priority Search Trees 226
10.3 Segment Trees 231
10.4 Notes and Comments 237
10.5 Exercises 239
11 Convex Hulls 243
Mixing Things
11.1 The Complexity of Convex Hulls in 3-Space 244
11.2 Computing Convex Hulls in 3-Space 246
11.3* The Analysis 250
11.4* Convex Hulls and Half-Space Intersection 253
11.5* Voronoi Diagrams Revisited 254
11.6 Notes and Comments 256
11.7 Exercises 257
12 Binary Space Partitions 259
The Painter’s Algorithm
12.1 The Definition of BSP Trees 261
12.2 BSP Trees and the Painter’s Algorithm 263
12.3 Constructing a BSP Tree 264
12.4* The Size of BSP Trees in 3-Space 268
12.5 BSP Trees for Low-Density Scenes 271
12.6 Notes and Comments 278
12.7 Exercises 279 xi
CONTENTS 13 Robot Motion Planning 283
Getting Where You Want to Be
13.1 Work Space and Configuration Space 284
13.2 A Point Robot 286
13.3 Minkowski Sums 290
13.4 Translational Motion Planning 297
13.5* Motion Planning with Rotations 299
13.6 Notes and Comments 303
13.7 Exercises 305
14 Quadtrees 307
Non-Uniform Mesh Generation
14.1 Uniform and Non-Uniform Meshes 308
14.2 Quadtrees for Point Sets 309
14.3 From Quadtrees to Meshes 315
14.4 Notes and Comments 318
14.5 Exercises 320
15 Visibility Graphs 323
Finding the Shortest Route
15.1 Shortest Paths for a Point Robot 324
15.2 Computing the Visibility Graph 326
15.3 Shortest Paths for a Translating Polygonal Robot 330
15.4 Notes and Comments 331
15.5 Exercises 332
16 Simplex Range Searching 335
Windowing Revisited
16.1 Partition Trees 336
16.2 Multi-Level Partition Trees 343
16.3 Cutting Trees 346
16.4 Notes and Comments 352
16.5 Exercises 353
Bibliography 357
Index 377

Encyclopedia of Algorithms

2008-07-03 14:46:36

Table of Contents
AbelianHiddenSubgroupProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1995; Kitaev
AdaptivePartitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1986; Du, Pan, Shing
AdwordsPricing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2007; Bu, Deng, Qi
AlgorithmDC-Tree for kServersonTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1991; Chrobak, Larmore
AlgorithmicCooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1999; Schulman, Vazirani
2002; Boykin, Mor, Roychowdhury, Vatan, Vrijen
AlgorithmicMechanismDesign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1999; Nisan, Ronen
AlgorithmsforSpannersinWeightedGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2003; Baswana, Sen
AllPairsShortestPathsinSparseGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2004; Pettie
AllPairsShortestPathsviaMatrixMultiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2002; Zwick
AlternativePerformanceMeasuresinOnlineAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2000; Koutsoupias, Papadimitriou
AnalyzingCacheMisses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2003;Mehlhorn, Sanders
ApplicationsofGeometricSpannerNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2002; Gudmundsson, Levcopoulos, Narasimhan, Smid
ApproximateDictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2002; Buhrman, Miltersen, Radhakrishnan, Venkatesh
ApproximateRegularExpressionMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1995; Wu, Manber, Myers
VIII Table of Contents
ApproximateTandemRepeats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2001; Landau, Schmidt, Sokol
2003; Kolpakov, Kucherov
ApproximatingMetricSpacesbyTreeMetrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
1996; Bartal, Fakcharoenphol, Rao, Talwar
2004; Bartal, Fakcharoenphol, Rao, Talwar
ApproximationsofBimatrixNashEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2003; Lipton, Markakis,Mehta
2006; Daskalaskis,Mehta, Papadimitriou
2006; Kontogiannis, Panagopoulou, Spirakis
ApproximationSchemesforBinPacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1982; Karmarker, Karp
ApproximationSchemesforPlanarGraphProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1983; Baker
1994; Baker
ArbitrageinFrictionalForeignExchangeMarket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2003; Cai, Deng
ArithmeticCodingforDataCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1994; Howard, Vitter
AssignmentProblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1955; Kuhn
1957;Munkres
AsynchronousConsensusImpossibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1985; Fischer, Lynch, Paterson
AtomicBroadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
1995; Cristian, Aghili, Strong, Dolev
Attribute-EfficientLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
1987; Littlestone
AutomatedSearchTreeGeneration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2004; Gramm, Guo, Hüffner, Niedermeier
Backtracking Based k-SATAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2005; Paturi, Pudlák, Saks, Zane
BestResponseAlgorithmsforSelfishRouting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
2005; Fotakis, Kontogiannis, Spirakis
Bidimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2004; Demaine, Fomin, Hajiaghayi, Thilikos
BinaryDecisionGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
1986; Bryant
Table of Contents IX
BinPacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
1997; Coffman, Garay, Johnson
BoostingTextualCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
2005; Ferragina, Giancarlo,Manzini, Sciortino
BranchwidthofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
2003; Fomin, Thilikos
BroadcastinginGeometricRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2001; Dessmark, Pelc
B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
1972; Bayer,McCreight
Burrows–WheelerTransform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
1994; Burrows,Wheeler
ByzantineAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
1980; Pease, Shostak, Lamport
Cache-ObliviousB-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2005; Bender, Demaine, Farach-Colton
Cache-ObliviousModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
1999; Frigo, Leiserson, Prokop, Ramachandran
Cache-ObliviousSorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
1999; Frigo, Leiserson, Prokop, Ramachandran
CausalOrder,LogicalClocks,StateMachineReplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
1978; Lamport
CertificateComplexityandExactLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
1995; Hellerstein, Pilliapakkamnatt, Raghavan,Wilkins
ChannelAssignmentandRoutinginMulti-RadioWirelessMeshNetworks . . . . . . . . . . . . . . . . . . . 134
2005; Alicherry, Bhatia, Li
CircuitPartitioning:ANetwork-Flow-BasedBalancedMin-CutApproach . . . . . . . . . . . . . . . . . . . . 138
1994; Yang,Wong
CircuitPlacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
2000; Caldwell, Kahng, Markov
2002; Kennings,Markov
2006; Kennings, Vorwerk
CircuitRetiming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
1991; Leiserson, Saxe
CircuitRetiming:AnIncrementalApproach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
2005; Zhou
X TableofContents
ClockSynchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
1994; Patt-Shamir, Rajsbaum
ClosestStringandSubstringProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
2002; Li, Ma, Wang
ClosestSubstring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
2005;Marx
ColorCoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
1995; Alon, Yuster, Zwick
CommunicationinAdHocMobileNetworksUsingRandomWalks . . . . . . . . . . . . . . . . . . . . . . . . 161
2003; Chatzigiannakis, Nikoletseas, Spirakis
CompetitiveAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
2001; Goldberg, Hartline, Wright
2002; Fiat, Goldberg, Hartline, Karlin
ComplexityofBimatrixNashEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
2006; Chen, Deng
ComplexityofCore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
2001; Fang, Zhu, Cai, Deng
CompressedPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
2003; Kida, Matsumoto, Shibata, Takeda, Shinohara, Arikawa
CompressedSuffixArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
2003; Grossi, Gupta, Vitter
CompressedText Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
2005; Ferragina,Manzini
CompressingIntegerSequencesandSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
2000;Moffat, Stuiver
ComputingPureEquilibriaintheGameofParallelLinks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
2002; Fotakis, Kontogiannis, Koutsoupias, Mavronicolas, Spirakis
2003; Even-Dar, Kesselman,Mansour
2003; Feldman, Gairing, Lücking, Monien, Rode
ConcurrentProgramming,MutualExclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
1965; Dijkstra
ConnectedDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
2003; Cheng, Huang, Li,Wu, Du
ConnectivityandFault-ToleranceinRandomRegularGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
2000; Nikoletseas, Palem, Spirakis, Yung
ConsensuswithPartialSynchrony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
1988; Dwork, Lynch, Stockmeyer
Table of Contents XI
ConstructingaGalledPhylogeneticNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
2006; Jansson, Nguyen, Sung
CPUTimePricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
2005; Deng, Huang, Li
CriticalRangeforWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
2004; Wan, Yi
CryptographicHardnessofLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
1994; Kearns, Valiant
CuckooHashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
2001; Pagh, Rodler
DataMigration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
2004; Khuller, Kim, Wan
DataReductionforDominationinGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
2004; Alber, Fellows, Niedermeier
DecodingReed–SolomonCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
1999; Guruswami, Sudan
DecrementalAll-PairsShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
2004; Demetrescu, Italiano
Degree-BoundedPlanarSpannerwithLowWeight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
2005; Song, Li, Wang
Degree-BoundedTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
1994; Fürer, Raghavachari
DeterministicBroadcastinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
2000; Chrobak, Ga?sieniec, Rytter
DeterministicSearchingontheLine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
1988; Baeza-Yates, Culberson, Rawlins
Dictionary-BasedDataCompression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
1977; Ziv, Lempel
DictionaryMatchingandIndexing(ExactandwithErrors) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
2004; Cole, Gottlieb, Lewenstein
DilationofGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
2005; Ebbers-Baumann, Grüne, Karpinski, Klein, Kutz, Knauer, Lingas
DirectedPerfectPhylogeny(BinaryCharacters) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
1991; Gusfield
DirectRoutingAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
2006; Busch, Magdon-Ismail, Mavronicolas, Spirakis
XII Table of Contents
Distance-BasedPhylogenyReconstruction(Fast-Converging) . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
2003; King, Zhang, Zhou
Distance-BasedPhylogenyReconstruction(OptimalRadius) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
1999; Atteson
2005; Elias, Lagergren
DistributedAlgorithmsforMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
1983; Gallager, Humblet, Spira
DistributedVertexColoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
2004; Finocchi, Panconesi, Silvestri
DynamicTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
2005; Tarjan,Werneck
EditDistanceUnderBlockOperations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
2000; Cormode, Paterson, Sahinalp, Vishkin
2000;Muthukrishnan, Sahinalp
EfficientMethodsforMultipleSequenceAlignmentwithGuaranteedErrorBounds . . . . . . . . . . . . . 267
1993; Gusfield
EngineeringAlgorithmsforComputationalBiology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
2002; Bader, Moret, Warnow
EngineeringAlgorithmsforLargeNetworkApplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
2002; Schulz,Wagner, Zaroliagis
EngineeringGeometricAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
2004; Halperin
EquivalenceBetweenPriorityQueuesandSorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
2002; Thorup
EuclideanTravelingSalespersonProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
1998; Arora
ExactAlgorithmsforDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
2005; Fomin, Grandoni, Kratsch
ExactAlgorithmsforGeneralCNFSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
1998; Hirsch
2003; Schuler
ExactGraphColoringUsingInclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
2006; Bj?rklund, Husfeldt
ExperimentalMethodsforAlgorithmAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
2001;McGeoch
ExternalSortingandPermuting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
1988; Aggarwal, Vitter
Table of Contents XIII
FacilityLocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
1997; Shmoys, Tardos, Aardal
FailureDetectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
1996; Chandra, Toueg
False-Name-ProofAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
2004; Yokoo, Sakurai, Matsubara
FastMinimalTriangulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
2005; Heggernes, Telle, Villanger
Fault-TolerantQuantumComputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
1996; Shor, Aharonov, Ben-Or, Kitaev
FloorplanandPlacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
1994; Kajitani, Nakatake,Murata, Fujiyoshi
FlowTimeMinimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
2001; Becchetti, Leonardi,Marchetti-Spaccamela, Pruhs
FPGATechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
1992; Cong, Ding
FractionalPackingandCoveringProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
1991; Plotkin, Shmoys, Tardos
1995; Plotkin, Shmoys, Tardos
FullyDynamicAllPairsShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
2004; Demetrescu, Italiano
FullyDynamicConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
2001; Holm, de Lichtenberg, Thorup
FullyDynamicConnectivity:UpperandLowerBounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
2000; Thorup
FullyDynamicHigherConnectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
1997; Eppstein, Galil, Italiano, Nissenzweig
FullyDynamicHigherConnectivityforPlanarGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
1998; Eppstein, Galil, Italiano, Spencer
FullyDynamicMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
2000; Holm, de Lichtenberg, Thorup
FullyDynamicPlanarityTesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
1999; Galil, Italiano, Sarnak
FullyDynamicTransitiveClosure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
1999; King
GateSizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
2002; Sundararajan, Sapatnekar, Parhi
XIV Table of Contents
GeneralEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
2002; Deng, Papadimitriou, Safra
GeneralizedSteinerNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
2001; Jain
GeneralizedTwo-ServerProblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
2006; Sitters, Stougie
GeneralizedVickreyAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
1995; Varian
GeographicRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
2003; Kuhn,Wattenhofer, Zollinger
GeometricDilationofGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
2006; Dumitrescu, Ebbers-Baumann, Grüne, Klein, Knauer, Rote
GeometricSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
2002; Gudmundsson, Levcopoulos, Narasimhan
Gomory–HuTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
2007; Bhalgat, Hariharan, Kavitha, Panigrahi
GraphBandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
1998; Feige
2000; Feige
GraphColoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
1994; Karger, Motwani, Sudan
1998; Karger, Motwani, Sudan
GraphConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
1994; Khuller, Vishkin
GraphIsomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
1980;McKay
GreedyApproximationAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
2004; Ruan, Du, Jia, Wu, Li, Ko
GreedySet-CoverAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
1974–1979, Chvátal, Johnson, Lovász, Stein
HamiltonCyclesinRandomIntersectionGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
2005; Efthymiou, Spirakis
HardnessofProperLearning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
1988; Pitt, Valiant
HighPerformanceAlgorithmEngineeringforLarge-scaleProblems . . . . . . . . . . . . . . . . . . . . . . . 387
2005; Bader
Table of Contents XV
Hospitals/ResidentsProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
1962; Gale, Shapley
ImplementationChallengeforShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
2006; Demetrescu, Goldberg, Johnson
ImplementationChallengeforTSPHeuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
2002; Johnson, McGeoch
ImplementingSharedRegistersinAsynchronousMessage-PassingSystems . . . . . . . . . . . . . . . . . . 400
1995; Attiya, Bar-Noy, Dolev
IncentiveCompatibleSelection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
2006; Chen, Deng, Liu
IndependentSetsinRandomIntersectionGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
2004; Nikoletseas, Raptopoulos, Spirakis
IndexedApproximateStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
2006; Chan, Lam, Sung, Tam, Wong
InductiveInference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
1983; Case, Smith
I/O-model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
1988; Aggarwal, Vitter
KineticDataStructures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
1999; Basch, Guibas, Hershberger
Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
1975; Ibarra, Kim
LearningwiththeAidofanOracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
1996; Bshouty, Cleve, Gavaldà, Kannan, Tamon
LearningAutomata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
2000; Beimel, Bergadano, Bshouty, Kushilevitz, Varricchio
LearningConstant-DepthCircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
1993; Linial,Mansour, Nisan
LearningDNFFormulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
1997; Jackson
LearningHeavyFourierCoefficientsofBooleanFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
1989; Goldreich, Levin
LearningwithMaliciousNoise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
1993; Kearns, Li
LearningSignificantFourierCoefficientsoverFiniteAbelianGroups . . . . . . . . . . . . . . . . . . . . . . . 438
2003; Akavia, Goldwasser, Safra
XVI Table of Contents
LEDA:aLibraryofEfficientAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
1995;Mehlhorn, N?her
LeontiefEconomyEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
2005; Codenotti, Saberi, Varadarajan, Ye
2005; Ye
LinearityTesting/TestingHadamardCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
1990; Blum, Luby, Rubinfeld
Linearizability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
1990; Herlihy, Wing
ListDecodingnearCapacity:FoldedRSCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
2006; Guruswami, Rudra
ListScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
1966; Graham
LoadBalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
1994; Azar, Broder, Karlin
1997; Azar, Kalyanasundaram, Plotkin, Pruhs,Waarts
LocalAlignment(withAffineGapWeights) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
1986; Altschul, Erickson
LocalAlignment(withConcaveGapWeights) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
1988;Miller,Myers
LocalApproximationofCoveringandPackingProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
2003–2006; Kuhn, Moscibroda, Nieberg, Wattenhofer
LocalComputationinUnstructuredRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
2005;Moscibroda,Wattenhofer
Local Search Algorithms for kSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
1999; Sch?ning
Local Search for K-mediansandFacilityLocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
2001; Arya, Garg, Khandekar,Meyerson,Munagala, Pandit
LowerBoundsforDynamicConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
2004; P?atra?scu, Demaine
LowStretchSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
2005; Elkin, Emek, Spielman, Teng
LPDecoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
2002 and later; Feldman, Karger, Wainwright
MajorityEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
2003; Chen, Deng, Fang, Tian
Table of Contents XVII
MarketGamesandContentDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
2005;Mirrokni
MaxCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
1994; Goemans, Williamson
1995; Goemans, Williamson
MaximumAgreementSubtree(of2BinaryTrees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
1996; Cole, Hariharan
MaximumAgreementSubtree(of3orMoreTrees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
1995; Farach, Przytycka, Thorup
MaximumAgreementSupertree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
2005; Jansson, Ng, Sadakane, Sung
MaximumCompatibleTree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
2001; Ganapathy, Warnow
Maximum-DensitySegment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
1994; Huang
MaximumMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
2004;Mucha, Sankowski
Maximum-scoringSegmentwithLengthRestrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
2002; Lin, Jiang, Chao
MaximumTwo-Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
2004; Williams
MaxLeafSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
2005; Estivill-Castro, Fellows, Langston, Rosamond
MetricalTaskSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
1992; Borodin, Linial, Saks
MetricTSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
1976; Christofides
MinimumBisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
1999; Feige, Krauthgamer
MinimumCongestionRedundantAssignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
2002; Fotakis, Spirakis
MinimumEnergyBroadcastinginWirelessGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . 526
2005; Ambühl
MinimumEnergyCostBroadcastinginWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
2001; Wan, Calinescu, Li, Frieder
MinimumFlowTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
1997; Leonardi, Raz
XVIII Table of Contents
MinimumGeometricSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
1999; Krznaric, Levcopoulos, Nilsson
Minimumk-ConnectedGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
2000; Czumaj, Lingas
MinimumMakespanonUnrelatedMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
1990; Lenstra, Shmoys, Tardos
MinimumSpanningTrees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
2002; Pettie, Ramachandran
MinimumWeightedCompletionTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
1999; Afrati et al.
MinimumWeightTriangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
1998; Levcopoulos, Krznaric
MobileAgentsandExploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
1952; Shannon
MulticommodityFlow,Well-linkedTerminalsandRoutingProblems . . . . . . . . . . . . . . . . . . . . . . . 551
2005; Chekuri, Khanna, Shepherd
Multicut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
1993; Garg, Vazirani, Yannakakis
1996; Garg, Vazirani, Yannakakis
MultidimensionalCompressedPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
2003; Amir, Landau, Sokol
MultidimensionalStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
1999; K?rkk?inen, Ukkonen
Multi-levelFeedbackQueues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
1968; Coffman, Kleinrock
MultipleUnitAuctionswithBudgetConstraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
2005; Borgs, Chayes, Immorlica, Mahdian, Saberi
2006; Abrams
MultiplexPCRforGapClosing(Whole-genomeAssembly) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
2002; Alon, Beigel, Kasif, Rudich, Sudakov
MultiwayCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
1998; Calinescu, Karloff, Rabani
NashEquilibriaandDominantStrategiesinRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
2005; Wang, Li, Chu
NearestNeighborInterchangeandRelatedDistances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
1999; DasGupta, He, Jiang, Li, Tromp, Zhang
Table of Contents XIX
NegativeCyclesinWeightedDigraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
1994; Kavvadias, Pantziou, Spirakis, Zaroliagis
Non-approximabilityofBimatrixNashEquilibria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
2006; Chen, Deng, Teng
Non-sharedEdges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
1985; Day
Nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581
2006; Deng, Fang, Sun
ObliviousRouting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
2002; R?cke
ObstacleAvoidanceAlgorithmsinWirelessSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
2007; Powell, Nikoletseas
O(log log n)-competitiveBinarySearchTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
2004; Demaine, Harmon, Iacono, Patrascu
OnlineIntervalColoring. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
1981; Kierstead, Trotter
OnlineListUpdate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
1985; Sleator, Tarjan
OnlinePagingandCaching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
1985–2002;multiple authors
OptimalProbabilisticSynchronousByzantineAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
1988; Feldman,Micali
OptimalStableMarriage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606
1987; Irving, Leather, Gusfield
P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
2001; Stoica, Morris, Karger, Kaashoek, Balakrishnan
PacketRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616
1988; Leighton, Maggs, Rao
PacketSwitchinginMulti-QueueSwitches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
2004; Azar, Richter; Albers, Schmidt
PacketSwitchinginSingleBuffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
2003; Bansal, Fleischer, Kimbrel,Mahdian, Schieber, Sviridenko
PACLearning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
1984; Valiant
PageRankAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
1998; Brin, Page
XX Table of Contents
Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625
1985; Sleator, Tarjan, Fiat, Karp, Luby, McGeoch, Sleator, Young
1991; Sleator, Tarjan; Fiat, Karp, Luby, McGeoch, Sleator, Young
ParallelAlgorithmsforTwoProcessorsPrecedenceConstraintScheduling . . . . . . . . . . . . . . . . . . . 627
2003; Jung, Serna, Spirakis
ParallelConnectivityandMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
2001; Chong, Han, Lam
ParameterizedAlgorithmsforDrawingGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
2004; Dujmovic,Whitesides
ParameterizedMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
1993; Baker
ParameterizedSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
2003; Szeider
PeptideDeNovoSequencingwithMS/MS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640
2005;Ma, Zhang, Liang
PerceptronAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
1959; Rosenblatt
PerfectPhylogeny(BoundedNumberofStates) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
1997; Kannan, Warnow
PerfectPhylogenyHaplotyping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
2005; Ding, Filkov, Gusfield
Performance-DrivenClustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
1993; Rajaraman, Wong
PhylogeneticTreeConstructionfromaDistanceMatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
1989; Hein
PlanarGeometricSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
2005; Bose, Smid, Gudmundsson
PlanarityTesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
1976; Booth, Lueker
PointPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
2003; Ukkonen, Lemstr?m, M?kinen
PositionAuction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660
2005; Varian
PredecessorSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
2006; P?atra?scu, Thorup
PriceofAnarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
2005; Koutsoupias
Table of Contents XXI
PriceofAnarchyforMachinesModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
2002; Czumaj, V?cking
ProbabilisticDataForwardinginWirelessSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
2004; Chatzigiannakis, Dimitriou, Nikoletseas, Spirakis
QuantizationofMarkovChains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
2004; Szegedy
QuantumAlgorithmforCheckingMatrixIdentities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
2006; Buhrman, Spalek
QuantumAlgorithmfortheCollisionProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
1998; Brassard, Hoyer, Tapp
QuantumAlgorithmfortheDiscreteLogarithmProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683
1994; Shor
QuantumAlgorithmforElementDistinctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686
2004; Ambainis
QuantumAlgorithmforFactoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
1994; Shor
QuantumAlgorithmforFindingTriangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
2005;Magniez, Santha, Szegedy
QuantumAlgorithmfortheParityProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
1985; Deutsch
QuantumAlgorithmsforClassGroupofaNumberField . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
2005; Hallgren
QuantumAlgorithmforSearchonGrids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696
2005; Ambainis, Kempe, Rivosh
QuantumAlgorithmforSolvingthePell’sEquation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
2002; Hallgren
QuantumApproximation oftheJonesPolynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
2005; Aharonov, Jones, Landau
QuantumDenseCoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
1992; Bennett, Wiesner
QuantumErrorCorrection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
1995; Shor
QuantumKeyDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
1984; Bennett, Brassard
1991; Ekert
QuantumSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
1996; Grover
XXII Table of Contents
Quorums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715
1985; Garcia-Molina, Barbara
RadiocoloringinPlanarGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
2005; Fotakis, Nikoletseas, Papadopoulou, Spirakis
RandomizationinDistributedComputing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
1996; Chandra
RandomizedBroadcastinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
1992; Reuven Bar-Yehuda, Oded Goldreich, Alon Itai
RandomizedEnergyBalanceAlgorithmsinSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728
2005; Leone, Nikoletseas, Rolim
RandomizedGossipinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731
2001; Chrobak, Ga?sieniec, Rytter
RandomizedMinimumSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732
1995; Karger, Klein, Tarjan
RandomizedParallelApproximationstoMaxFlow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734
1991; Serna, Spirakis
RandomizedRounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
1987; Raghavan, Thompson
RandomizedSearchingonRaysor theLine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740
1993; Kao, Reif, Tate
RandomPlanted3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
2003; Flaxman
RankedMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744
2005; Abraham, Irving, Kavitha, Mehlhorn
RankandSelectOperationsonBinaryStrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
1974; Elias
Rate-MonotonicScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 751
1973; Liu, Layland
RectilinearSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
2002; Zhou, Shenoy, Nicholls
RectilinearSteinerTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
2004; Zhou
Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761
1986; Lamport, Vitanyi, Awerbuch
RegularExpressionIndexing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764
2002; Chan, Garofalakis, Rastogi
Table of Contents XXIII
RegularExpressionMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
2004; Navarro, Raffinot
ReinforcementLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771
1992; Watkins
Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774
1990; Attiya, Bar-Noy, Dolev, Peleg, Reischuk
RNASecondaryStructureBoltzmannDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777
2005;Miklós, Meyer, Nagy
RNASecondaryStructurePredictionIncludingPseudoknots . . . . . . . . . . . . . . . . . . . . . . . . . . . . 780
2004; Lyngs?
RNASecondaryStructurePredictionbyMinimumFreeEnergy . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
2006; Ogurtsov, Shabalina, Kondrashov, Roytberg
Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785
1997; (Navigation) Blum, Raghavan, Schieber
1998; (Exploration) Deng, Kameda, Papadimitriou
2001; (Localization) Fleischer, Romanik, Schuierer, Trippen
RobustGeometricComputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788
2004; Li, Yap
Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
2003; Azar, Cohen, Fiat, Kaplan, R?cke
RoutinginGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793
2003; Kuhn,Wattenhofer, Zhang, Zollinger
RoutinginRoadNetworkswithTransitNodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796
2007; Bast, Funke, Sanders, Schultes
R-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800
2004; Arge, de Berg, Haverkort, Yi
SchedulersforOptimisticRateBasedFlowControl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803
2005; Fatourou, Mavronicolas, Spirakis
SchedulingwithEquipartition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806
2000; Edmonds
SelfishUnsplittableFlows:AlgorithmsforPureEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
2005; Fotakis, Kontogiannis, Spirakis
Self-Stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812
1974; Dijkstra
SeparatorsinGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815
1998; Leighton, Rao
1999; Leighton, Rao
XXIV Table of Contents
SequentialApproximateStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818
2003; Crochemore, Landau, Ziv-Ukelson
2004; Fredriksson, Navarro
SequentialCircuitTechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 820
1998; Pan, Liu
SequentialExactStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
1994; Crochemore, Czumaj, Ga?sieniec, Jarominek, Lecroq, Plandowski, Rytter
SequentialMultipleStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826
1999; Crochemore, Czumaj, G?asieniec, Lecroq, Plandowski, Rytter
SetAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829
1993; Chaudhuri
SetCoverwithAlmostConsecutiveOnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832
2004;Mecke, Wagner
ShortestElapsedTimeFirstScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834
2003; Bansal, Pruhs
ShortestPathsApproachesforTimetableInformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837
2004; Pyrga, Schulz,Wagner, Zaroliagis
ShortestPathsinPlanarGraphswithNegativeWeightEdges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838
2001; Fakcharoenphol, Rao
ShortestVectorProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841
1982; Lenstra, Lenstra, Lovasz
SimilaritybetweenCompressedStrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843
2005; Kim, Amir, Landau, Park
Single-SourceFullyDynamicReachability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846
2005; Demetrescu, Italiano
Single-SourceShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
1999; Thorup
SkiRentalProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849
1990; Karlin,Manasse,McGeogh, Owicki
SlicingFloorplanOrientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 852
1983; Stockmeyer
SnapshotsinSharedMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855
1993; Afek, Attiya, Dolev, Gafni, Merritt, Shavit
SortingSignedPermutationsbyReversal(ReversalDistance) . . . . . . . . . . . . . . . . . . . . . . . . . . . 858
2001; Bader, Moret, Yan
SortingSignedPermutationsbyReversal(ReversalSequence) . . . . . . . . . . . . . . . . . . . . . . . . . . . 860
2004; Tannier, Sagot
Table of Contents XXV
SortingbyTranspositionsandReversals(ApproximateRatio1.5) . . . . . . . . . . . . . . . . . . . . . . . . . 863
2004; Hartman, Sharan
SparseGraphSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867
2004; Elkin, Peleg
SparsestCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868
2004; Arora, Rao, Vazirani
SpeedScaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870
1995; Yao, Demers, Shenker
SpherePackingProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871
2001; Chen, Hu, Huang, Li, Xu
SquaresandRepetitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874
1999; Kolpakov, Kucherov
StableMarriage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 877
1962; Gale, Shapley
StableMarriageandDiscreteConvexAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880
2000; Eguchi, Fujishige, Tamura, Fleiner
StableMarriagewithTiesandIncompleteLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 883
2007; Iwama, Miyazaki, Yamauchi
StablePartitionProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885
2002; Cechlárová, Hajduková
StackelbergGames:ThePriceofOptimum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888
2006; Kaporis, Spirakis
StatisticalMultipleAlignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892
2003; Hein, Jensen, Pedersen
StatisticalQueryLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894
1998; Kearns
SteinerForest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897
1995; Agrawal, Klein, Ravi
SteinerTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 900
2006; Du, Graham, Pardalos,Wan,Wu, Zhao
StochasticScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904
2001; Glazebrook, Nino-Mora
StringSorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907
1997; Bentley, Sedgewick
SubstringParsimony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910
2001; Blanchette, Schwikowski, Tompa
XXVI Table of Contents
SuccinctDataStructuresforParenthesesMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912
2001;Munro, Raman
SuccinctEncodingofPermutations:ApplicationstoText Indexing . . . . . . . . . . . . . . . . . . . . . . . . 915
2003;Munro, Raman, Raman, Rao
SuffixArrayConstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919
2006; K?rkk?inen, Sanders, Burkhardt
SuffixTreeConstructioninHierarchicalMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922
2000; Farach-Colton, Ferragina,Muthukrishnan
SuffixTreeConstructioninRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925
1997; Farach-Colton
SupportVectorMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928
1992; Boser, Guyon, Vapnik
SymbolicModelChecking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 932
1990; Burch, Clarke,McMillan, Dill
Synchronizers,Spanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935
1985; Awerbuch
TableCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 939
2003; Buchsbaum, Fowler, Giancarlo
TailBoundsforOccupancyProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 942
1995; Kamath, Motwani, Palem, Spirakis
TechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944
1987; Keutzer
TeleportationofQuantumStates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947
1993; Bennett, Brassard, Crepeau, Jozsa, Peres,Wootters
Text Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 950
1993;Manber, Myers
Thresholds of Randomk-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954
2002; Kaporis, Kirousis, Lalas
TopologyApproach inDistributedComputing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956
1999; Herlihy Shavit
Trade-OffsforDynamicGraphProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958
2005; Demetrescu, Italiano
TravelingSalesPersonwithFewInnerPoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
2004; De??neko, Hoffmann, Okamoto, Woeginger
TreeCompressionandIndexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964
2005; Ferragina, Luccio, Manzini,Muthukrishnan
Table of Contents XXVII
TreewidthofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968
1987; Arnborg, Corneil, Proskurowski
TruthfulMechanismsforOne-ParameterAgents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 970
2001; Archer, Tardos
TruthfulMulticast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973
2004; Wang, Li, Wang
TSP-BasedCurveReconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976
2001; Althaus, Mehlhorn
Two-DimensionalPatternIndexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 979
2005; Na, Giancarlo, Park
Two-DimensionalScaledPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 982
2006; Amir, Chencinski
Two-IntervalPatternProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985
2004; Vialette
2007; Cheng, Yang, Yuan
Two-LevelBooleanMinimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 989
1956;McCluskey
UndirectedFeedbackVertexSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995
2005; Dehne, Fellows, Langston, Rosamond, Stevens;
2005; Guo, Gramm, Hüffner, Niedermeier,Wernicke
UtilitarianMechanismDesignforSingle-MindedAgents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997
2005; Briest, Krysta, V?cking
VertexCoverKernelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1003
2004; Abu-Khzam, Collins, Fellows, Langston, Suters, Symons
VertexCoverSearchTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1006
2001; Chen, Kanj, Jia
VisualizationTechniquesforAlgorithmEngineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1008
2002; Demetrescu, Finocchi, Italiano, N?her
VoltageScheduling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1011
2005; Li, Yao
Wait-FreeSynchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1015
1991; Herlihy
WeightedConnectedDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1020
2005; Wang,Wang, Li
WeightedPopularMatchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1023
2006;Mestre
XXVIII Table of Contents
WeightedRandomSampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1024
2005; Efraimidis, Spirakis
WellSeparatedPairDecomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1027
2003; Gao, Zhang
WellSeparatedPairDecompositionforUnit–DiskGraph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1030
1995; Callahan, Kosaraju
WireSizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1032
1999; Chu, Wong
Work-FunctionAlgorithmforkServers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1035
1994; Koutsoupias, Papadimitriou
Chronological Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1039
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1157

数据结构与算法导学

2008-07-03 08:06:12

分点讲解数据结构和算法的知识点，后面还附有网友学习经验总结，非常适合刚接触数据结构和即将考试需要复习的人。目录如下：
第一章概论 3
第二章线性表 4
第三章栈和队列 8
第四章串 15
第五章多维数组和广义表 18
第六章树 20
第七章图 23
第八章排序 26
第九章查找 28
第十章文件 32

ShaderX系列 by NV and ATI (ShaderX to ShaderX3)

2008-06-29 11:30:20

1,ShaderX_ImageProcessingbyPS1.4
2,shaderx2_advancedimageprocessDX9
3,shader x3_ Advanced Rendering witDirectX and OpenGL
4,ShaderX_3DTextures
5,ShaderX_NonPhotorealisticRendering