資料流分析演算法(英文授課)
streaming algorithms
學期
106-2
學分
3
學分
當期課號
5248
永久課號
IOC5196
開課單位
資訊科學與工程研究所
授課教師
蔡孟宗
校區
光復
類別
選修
上課時間表
| 節 | 週二 | 週五 |
|---|---|---|
3 10:10–11:00 | 資料流分析演算法(英文授課) ED102 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 資料流分析演算法(英文授課) ED102 |
* 根據陽明交大上課時間表所列
概述
Introduction to the design of algorithms to process huge amounts of data.
先修科目
Introduction to Algorithms
評分方式
3 Programming Assignments (30%), 3 Written Assignments (30%), Final Project (40%)
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction to Streaming Models, The Basics |
| 第 2 週 | The Probabilistic Method |
| 第 3 週 | The Probabilistic Method |
| 第 4 週 | Count Sketch, Count-Min Sketch, Heavy Hitter |
| 第 5 週 | Frequency Moments |
| 第 6 週 | Approximate Median |
| 第 7 週 | Graph Streaming, Minimum Spanning Trees, k-EC, k-VC |
| 第 8 週 | Approximate Shortest Paths, Graph Spanners |
| 第 9 週 | Maximum Matching |
| 第 10 週 | Maximum Independent Set, Turan’s Theorem |
| 第 11 週 | Geometric Streaming, Minimum Enclosing Ball Problem |
| 第 12 週 | Communication Complexity, The Index Problem |
| 第 13 週 | Reductions from Communication Complexity to Streaming Problems |
| 第 14 週 | Fooling Set Method, Set-disjointness, Equality Problem |
| 第 15 週 | Information Complexity, The Augmented Index Problem |
| 第 16 週 | Turnstile Model, Lp Sampler |
| 第 17 週 | Selected Applications of Lp Sampler |
| 第 18 週 | Final Project Presentations |
教科書
TBA
Office Hours
- 地點
- EC 336
- 時間
- TBA