Combinatorics and Algorithms Design

This course covers topics in Combinatorics and Algorithms Design. We comprehensively discuss basic concepts, theories, methods, and instances in Combinatorics while focusing on concepts and ideas. We also discuss basic mathematics concepts in algorithms design including growth of function, Big-O notations and recurrence relations etc., and basic strategies of algorithms design including randomized algorithms, divide and conquer, and dynamic programming etc.

播放:216次,课程ID:4048105

Combinatorics and Algorithms Design课程简介:前往报名学习

Combinatorics and Algorithms Design课程简介:

This course covers topics in Combinatorics and Algorithms Design. We comprehensively discuss basic concepts, theories, methods, and instances in Combinatorics while focusing on concepts and ideas. We also discuss basic mathematics concepts in algorithms design including growth of function, Big-O notations and recurrence relations etc., and basic strategies of algorithms design including randomized algorithms, divide and conquer, and dynamic programming etc.

前往报名学习

Combinatorics and Algorithms Design课程目录:

Introduction to Combinatorial Mathematics

--What's Combinatorial Mathematics

--The Most Ingenious Arrangement - Magic Square

--Suffering Parchment Roll

--Is Your Phone Password Safe

--Brute-force Enumaration OR Abstract Conversion

--Homework 1

--Demo Of Week 1

Combinatorial trip of a Pingpong ball

--Counting with "+" "-" "*" "/"

--Permutation or Combination?

--Various Permutations

--Different Kinds of Combinations

--Permutation In The Bell Ring

--Homework 2

--Demo Of Week 2

Generating Function

--Generating Function & Counting Rules

--Simple Application Of Generating Function

--Integer Partition

--Ferrers Diagram

--Generating Function And Recurrence Relation

--Homework 3

--Demo of Week 3

Linear Homogeneous Recurrence Relation

--Fibonacci Sequence

--Application Of The Fibonacci Sequence

--Linear Homogeneous Recurrence Relation

--Examples

--Homework Of Week 4

--Demo Of Week4

--Behind the scenes extra

Magical Sequences

--Catalan Numbers

--Exponential Generating Functions

--Derangements

--Stirling Numbers

--Summary of Generating Function

--Homework of Week 5

--Demo of Week 5

Inclusion-Exclusion Principle And Pigeonhole Principle

--Inclusion And Exclusion Principle

--The Elegancy Of Inclusion-Exclusion Principle

--New solutions to old problems

--Pigeonhole Principle

--Visible Pigeonholes

--6 People And Ramsey

--Homework Of Week 6

Introduction to Algorithms Design

--What is Algorithm?

--Example: Majority Element

--Algorihtm Complexity

--Asymptotic Analysis

--Homework of Week 7

Incremental Algorithms

--Elements of Incremental Algorithms

--Loop Invariant

--Example: Insertion Sort

--Example: 2-Color Dutch National Flag Problem

--Homework of Week 8

Divide and Conquer

--Design Paradigm

--Example: Merge Sort

--Example: Order Statistics: Select: Partition

--Example: Order Statistics: Select: Linear Time

--Substitution Method

--Recursion Tree Method

--The Master Method

--Homework of Week 9

Randomized Algorithms

--Indicator Random Variable

--Hiring Problem

--On-line Hiring Problem

--Randomized Algorihtm

--Example: Randomized Select

--Example: Randomized Select Analysis

--Homework of Week 10

Dynamic Programming

--Maximum Subarray: D&C solution

--Maximum Subarray: Dynamic Programming Solution

--Optimization Problems: Knapsack and Matrix Chain Multiplication

--Steps of Dynamic Programming (1&2 Recursively Define Optimal Solutions)

--Steps of Dynamic Programming (3&4 Compute Optimal Solutions)

--Summary

--Homework of Week 11

Group (Optional)

--Turnable World

--Permutation Group

--Burnside Lemma

Polya Theorem (Optional)

--The Plight of Burnside Lemma

--From Burnside to Polya

--Rotating Polyhedron

--Generating Functon Type of Polya Theorem

Final Exam

--Final Exam

Combinatorics and Algorithms Design授课教师:

马昱春-副教授-清华大学-计算机科学与技术系

博士,清华大学计算机科学与技术系副教授,2004年毕业于清华大学计算机系,获清华大学优秀毕业生称号,2005年-2006年赴美国加州大学洛杉矶分校访问,主要从事微处理器系统设计以及芯片自动化设计研究,参与多项国家重点科研项目,在国际一流期刊和学术会议上发表论文60余篇,其中SCI检索15篇,多次获得国际会议的最佳论文奖以及最佳论文候选。教学方面成果突出,其负责的《组合数学》课程连续被评为清华大学研究生精品课,2013年获得北京高校第八届青年教师教学基本功比赛理工组一等奖,2014年获得清华大学青年教师教学优秀奖。目前其讲授的《组合数学》MOOC课程在学堂在线和edx平台上中英文两个版本同时开课,注册学习人数超过6万人。该课程自2014年上线以来就以其精巧的设计,清晰的讲授,极具特色的诠释方法受到学习者的喜爱,网上学习者评价该课程“堪称MOOC必选课之一”。课程的运营中充分体现以学习者为中心的理念,让一门传统意义上枯燥晦涩的计算机专业基础理论课变得生动而富有活力,备受国内外学习者好评, 2015年在果壳网全球MOOC排行榜中位列全球1800余门课中第20(并列)。2017年被评为首批国家级精品在线开放课程。

赵颖-副教授-清华大学-计算机科学与技术系

赵颖,清华大学计算机系副教授,主要研究领域为数据挖掘、机器学习与自主计算。来华留学品牌课程“组合数学与算法设计”主讲教师。担任或曾担任KDD、WWW、ICDM、CIKM、SDM、IEEE Transaction on Knowledge and Data Engineering、Data Mining and Knowledge Discovery等国际会议或者学术期刊的程序委员会委员或审稿人;在ICDE、CIKM、SDM、Machine Learning、DAMI等著名国际会议和期刊上发表论文50余篇。获2007年国家留学基金委IBM奖研金、2011年深圳市海外高层次人才创新创业专项资金。

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。