- Welcome to the class. Have fun!
- Please send an email to your TA before 12/27/2011 (Check MCS_TA_Assignment.xls to find your TA)
- We have 14 homeworks (10 questions per day) and 2 exams (Midterm, Final) in this course.
- Please finish your homework within 2 days. (E.g., HW1 is assigned on Dec.26th, then you should submit it no later than 8:00pm, Dec.28th). Late submission is not accepted.
- Midterm exam is on Jan.4th (1 hour); Final exam is on Jan.13th (2.5 hours).
- TA Office Hour: 1:00-4:00pm, 12/31/2011 (Saturday), Zhiyuan College Room 601.
- TA Office Hour (for Midterm): 6:00pm, 1/5/2012 (Thursday), Telecom Building 3-410 (电信群楼 3-410).
- TA Office Hour (for Final): 1/12/2012 (Thursday). Time：1:00-4:00pm, Location: Telecom Building 3-414 (电信群楼3-414).
- Please contact TA representative Rong Ma (马融) to pick up your homeworks (posted 1/13/2012).

Undergraduates

Dong ZhongYuan 1-300 (东中院1-300)

John E. Hopcroft, jeh(at)cs.cornell.edu

- Xiaofeng Gao (高晓沨), gao-xf(at)cs.sjtu.edu.cn
- Huan Long (龙环), longhuan(at)sjtu.edu.cn

- Representative: Rong Ma (马融), marong1204(at)gmail.com
- There are totally 10 TAs:
- Qiang Yin (尹强) yinqiang.sjtu(at)gmail.com
- Meixian Chen (陈美先) misamchen(at)gmail.com
- Mingzhang Huang (黄明璋) mingzhanghuang(at)gmail.com
- Minjie Wang (王敏捷) jpeng.zhang(at)gmail.com
- Yuanjian Zhou (周元剑) woodobserver(at)gmail.com
- Peichao Zhang (张培超) starforever00(at)gmail.com
- Li Han (韩立) lihancom.g(at)gmail.com
- Yihe Zhu (朱一和) sjtu.pigoneand(at)gmail.com
- Jianghong Shi (施江虹) zjjxsjh(at)gmail.com
- Peining Zheng (郑培凝) ryanzheng86(at)gmail.com

- Each TA is responsible for 15 students.
- Please click MCS_TA_Assignment.xls to check who is your TA and contact with him/her directly.

Dec.26 | Dec.27 | Dec.28 | |

8:30am-11:00am | Mingzhang Huang, Jiapeng Zhang | ||

1:00pm-3:30pm | Qiang Yin, Meixian Chen | Yuanjian Zhou, Peichao Zhang | |

Dec.29 | Dec.30 | Dec.31 | |

8:30am-11:00am | Li Han, Yihe Zhu | Peining Zheng, Jianghong Shi | Qiang Yin, Meixian Chen |

1:00pm-3:30pm | |||

Jan.4 | Jan.5 | Jan.6 | |

8:30am-11:00am | Mingzhang Huang, Jiapeng Zhang | Yuanjian Zhou, Peichao Zhang | Li Han, Yihe Zhu |

1:00pm-3:30pm | |||

Jan.7 | Jan.9 | Jan.10 | |

8:30am-11:00am | Peining Zheng, Jianghong Shi | Qiang Yin, Meixian Chen | Minzhang Huang, Jiapeng Zhang |

1:00pm-3:30pm | |||

Jan.11 | Jan.12 | Jan.13 | |

8:30am-11:00am | Yuanjian Zhou, Peichao Zhang | Li Han, Yihe Zhu | Peining Zheng, Jianghong Shi |

1:00pm-3:30pm |

