Extra TA office hours

Tue afternoon: All tutors
Wed morning: Hackson
Wed afternoon: All tutors
Thu afternoon: Jesse

The location is in SHB 117.

Marked homework 3

Homework 3 is marked. You can take it back from SHB 117 after 2pm of Dec 8.

supplementary exercises

Supplementary exercises for homework 4 are posted.

homework 4

Homework 4 is posted. The deadline is on Dec 9 at 5pm sharp. You will need to submit the assignments to a bin outside SHB 924. No late submission is accepted. We will post the solutions right after the deadline.

lecture 20

Graph coloring is perhaps the most famous graph problem, thanks to the map coloring problem and the 4-color theorem. We first discuss the basic definition and show that a graph is 2-colorable if and only if it is bipartite. Then we briefly mention some applications of graph coloring, and coloring of an interval graphs. Finally we study the map coloring problem and prove that every planar graph is 6-colorable (and then quickly sketch the proof for 5-coloring). The proof is based on a sequence of simple statements, each of which is not difficult to understand but putting it together is not easy. This is the final lecture of this course.

lecture 19

We have introduced two matching problems, the stable matching and the bipartite matching problem. Both are useful problems in practice, and matching is a central problem in graph theory. The proof of the Hall's theorem is not covered in class and is optional.

supplementary exercise 3

The supplementary exercises are posted. There are some "programming" exercises available.

lecture 18

We started our discussions on graphs, and prove Euler's theorem, the first non-trivial result in graph theory. On the way we have also introduced some basic definitions in graph theory, e.g. degree sequence, isomorphism, path, cycle, etc.

lecture 17 - second half

We spent some time studying the recursive solution to the Tower of Hanoi problem. This is a key problem in understanding recursion, which will be a very useful technique in writing program. Then we show how to compute a closed form formula for some recursion. We show the steps to compute the solution, but did not go into the details of the proofs of why this method works. This method is easy to use, and for those who are interested in the proofs, all the details are provided in the textbook. This is the last lecture on counting. Once again let me emphasize that recursion is an important topic that we should know.

lecture 17 - first half

We have gone through the first half of lecture 17 about recursion. The first half is about setting up the recurrence relations, and the second half is about solving them. Today we have stopped at the last but a very important example - the Tower of Hanoi. We will continue our discussion on this example next Monday, and now is a good time for you to think about this problem. Recursion is only useful in mathematics, but also very useful in computer programming. Once you have understood the idea of recursion, you will be a much better programmer!

lecture 16

We discussed how the concept of a bijection between two sets can be applied to counting. This is a very useful idea in counting more complicated objects, perhaps we will see one such example later in this course.

extra supplementary exercises for homework 1

Some student asked for more exercises (and solutions) for proof by induction. Thanks to Leo. Some extra supplementary exercises are solutions are posted under homework 1. You are encouraged to solve these problems, and compare your solutions to Leo's solutions.

homework 3

Homework 3 is posted. The difficulty is similar to that of homework 2. So it would be better to start early. Today we have covered lecture 16. So you should be able to solve up to 3(a) by now, actually 3(b) is also doable by now (we will derive a recursive formula for the matching parenthesis problem in lecture 17, but it is not essential in solving 3(b)). The deadline is Nov 23 in class. Feel free to leave comments and questions.

project

The project is due next Monday on Nov 16. You just need to hand in the report. There is no need to prepare the presentation.

midterm

