logo资料库

Algorithm Design and Applications.pdf

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：12.26M 资料格式：pdf 举报 版权申诉
第1页 / 共803页
第2页 / 共803页
第3页 / 共803页
第4页 / 共803页
第5页 / 共803页
第6页 / 共803页
第7页 / 共803页
第8页 / 共803页
资料共803页，剩余部分请下载后查看
    www.it-ebooks.info
    Algorithm Design and Applications Michael T. Goodrich Department of Information and Computer Science University of California, Irvine Roberto Tamassia Department of Computer Science Brown University www.it-ebooks.info
    www.it-ebooks.info
    iii www.it-ebooks.info
    To Karen, Paul, Anna, and Jack – Michael T. Goodrich To Isabel – Roberto Tamassia www.it-ebooks.info
    Contents Preface 1 Algorithm Analysis 1.1 Analyzing Algorithms . . . . . . . . . . . . . . . . . . . . . . . 1.2 A Quick Mathematical Review . . . . . . . . . . . . . . . . . . 1.3 A Case Study in Algorithm Analysis . . . . . . . . . . . . . . 1.4 Amortization . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Part I: Data Structures 2 Basic Data Structures 2.1 Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . 2.2 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1 3 19 29 34 42 51 53 60 68 84 3 Binary Search Trees 89 3.1 Searches and Updates . . . . . . . . . . . . . . . . . . . . . . 91 3.2 Range Queries . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.3 Index-Based Searching . . . . . . . . . . . . . . . . . . . . . 104 3.4 Randomly Constructed Search Trees . . . . . . . . . . . . . . 107 3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4 Balanced Binary Search Trees 115 4.1 Ranks and Rotations . . . . . . . . . . . . . . . . . . . . . . . 117 4.2 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.3 Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . 126 4.4 Weak AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . 130 4.5 Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5 Priority Queues and Heaps 155 5.1 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . 157 5.2 PQ-Sort, Selection-Sort, and Insertion-Sort . . . . . . . . . . 158 5.3 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 5.4 Heap-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 5.5 Extending Priority Queues . . . . . . . . . . . . . . . . . . . . 179 5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 v www.it-ebooks.info
    vi Contents 6 Hash Tables 187 6.1 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 6.2 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 192 6.3 Handling Collisions and Rehashing . . . . . . . . . . . . . . . 198 6.4 Cuckoo Hashing . . . . . . . . . . . . . . . . . . . . . . . . . 206 6.5 Universal Hashing . . . . . . . . . . . . . . . . . . . . . . . . 212 6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 7 Union-Find Structures 219 7.1 Union-Find and Its Applications . . . . . . . . . . . . . . . . . 221 7.2 A List-Based Implementation . . . . . . . . . . . . . . . . . . 225 7.3 A Tree-Based Implementation . . . . . . . . . . . . . . . . . . 228 7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Part II: Sorting and Selection 8 Merge-Sort and Quick-Sort 241 8.1 Merge-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 8.2 Quick-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 8.3 A Lower Bound on Comparison-Based Sorting . . . . . . . . 257 8.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 265 9 Fast Sorting and Selection 9.1 Bucket-Sort and Radix-Sort . . . . . . . . . . . . . . . . . . . 267 9.2 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 9.3 Weighted Medians . . . . . . . . . . . . . . . . . . . . . . . . 276 9.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 Part III: Fundamental Techniques 10 The Greedy Method 283 10.1 The Fractional Knapsack Problem . . . . . . . . . . . . . . . 286 10.2 Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 289 10.3 Text Compression and Huffman Coding . . . . . . . . . . . . 292 10.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 11 Divide-and-Conquer 303 11.1 Recurrences and the Master Theorem . . . . . . . . . . . . . 305 11.2 Integer Multiplication . . . . . . . . . . . . . . . . . . . . . . . 313 11.3 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . 315 11.4 The Maxima-Set Problem . . . . . . . . . . . . . . . . . . . . 317 11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 www.it-ebooks.info
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料