随机算法 3 Hash Functions
Lecturer: Kasper Lecture notes is based on High Speed Hashing for Integers and Strings by Mikkel Thorup Hash Functions Universe UUU. Mapping randomly to a range [m]={0,⋯ ,m−1}[m]=\{0,\cdots,m-1\}[m]={0,⋯,m−1}. Truly random hash function h:U→[m]h:U\rarr[m]h:U→[m]. hhh is idealized, can not be implemented. To represent a truly random hash functions, we need to store at least ∣U∣log2m|U|\log_2m∣U∣log2m bits. (too large, impossible!) Idea: hash functions contain only a small element or seed of ra ...
数据挖掘 3 Densiy-based Clustering
Density-based departs from the rigid geometrical structure of representative-based clustering and defines cluster as high-density regions separated by low density regions. Density is number of points in a certain region in proportion to the size of the region. Different definition of density, different density-based approaches. DBSCAN A density-based clustering algorithm grounded into the intuition that a point in a cluster should be density reachable from any other point in that cluster, i.e., ...
丹麦语 DU 3.2 2 Invitationer (2)
Gennemgang af modul 1 复习 modul 1 的内容：数字、简单的问题、日期等。 Feedback aflevering 太正式/用法错误 更合适 … tilbringe tid sammen Skal vi ikke + infinitiv/Det kunne være hyggeligt at ses/Skal vi hænge lidt ud? i min bolig hjemme hos mig pas på! pas på dig selv Kære Peter, hvordan går det? Kære Peter Hvordan går det? （信件开头没有逗号，首字母大写） lad mig vide fortæl mig… På besøg lukker op 开门 gamle naboer 以前的邻居 smukke 华丽的 Om præferencer Godt godt 的比较级 bedre、最高级 bedst positiv: Jeg kan godt lide kager. 我喜欢蛋糕。 k ...
随机算法 2 Probabilistic Inequalities, Hashing with Chaining
This time: Kasper Green Larsen No slides! Basic Probabilistic Inequalities The Dictionary Problem: set SSS of nnn keys: x1,⋯ ,xnx_1,\cdots,x_nx1,⋯,xn from a universe [U]={0,⋯ ,U−1}[U]=\{0,\cdots,U-1\}[U]={0,⋯,U−1}. Goal: To store SSS in a data structure s.t., given a query element x∈[U]x\in[U]x∈[U], we can quickly determine whether x∈Sx\in Sx∈S. Hashing with Chaining: A data structure solves the dictionary problems: Construct an array AAA with mmm entries, denoted A[0],⋯ ,A[m−1]A[0],\cdots,A[ ...
数据挖掘 2 Representation-based Clustering
What is Clustering Grouping a set of data objects into clusters Cluster: a collection of data objects Similar to one another within the same cluster Dissimilar to the objects in other clusters Cluster = unsupervised classification no predefined classes Usage Get insight into data distribution Preprocessing step for other algorithms Application of Clustering Pattern Recognition and Image Processing Spatial Data Analysis WWW Biology Information retrieval Marketing City-planning Social net ...
德语学习 B2 Kapitel 4 Zusammen leben
Inhalt Sport gegen Gewalt Armut im Netz Der kleine Unterschied 4-1 Zusammen leben mit jmdm fertigwerden 能对付某人 wühlen 挖，翻，刨 v grunzen （猪叫）噜噜叫 v schluchzen 抽泣，哽咽 der Matsch 烂泥 sich suhlen 打滚 artgerecht 适应该物种的 fürchterlich = furchtbar 可怕的，很糟糕的 die Eltern in die Schule bestellen 叫家长来学校谈话 das Solarium-rien 日光浴 der Knödel- 丸子 eintüten 把……装入袋中 Alles eingetütet. 一切顺利。= Alles erledigt. = Alles gut klaret. = Alles gut gelaufen. Schön wärs! 有完没完！ 4-2 Sport gegen Gewalt (1) die Gewalt 暴力；强权 ein Dach ...
Fair Division 1 Survey Study
在和扬尼斯教授交流后，我确定了 24 Spring 这 10 ECT 的 Projektarbejde i Datalogi 的具体方向为“不可分割物品的公平分配博弈” Fair Division with Indivisible Items 美美考完算法博弈论，从扬尼斯教授这拿了 12 分之后，我就得开搞 Projekt 了。 Objective Gain familiarity with fairness notions and key results in fair division with indivisible items. Fairness Notions Denotation Set NNN of nnn agents Set MMM of mmm indivisible goods For agent iii: Valuation function vi:2M→R≥0v_i:2^M\rightarrow\mathbb R_{\ge0}vi:2M→R≥0. vi(∅)=0,vi(S)≤vi(T)∀S⊆T⊆Mv_i(\emptyset)=0,v_i(S)\l ...
丹麦语 DU 3.2 1 Invitationer (1)
DU 3.2 换老师了，换成了 Lisbeth Døssing Mortensen 女士。 教材是 Videre mod dansk 《进一步走向丹麦语》 Faste udtryk Jeg er meget glad for (substantiv/at infinitiv) 我很乐意（做）…… Det er vigtigt for mig (substantiv/at infinitiv) （做）……对我很重要 Jeg er træt af (substantiv/at infinitiv) 我厌倦（做）…… Jeg har lyst til (substantiv/at infinitiv) 我对（做）……感兴趣 Jeg har brug for (substantiv/at infinitiv) 我需要（做）…… Subjekt + glæder + refleksiv for (substantiv/at infinitiv) 某人很乐意（做）某事 desværre 很遗憾 Det vil jeg (meget) gerne. 我很乐意。 Velkommen/Kom inde ...
随机算法 1 Examples of Randomized Algorithm
Course Info 3 Project - 30% (A group of 3 people) Oral Exam - 70% Prof. Ioannis Caragiannis and Prof. Kasper Green Larsen Randomization Randomization algorithms use random coins, dice, card shuffling etc. Assumptions Fair coins Pr[HEADS]=Pr[TAILS]=1@\Pr[HEADS]=\Pr[TAILS]=\frac{1}{@}Pr[HEADS]=Pr[TAILS]=@1 More complicated operations Random selection among a finite set of items Access to a random permutation of elements Selection of a random point in the interval [0,1][0,1][0,1] Selection f ...
数据挖掘 1 Introduction
Brief Introduction to This Course 3 Modules Clustering - 4 Lectures Representative-based Density-based Hierarchical and Subspace Outlier Detection Graph Mining - 5 Lectures Spectral Theory and Clustering Community Detection Link Analysis Similarities and Graph Embeddings Graph Convolutional Networks Pattern Mining - 3 Lectures Frequent Subgraph Mining Frequent Items and Association Rules Sequence Mining Similarities and Stream Mining Three hand-ins (⚠️Graded 10% each) for each topic ...