**Set:**definition,operations, representations, relations, etc.**Cardinality:**definition,halting problem, etc.**Proofs:**informal proof, proof by contraction, nonconstructive proof, Pigeon hole principle, etc.**Recurrence Relationships:**Fibonacci, Solving recurrence relations, Differential equations, Vector spaces and linear algebra**Number Theory:**Divisibility, Modular Arithmetic, Euclead’s algorithm, Chinese remainder theorem**Encryption:**Prime number theorem, Relative primality, The Fundamental Theorem of Arithmetic, Open problems, Public-Key Cryptosystems and RSA**Combinatorics:**Product rule, Sum rule, Stirling’s formula, Permutation, Principle of inclusion and exclusion, Balls and Urns, Pigeon hole principle.**Polya:**Polya Theory of Counting, Groups, Functions, Burnside Theorem.**Probability:**Birthday problem, Hashing collision, Union bound, Conditional probability, Universal Hash Functions, Bayes rule, Conditional Independence.**Logic:**Epistemic logic, Muddy children problem, Inserted material knowledge, Traveller’s dilemma, Propositional logic, First/Second order logic, Model logic, Logical inference**Graphs:**Graph representation, Graph coloring, Graph isomorphism,**Finite automata:**Deterministic finite automata, Nondeterministic Finite Automata**Regular expressions:**Basic concepts, Inverse homomorphism**Computability:**Turing machine, Halting problem, Rice Theorem, Cook’s Theorem

- You can write the homework either in English or in Chinese (both are accepted)
- Submit your homework to Mr. Ma Rong in class or drop it to Telecom Building 3-335 (电信群楼 3-335) during 6:30pm – 8:00 pm. (Also, you can send the electronical version via email to your TA directly.)
- Late submission is not accepted.

- Please click Homework01.pdf to download your homework.
- Latex source file Homework01.tex (the same as Homework01.pdf, just for convenience)
- Pay attention to your handwriting. Your credits are based on not only the correct answers but also a neat, clean, and well-organized writing style.
- Correction: the last question in 6(e) should be (i×j)mod

- Please click Homework02.pdf to download your homework.
- Latex source file Homework02.tex (the same as Homework02.pdf, just for convenience)
- There are three optional questions in this homework without submission requirement.

- Please click Homework03.pdf to download your homework.
- Latex source file Homework03.tex (the same as Homework03.pdf, just for convenience)
- The problems will be graded on penmanship, clarity, and style of your solution.

- Please click Homework04.pdf to download your homework.
- Latex source file Homework04.tex (the same as Homework04.pdf, just for convenience)

- Please click Homework05.pdf to download your homework.
- Latex source file Homework05.tex (the same as Homework05.pdf, just for convenience)
- There is an optional question in this homework without submission requirement.

- Please click Homework06.pdf to download your homework.
- Latex source file Homework06.tex (the same as Homework06.pdf, just for convenience)
- Note: The due day of this assignment is the same as the previous one (HW5).

- Please click Homework07.pdf to download your homework.
- Latex source file Homework07.tex (the same as Homework07.pdf, just for convenience)
- There is an optional question in this homework without submission requirement.

- Please click Homework08.pdf to download your homework.
- Latex source file Homework08.tex (the same as Homework08.pdf, just for convenience)

- Please click Homework09.pdf to download your homework.
- Latex source file Homework09.tex (the same as Homework09.pdf, just for convenience)
- Note: You have an extra day to finish this homework :)

- Please click Homework10.pdf to download your homework.
- Latex source file Homework10.tex (the same as Homework10.pdf, just for convenience)
- Note: The due day of this assignment is the same as HW9.

- Please click Homework11.pdf to download your homework.
- Latex source file Homework11.tex (the same as Homework11.pdf, just for convenience)

- Please click Homework12.pdf to download your homework.
- Latex source file Homework12.tex (the same as Homework12.pdf, just for convenience)

- Please click Homework13.pdf to download your homework.
- Latex source file Homework13.tex (the same as Homework13.pdf, just for convenience)
- Note: This is the last homework of this class~~~~Yeah! \
*^o^*//

- Discrete Mathematics and Its Applications (Sixth Edition), by Kenneth H. Rosen, published by The McGraw-Hill Companies, Inc., 2007.
- Discrete Algorithmic Mathematics (Third Edition), by Stephen B. Maurer and Anthony Ralston, published by A K Peters/CRC Press, 2004.

- How to Solve It: A New Aspect of Mathematical Method, by G. Polya, published by Princeton University Press, 2004.
- One Two Three . . . Infinity: Facts and Speculations of Science, by George Gamow, published by Dover Publications, 1988.

Graph Theory Problems and Solutions, http://www.geometer.org/mathcircles/graphprobs.pdf

Suppose that we are interested in identifying communities in online social networks. A Tutorial on Spectral Clustering: http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf

See June Andrew email in CS2800 of 11/20/2011 for good web site at U. of W. \newline First order: http://faculty.washington.edu/smcohen/120/Chapter10.pdf Second order: http://faculty.washington.edu/smcohen/120/SecondOrder.pdf