● Generalspeaking,NOcomparison-basedsortingalgorithmcan have a better efficiency than O(NlogN)
● Therefore,pre-sortingtechniqueissuperiorinsomeproblems where sorted input(array) can easily return the solution of the problem.
● Sincepre-sortingrequiresexecutionofsortingalgorithms,thebest case time complexity of pre-sorting is O(NlogN)
UNIQUENESS CHECKING
Brute Force: checking uniqueness in an array requires O(N^2)
Pre-sorting: Complexity of Sort + Complexity of Scan = ? How can we scan?
function ckeckBill(bill[·], n, check[·], m) MergeSort(bill)
MergeSort(check) Unpaid_bill <- [] b<- 0
While c < m and b < n do
If Bill[b] = Check[c] do b <- b+1
c <- c+1 else
Unpaid_bill[ub] <-Bill[b] b <- b+1
return unpaid_bill s.name
s.homeaddress
[s1,s2,s3,s4,s5,s6]
Dict { key 保存州名， value: 学生个数} For i in 0 to S.len do
state_name = S[i].homeaddress.state_name if state_name exist in dict then
dict[state_name] <- dict[state_name] +1 else
dict[state_name] <- 1 Return dict
SPACE/TIME TRADE OFF
Also called input enhancement
the idea is to preprocess the problem’s input, in whole or in part, and store the additional information obtained to accelerate solving the problem afterward
HORSPOOL’S STRING SEARCH
● Utilizedthepatternthatuseforsearchingtocreateashifttable
● Ifsamecharacterexist,shiftvaluedeterminebythelastcharacter
in pattern
● Attention:Lastcharacterinthepatterndoesn’tconsider
PSEUDOCODE
● 哈希Hashing是实现字典Dictionary的标准方式
● Dictionary是一个ADT(abstractdatatype)以键值对的形式储存数据
● key-valuepair/attribute-valuepair
● 每一条数据identifiedbykey
● Key可以是Integer,Char甚至String
● 数据储存在hashtable中
● hashfunctionh(k)对数据的key进行hash处理
● 得到一个int值作为value的index,储存在hashtable中
● hashfunction是一个数学运算,运算结果得到hashaddress
● 不同的key可能会得到相同的hashaddress,称为collision,也叫哈希
SEPARATE CHAINING
● 减少比较次数(reduce the number of comparisons)
● 动态性(goodindynamicenvironment),当key数量不确定时 ● chains是可以排序的(sortable),也可以pulledupfront
● 删除更简单(easytodeletedata)
● 额外的空间储存link(additionalspacetostoragelinkedlist)
load factor = n/m
● Numberofprobesinsuccessfulsearch~1+(𝛼/2) ● Numberofprobesinunsuccessfulsearch~𝛼
A = 1, B = 2, C = 3, Unordered list
D = 4, 11 * 4 mod 5 = 4
E = 5, 11 * 5 mod 5 = 5
M = 13, 13 * 11 mod 5 = 3 O = 15, 15 * 11 mod 5 = 0 C = 3, 3 * 11 mod 5 = 3
R = 18, 18 * 11 mod 5 = 3 A = 1, 1* 11 mod 5 = 1
T = 20, 20*11 mod 5 = 0 S = 19, 19* 11 mod 5 = 4 Ordered list
LINEAR PROBING
当冲突的时候, 尝试下一个cell, 如果下一个还是冲突, 继续尝试下一个, 如 果到结尾还是冲突, 返回到0重新尝试
Add [83(14) 110(18) 497(14)] to the table
黑色为值, 红色为address
Number of probes in successful search ~ 0.5 + 1/(2(1-α )) Number of probes in unsuccessful search ~ 0.5 + 1/(2(1-α )^2) Linear probing会导致很长的一段cells被占用, 称为clustering 删除很困难, 因为要rehashing所有key, 需要很长时间
DOUBLE HASHING
一种解决clustering 的方法
当冲突时, 使用第二种 hash function s(k)去计算偏移的位置
Linear probing 中冲突寻找的是下一位
而double hashing中寻找的是下s(k)位, 如果冲突, 继续寻找至有空位
每次s(k)后都要mod 11 否则可能会找不到位置(越界) 结果是h=[2 9 4 7 0]
如果m是prime number素数, 那我们终会找到一个free cell
12: 12(12+3) mod 7 = 5 7: 7(7+3) mod 7 = 0
6: 6(6+3) mod 7 = 5
8: 8(8+3) mod 7 = 4
i. Separate Chaining
ii. Linear Probing
α = n/m = 4/7
0.5 + 1/(2(1- 4/7)) = 1.6667 b.
DYNAMIC PROGRAMING
● analgorithmdesigntechnique
● applicablewhensolvingarecurrencerelationandtherecursion
involves overlapping instances.
● Ratherthansolvingoverlappingsubproblemsagainandagain,
dynamic programming suggests solving each of the smaller subproblems only once and recording the results in a table from which a solution to the original problem can then be obtained.
● CoinRow,Knapsack,Warshall’salgorithm,Floyd’salgorithmetc.
WARSHALL’S ALGORITHM
● Purpose:computesthetransitiveclosureofabinaryrelation(ora directed graph), presented as a matrix.
● Transitiveclosure:Anedge(a,z)isinthetransitiveclosureof graph G if and only if there is a path in G from a to z.
FLOYD’S ALGORITHM
● Floyd'salgorithmsolvestheall-pairsshortest-pathproblemfor weighted graphs with positive weights.
● Itworksfordirectedaswellasundirectedgraphs
D[3,1] = 4, D[1,2] = 8, D[1,4] = 1 D[2,1] = 5, D[1,4] = 1, D[2,4] = 6 D[3,2] = 12, D[3,4] = 5
D[1,2] = 8, D[2,3] = 1, D[1,3] = 9 D[4,2] = 2, D[2,3] = 1, D[4,3] = 3
D[1,3] = 9, D[3,2] = 12, D[1,2] = 8 D[2,3] = 1, D[3,1] = 4, D[2,1] = 5 D[2,3] = 1, D[3,4] = 5, D[2,1] = 6 D[4,3] = 3, D[3,1] = 4, D[4,1] = 7 D[4,3] = 3, D[3,2] = 12, D[4,1] = 2
D[1,4] = 1, D[4,2] = 2, D[1,2] = 3 D[1,4] = 1, D[4,3] = 3, D[1,3] = 4
SPANNING TREES
● SpanningtreeisthesubsetforagivenGraphG
● Minimumspanningtreeisaspanningtree,withtheleasttotal weight of all edges.
● AMaximalspanningtreeistheoppositeofaminimumspanning tree, the weight of its edges has the greatest value in total.
GREEDY ALGORITHMS
● Ingeneral,itisunusualthatlocallybestchoicesyieldglobalbest results
● However,thereareproblemsforwhichagreedyalgorithmis correct and fast
● Insomeotherproblems,agreedyalgorithmisanacceptable approximation algorithm
Prim’s algorithm
● Findingminimumspanningtree
● Prim’salgorithmcanstartfromanynode
● Minimumspanningtree:subgraphasatreewiththeleastcost
Dijkstra’s algorithm
Single-source shortest path