课程简介
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. Selected topics include: the Pigeonhole Principle, counting, combinations, Polya counting, recurrence relations and generating functions, graph, and linear programming etc. 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.
课程大纲
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
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