# CSCI5450 Randomness and Computation

 Course code CSCI5450 Course title Randomness and Computation 隨機性與計算 Course description This course is to study the use of randomness in theoretical computer science. We will introduce basic probability tools (e.g. random variables, expectation, moments and derivations, tail inequalities, martingales) and probabilistic methods (e.g. first moment method, second moment method, Lovasz local lemma, semi-random method). Then we will show how these tools and methods can be used to design randomized algorithms (e.g. graph algorithms, number-theoretic algorithm, computational geometry), efficient data structures (e.g. balls and bins, hashing, load balancing), and sublinear algorithms (e.g. property testing, constant time algorithms, data streaming). We will also demonstrate how these tools and methods can be combined with other techniques, such as Markov chain and random walk (e.g. electric networks, expanders, random sampling, approximate counting), algebraic techniques (e.g. determinant method, fingerprinting, polynomial identity testing, interactive proof), and mathematical programming (e.g. linear programming, randomized rounding, semidefinite programming). Finally we study some methods of derandomization (e.g. conditional probability, k-wise independence, small-bias space, pseudorandom generator). 本科研究理論計算機科學中隨機性的應用。我們會介紹基本的概率工具（例如：隨機變量，期望，矩與求導，尾不等式，鞅）及概率方法（例如：第一矩法，二次矩方法，洛瓦茲局部引理，半隨機方法）。然後我們會學習如何運用這些方法來設計隨機算法（例如：圖論算法，數論算法，計算幾何）、高效數據結構（例如：球和箱，哈希，負載平衡）以及次線性算法（例如：屬性測試，常數時間算法，數據流）。上述方法還能結合其他技巧，如馬可夫鏈與隨機漫步（例如：電氣網絡，expander，隨機取樣，近似計數）、代數方法（例如：行列式方法，fingerprinting，多項式判等，交互證明）以及數學規劃（例如：線性規劃，隨機取整，（正）半定規劃）。最後我們將研究去隨機化的一些方法，如：條件概率，每k元獨立，小偏差空間，偽隨機生成器。 Unit(s) 3 Course level Postgraduate Semester 1 or 2 Grading basis Graded Grade Descriptors A/A-:  EXCELLENT – exceptionally good performance and far exceeding expectation in all or most of the course learning outcomes; demonstration of superior understanding of the subject matter, the ability to analyze problems and apply extensive knowledge, and skillful use of concepts and materials to derive proper solutions. B+/B/B-:  GOOD – good performance in all course learning outcomes and exceeding expectation in some of them; demonstration of good understanding of the subject matter and the ability to use proper concepts and materials to solve most of the problems encountered. C+/C/C-: FAIR – adequate performance and meeting expectation in all course learning outcomes; demonstration of adequate understanding of the subject matter and the ability to solve simple problems. D+/D: MARGINAL – performance barely meets the expectation in the essential course learning outcomes; demonstration of partial understanding of the subject matter and the ability to solve simple problems. F: FAILURE – performance does not meet the expectation in the essential course learning outcomes; demonstration of serious deficiencies and the need to retake the course. Learning outcomes • Understanding of the use of randomness in computation. • Skills to apply probability tools in solving problems. Assessment (for reference only) Project: 50% Homework or assignment: 50% Recommended Reading List Sketching as a Tool for Numerical Linear Algebra. David Woodruff, Foundations and Trends® in Theoretical Computer Science, Vol 10, Issue 1–2, 2014.

 CSCIN programme learning outcomes Course mapping Upon completion of their studies, students will be able to: 1. identify, formulate, and solve computer science problems (K/S); 2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S); 3. receive the broad education necessary to understand the impact of computer science solutions in a global and societal context (K/V); 4. communicate effectively (S/V); 5. succeed in research or industry related to computer science (K/S/V); 6. have solid knowledge in computer science and engineering, including programming and languages, algorithms, theory, databases, etc. (K/S); 7. integrate well into and contribute to the local society and the global community related to computer science (K/S/V); 8. practise high standard of professional ethics (V); 9. draw on and integrate knowledge from many related areas (K/S/V); Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured