随机算法 12 Nearest Neighbor Search and Locality Sensitive Hashing
Nearest Neighbor Search 2D scenario: Voronoi Diagram 3D or higher dimensions: Not efficient. Fine-grained complexity Approximate nearest neighbor search Assume the distance between query point and its nearest neighbor is RRR, ccc-approximate RRR-near neighbor is all the points within range cR(c≥1)cR(c\ge1)cR(c≥1). input: point qqq, constant ccc, radium RRR. if there is a point ppp with dist(p,q)≤Rdist(p,q)\le Rdist(p,q)≤R, then return point p′p'p′ with dist(p′,q)≤cRdist(p',q)\le cRd ...
数据挖掘 12 Frequent Itemsets and Association Rules
Frequent itemsets and association rules. This problem aims to find a set of items that are bought together. These itemsets can be efficiently mined by exploiting the apriori principle of the support measure. Frequent Itemsets Mining Frequent itemsets: collections of objects that appear a minimum number of times in the baskets of the customers. Set of ddd items I\mathcal II, set of nnn transactions identifiers T\mathcal TT. Dataset D\mathcal DD is a set of pairs (i,t)∈I×T(i,t)\in\mathcal I\times ...
随机算法 11 Randomized Rounding for MAX SAT
MAX SAT and MAX CUT randomized ½ approximation for each problem MAX SAT aka maximum satisfiability problem Input consists of nnn Boolean variables x1,⋯ ,xnx_1,\cdots,x_nx1,⋯,xn, mmm clauses C1,⋯ ,CmC_1,\cdots,C_mC1,⋯,Cm. Clauses CjC_jCj consist of some number of variables and \or and a non-negative weight wjw_jwj. The objective of the problem is to find an assignment of xix_ixi that maximizes the weight of the satisfied clauses. A clause is said to be satisfied if one of the unnegat ...
法语学习 A1 Unité 4 Au rythme du temps
Leçon 13 Un aller simple Vocabulaire 方向有关的词汇 au nord-ouest 在西北方向 au nord-est 在东北方向 au sud-ouest 在西南方向 au sud-est 在东南方向 星期的表达 lundi 星期一 mardi 星期二 mercredi 星期三 jeudi 星期四 vendredi 星期五 samedi 星期六 dimanche 星期天 名词 gare f. 火车站 à la gare 咋爱火车站 quai m. 站台，月台；码头 horaire m. 时刻表，时间表 heure f. 时间/小时 pendule f. 挂钟，座钟；钟摆 classe f. 等级，级别 première classe 一等座 aller m. 去程票 Ex : un aller Paris-Marseille 一张巴厘岛马赛的票 Ex : un aller simple 一张单程票 un aller-retour 一张往返票 départ m. 出发 arrivée f. 到达（时间或地点），终点 tarif m. 定价，价 ...
Fair Division 7 Ex-ante and Ex-post Fairness
Objective: Explore randomized indivisible allocations (equivalent to fractional allocation) and their implications on fairness: the compatibility of Ex-ante and Ex-post fairness. Activities: Study the paper Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation. What does Both worlds here means? The indivisible allocation is randomized. Before the allocation, each agent has a expected valuation for the bundle. Ex-ante WORLD I After the allocation, each agent has its actual ...
丹麦语 DU 3.2 9-10 Arbejde og studieliv
er ansat af 受雇于 borger -en -ere- erne 公民 rækkefølge -n -r -rne 顺序 det værste 最坏的事 især 副词，尤其是 deltid 兼职 fuldtid 全职 Modultest DU 3.2 模拟题阅读部分 Opgave 1 是类似于中考英语的弱智题，直接可以找原文。注意用短回答 kortsvar，不要给自己加戏！ Opgave 2 我认为阅读部分最 SVÆRT 的题目，给五段话，每段话有一个句子不符合段落大意，需要划掉。因为生词太多了，根本读不懂！ 一种投机取巧的方式：每段话都选择最短的那个句子划掉。大概 80% 的情况下这样做答案是对的。 老师说，要做好这题，必须多读多积累单词😭 hjort -en -e -ene 鹿 springe ud 跳到跟前；保释 flyvende 飞行的 adj mørk 黑暗的 adj falde i søvn 入睡 pludselig 突然 adj ramme 击打；撞到 sikkerhedssele -n -r -rne 安全带 Ingen blev skadet. 没 ...
数据挖掘 11 Frequent Subgraph Mining
A labeled graph is a triple G=(V,E,ℓ)G=(V,E,\ell)G=(V,E,ℓ) where ℓ:V∪E→L\ell:V\cup E\rarr Lℓ:V∪E→L is a labeling function assigning a label from a set of labels LLL to each node and each edge. Definition of frequency: it is encoded into a support measure that return the number of occurrences of the subgraph in the graph. FSM in Graph Collections A graph collection aka a graph database is a set D={G1,G2,⋯ ,Gn}\mathcal D=\{G_1,G_2,\cdots,G_n\}D={G1,G2,⋯,Gn} of labeled graphs Gi=(Vi,Vi,ℓi),i∈[1 ...
随机算法 10 Invertible Bloom Filters
Brief Introduction Invertible Bloom Lookup Table (abbr. IBLT) a fancy hash-table stores key-value pair (x,y)(x,y)(x,y) space budget: ttt Guarantee It “works” when the number of key-value pairs, nnn, in table has n≤tn\le tn≤t. “temporarily” stops working if n>tn\gt tn>t. starts working again if nnn drops below ttt. Operations (x,y) is key-value pair. insert(x,y), delete(x,y), get(x), listentries. Details Start with table with k≥3k\ge3k≥3 rows, m=2×tm=2\times tm=2×t columns. In each row, ...
丹麦 IT 学生工求职记（已接 offer 版）
Kdag (Katrinebjerg Karrieredag) 2024 2024 年 4 月 12 日，期待已久的 Kdag 😍 在 Katrinebjerg AUDatalogi 的 Nygaard 楼，一年一度🎆 总共有 54 家企业/单位，针对 IT 的岗位信息交流会。我认得的企业也就 乐高、Arla（乳制品垄断企业，经常喝这家的牛奶）、Uber。 也有跟国防有关的企业，看宣传资料像是给 F35 战机生产零部件的企业，反正 in collaboration with Lockheed Martin （一眼不招非 EU 国籍的） 有些企业是针对丹麦本地的生意，或者员工大部分是丹麦人的。这种企业的宣传资料上只有丹麦语的，也可以直接跳过了。所以想在丹麦有更多的工作机会，需要学好丹麦语😭 还有就是，说 danish is not mandatory, but highly recommended 的，那就是 mandatory 的意思。 为什么我喜欢这样的活动 可以白嫖吃的喝的，谁不喜欢啊？😍😍😍 目标 主要是有 Student Job 岗位的企业，狠狠地投简历 ...
数据挖掘 10 Graph Neural Networks
GNN - graph neural networks Intuition: how to propagate information over the neighbors in a non-linear manner. Graph Embeddings as Matrix Factorization Linear embeddings correspond to SVD of the similarity matrices chosen in the objective. For adjacency-based similarity, the best linear ddd-dimensional embedding corresponds to the projection of the dataset into the ddd directions associated to the top-ddd singular values: if SVD(A)=UΣV⊤then the embedding matrix Z=UdΣd\text{if }SVD(\mathbf A)=\m ...
