How large should a hash table be? Goal: Make the table as small as possible but large enough so that it wont overflow(or otherwise become inefficient Problem: what if we don 't know the proper size

ynamic order statistics OS-SELECT(i, S): returns the i th smallest element in the dynamic set S. OS-RANK(, S): returns the rank ofx E S in the sorted order of s s elements IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes

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

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

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)

第三章静电场的边值问题 主要内容 电位微分方程,镜像法,分离变量法。 1.电位微分方程 已知,电位q与电场强度E的关系为

These notes introduce some ideas for modeling markets with adverse selec- tion. This framework was originally intended to deal with markets that cannot be easily accommodated by the standard signaling game e. g, be- cause there is two-sided adverse selection. For present purposes, however, it is enough to deal with the simplest case in which there is adverse selection

Ch. 7 Violations of the ideal conditions 1 ST pecification 1.1 Selection of variables Consider a initial model. which we assume that Y=x1/1+E, It is not unusual to begin with some formulation and then contemplate adding more variable(regressors) to the model

Ch. 5 Hypothesis Testing The current framework of hypothesis testing is largely due to the work of Neyman and Pearson in the late 1920s, early 30s, complementing Fisher's work on estimation. As in estimation, we begin by postulating a statistical model but instead of seeking an estimator of 6 in e we consider the question whether

本节试图抓住直线上的开区间、闭区间及其点的基本性质,予以一般化。 对ⅤEsR\,我们可以通过看是否有x的完整邻域含于E中将R\中点x分 为三类: