a weakness of hashing Problem: For any hash function h, a set of keys exists that can cause the average access time of a hash table to skyrocket An adversary can pick all keys from tkeU: h(k)=i for some slot i IDEA Choose the hash function at random independently of the keys

Symbol-table problem Symbol table T holding n records

Order statistics Select the ith smallest of n elements(the element with rank i i=l: minimum, .i=n: marimum, i=L(n+1)/2]or[(n+1)/2 median Naive algorithm: Sort and index ith element Worst-case running time =o(n Ig n)+o(1 o(nIg n using merge sort or heapsort(not quicksort) c 2001 by Charles E Leiserson

How fast can we sort? All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements E. g, insertion sort, merge sort, quicksort heapsort The best worst-case running time that weve seen for comparison sorting is O(nIgn) Is o(nlgn) the best we can do?

Quicksort Proposed by C. A.R. Hoare in 1962 Divide-and-conquer algorithm Sorts“ in place”( like insertion sort, but not like merge sort Very practical(with tuning)

The divide-and-conquer design paradigm 1. Divide the problem(instance) into subproblems 2. Conquer the subproblems by solving them recursively 3. Combine subproblem solutions

Solving recurrences The analysis of merge sort from Lecture I required us to solve a recurrence Recurrences are like solving integrals erential equations, etc o Learn a few tricks Lecture 3: Applications of recurrences

Welcome to Introduction to Algorithms, Fall 2001 Handouts 1. Course Information 2. Calendar 3. Registration (MIT students only) 4. References 5. Objectives and Outcomes 6. Diagnostic Survey

实验二波形输入与仿真实现 一、实验目的:通过本次实验掌握波形输入法制作元件的过程,掌握实验箱中时钟和扬声器的具体使用方法以及任意模值计数器的设计方法。 二、实验要求: 1、利用波开输入法设计非门电路模块。 2、利用VHDL语言输入方法设计数据选择器(参考二选一数据选择器程序),编译、定义引脚并下载到实验箱中验证

通信与信息工程系 综合、设计性实验指导书 课程名称:可编程ASIC原理 实验项目名称:数字钟设计 一、实验目的与要求: (1)、使用VHDL语言或 Verilog语言设计数字钟。 (2)、正确选择实验箱的工作模式。 (3)、正确配置FPGA的引脚。 (4)、实验前预习数字钟原理