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.