Today we have returned the marked midterms. (If you have not picked it up, please do so in tomorrow's tutorial or the TA office hours.)

The average is 47.5 and the median is 45, while the highest is 100. It seems that the results are not quite satisfactory. We have discussed about the difficulty of this course, and the objective of this course, and I won't repeat here.

As discussed in the class, the remaining 65% of this course will mostly depend on the second half of this course (e.g. at least 70% of the final exam will be starting from lecture 12). I will try to cut off some more difficult topics, and spend more time in explaining. There are many things you can do to do better in the second half.

1. Buy the textbook. Read it as suggested by the course homepage. Do the exercises inside; there are solutions for half of the exercises. No matter how hard I try to made the slides self-contained and put as much details as possible. Slides are NOT a substitute for the textbook. (Only very few students bought the textbook. Why do you suddenly think that textbooks are not important? As a student I bought most of the textbooks.)
   
2. More practice. There is no other way to learn mathematics. You need to try to solve problems and make mistakes. Only then you can gain the experience to solving problems. It is impossible to learn mathematics by just listening. The TAs are putting much effort in coming up with relevant supplementary exercises and providing solutions. You should spend more time in solving these problems and the problems in the textbook.
3. Come to classes and tutorials. Ask questions in classes. Some responses like "I do not understand what you just said", "could you repeat?" are much appreciated.
4. No talking in class. I will ask the students who talk to leave the classroom. Many students have complained that they could not focus because of the noise in classroom. Please be considerate to others.
5. Ask questions outside class. We do care about you, and are willing to offer help. My office hour is in every Tuesday 10am-5pm. You could come and I will try to answer every question of you. The TAs also have office hours on Friday. And, of course, you can always come and ask questions after classes and tutorials. Also, you can discuss the lectures (e.g. if you don't understand some slides, if you find typos, etc) and the homework in the course blog and newsgroup. We will try to reply as soon as possible.
   

I hope the quick return of the midterms will give you some extra time to do well in the second half. I also hope you could be more active in learning.

lecture 15

We covered the basic definitions of functions and discussed the pigeonhole principle. Slides 20-26 will not be covered in this course...

lecture 14

We explained the inclusion-exclusion formula (for 2 sets, 3 sets, to n sets) and showed some applications. The last part on Euler function will be skipped in this course (although I just added it in this year...).

homework 2 updated

The statement of question 4(a) is modified for clarification.

supplementary exercises 2

The supplementary exercises for homework 2 are posted.

lecture 12-13

We have introduced some very basic set theory and some simple counting techniques. Next week will be more interesting.

solutions for homework 1 and supplementary exercises

Solutions for homework 1 and supplementary exercises are posted. (The hard problems in the supplementary exercises are just for fun and no solutions are provided.) No late submissions are accepted now. Please start to review the material for midterm as soon as possible. If you have any questions please come to ask me during my office hours (today 10am-5pm).

homework 2

Homework is posted and the due date is on Oct 30 (5pm sharp). You are advised to start early. Please comment if you have any questions.

midterm

Midterm will be on Nov 2 (in class).

lecture 10-11

We have covered the Chinese remainder theorem and the applications of number theory to cryptography. It illustrates how (not-so-difficult) mathematics can be very useful in computer science. These are the more interesting but more difficult part of this topic. Feel free to comment if you have any questions.

homework 1

Homework 1 and the supplementary exercises are posted. Please feel free to ask questions.

lecture 9-10

We have covered some basic number theory, from greatest common divisor to modular arithmetic to Fermat's little theorem and Wilson's theorem. Note that number theory is a topic that was not covered in high school mathematics, and so everyone has the same background. It is quite fascinating that we have derived some profound statements just from the basic concepts such as greatest common divisor. Please free feel to leave comments if you have any questions about this topic.

lecture 8

Today we have shown the (inductive) proofs of two useful inequalities, the Cauchy-Schwarz inequality and the AM-GM inequality. We have also discussed the intuition and some applications of the inequalities.

new office hours

Since some students have conflicts with my office hours and possibly there will be no 2 hours that will fit every student's schedule, I will extend my office hours to Tuesday 10am-5pm in SHB 911. Please come to ask questions. I would be happy to explain anything starting from lecture 1. You can also come to discuss about your course project.

lecture 7

Today we go over some basic skills in analyzing sums and products of number sequences. There are some differentiation and integration techniques used in this lecture. For those of you who have not learnt calculus before, don't worry about it since these will not be asked in homeworks and exams. But I would like to show these because this is a general principle in deriving closed form formulas and/or to approximate the sums and products. Feel free to leave questions and comments.

Lecture 1-6

We covered the topic on logic and proof in lecture 1-6. Please feel free to have questions and comments.