John Wong's Blog

Class#1: Intro to Discrete Mathematics

John Wong — Thu, 11 Feb 2010 03:00:30 +0000

I figure this is a good way to review class note, and I will try to write an entry as frequently as possible.

Discrete mathematics: problems over natural numbers, and natural numbers are anything from zero to infinite positive integers.

Discrete mathematics is relatively a new course in computer science. Fairly a decade or two ago, students have to study all the components of discrete mathematics separately, so there will be a class for graph theory, abstract algebra, number theory and logic.

The followings are the topics will be discovered in today's discrete mathematics course:

1. combinatorial

This is one of the most fundamental studies of computer science, as simple as just counting numbers, or method of counting. It includes permutation, combination and binomial theorem. It may seems elementary but combinatorial applications are extremely difficult.

Let us consider this case. A computer scientist is asked to study and create a new network system for Verizon (a national-wide telephone company), and the figure below is his draft. A challenge is to detect failure of any point. A complex algorithm must be written for this task, and a computer scientist will need to find out how many ways can this failure occur, method of detection, and such.

Sometime, for a computer scientist, it can be a disaster if the method of counting grows at an exponential rate (try to compute 100, you get power of 43). For most real world application, combinatorial results usually generate millions results, it is very important that one knows how to optimize the calculation.

Combinatorial application, can also be as simple as lottery. Choosing 5 numbers from 1-56, and a number from 1-46, will result in C(56,5) x 46 ~=(approx.) 180 million chances (0.18 billion).

With coding theory and computer language theory, "string" is also studied in combinatorial application, which is treated as linear arrangement. For both computer science and computer engineering major students, combinatorial is very important.

2. set, relation and function

Set theory is even more fundamental than method of counting. In fact, a function has a set. Elementarily speaking, {} or set, for example, {1,2,3} is the same as {2,3,1} and {1,3,2}. In combinatorial application, we can find out how many possible ways of the same "set" arrangement. Neglect counting, we see set theory a basic feature of mathematics. In fact, when we carry out combinatorial operations, each arrangement or collection of items are in sets {}.

I haven't touch on set theory yet, but fairly speaking, set theory and relation can be seem as simple as (yet as difficult as) collections, membership and probability. When a software engineer programs a class, he is applying set theory, such as class inheritance and such.

3. number theory
Again, when we are touching computer science, number matters, number rules. A major application of number theory is finding the largest prime, for example. The idea of number theory, asking students to learn what a/b (assume a and b is some integers). The meaning of integers, partitions of integers, meaning of divisions, recursive and linear mathematics will be studied in number theory.

An algorithm can be as simple as just print "hello world" (python), but the theory and mechanics behind it is extremely complicate, which, again touches with only numbers. Knowing the reminder of 1234 to the power of 1234 or (1234^1234 % 5) will take hundreds of years for a super computer to find out.

Another common use of number theory is encryption, for example, banking encryption and online information encryption.
n = -> p * q (or known as P.N.P).
It is extremely difficult to calculate the 2 prime factors from a 3000 bits.

Quantum computing is another story in number theory.

4. graph theory
graph theory is not necessarily the usual graph we see in classroom. A graph can be a set of objects, mathematically speaking, in any shape and form it may takes.

The beginning of graph theory can traced back as early as 18th century, around mid 1700 with Euler. His "Seven Bridges of Königsberg" problem led to the today's graph theory. For years, people are engaged to disapprove Euler, but he is always right. For the problem, you may visit this site: http://www.jcu.edu/math/vignettes/bridges.htm

The question of the seven bridges: "Is it possible to cross bridge once and exactly once"? According to Euler it is impossible.

Another innovation in the 1970s is a problem with "4 colors theorem", or look at here http://en.wikipedia.org/wiki/Four_color_theorem
It solution is well recognized because it is the first computer proof ever in history. The answer to this problem is yes, it is possible to color with only four colors.

The very last application of graph theory would be "optimization and matching". Google and Yahoo search is a known product of graph theory.

5. logic
Although it is elementary in the beginning, its application is just as robust as other discrete mathematics.

6.Applied Algebra
A recent discussion with an electrical engineering student that I had had an important aspects with applied algebra. His senior project is to build a new network system in rings structure.

Linear Algebra is not discussed in discrete mathematics, however, some aspects are discussed in great detail throughout the course.

Cryptography, image processing and detection all come back to discrete mathematics. In fact, again, a computer is just a huge string of numbers.

Discrete mathematics is not a privilege to only computer science students. Real scientists also study this in order to understand their fields.

Numbers, are really powerful.

Google is leaving China

John Wong — Wed, 13 Jan 2010 04:33:24 +0000

Yesterday Google's Corporate Development and Chief Legal officer, David Drummond wrote an entry on his blog, announcing that Google would withdraw its business from China, if the two parties' negotiation fail.

Political censoring has hindered Google from competing against China-native search engine Baidu. Google sounds threatening and this withdrawal may cost both parties billions of dollars of lost. If negotiation fails, Google will probably re-locate its Asia business strategy to Taiwan.

http://googleblog.blogspot.com/2010/01/new-approach-to-china.html

A sticky note for Ubuntu installation

John Wong — Thu, 07 Jan 2010 01:12:55 +0000

gcin

http://cle.linux.org.tw/trac/wiki/GcinDistros

1	im-switch -s gcin

ShowTime theme

1
2
3
4
5

gpg --keyserver hkp://keyserver.ubuntu.com:11371 --recv-key 881574DE && gpg -a --export 881574DE | sudo apt-key add -

sudo gedit /etc/apt/sources.list
deb http://ppa.launchpad.net/bisigi/ppa/ubuntu jaunty main
sudo apt-get install showtime-theme

Emacs, checkGmail

1
2
3

sudo apt-get install emacs
sudo apt-get install checkgmail
checkgmail -update

Python 101: Intro to Python

John Wong — Sun, 03 Jan 2010 02:07:15 +0000

Most tutorials start with installation, and write a simple program called "Hello World", I will follow this tradition just to make sure we cover the basics. Then I will move into control structures and some basic OOP, because almost everything we do in Python is OOPs.

Where to get python?
http://python.org/download/ and get whichever version you want, either 2.6.4 / 3.1.1 (at the time of this writing)

2.6.4 vs 3.1.1, which one?
It gets very technical when one is asked to explain the difference. Here is the shortest and simplest version:

Go with 2.X branch because 3.X branch has a lot of changes, and many existing books, codes and resources are written based on 2.X, so you are better off learning 2.X branch.

If you are very serious about learning Python, you will be happy with 2.X and then learn the differences later.

Write Hello World

Just like any other modern programming language,

1	print "Hello World"

Notice that, unlike C++, Python does not end with semicolon ;

Hack Python Program

As an beginner, you are better off hacking programs, rather than writing the entire program yourself. Once you understand what each line means, then you can write your own program. For example, just change the values or words around.

Unlike complex language like C++, Python is very simple, yet elegant. You do not always need to declare and define types and identifiers.
When we assign a number to any variable, Python knows it is an integer by default. When it is within double quote "", Python knows it is a string.

1 2	abc = 1 cde = "What"

When you need floating point and other numerical types, then, yes, you do need to specify it. So use the option when it is mandatory.

Here is the major difference between the 3.X and 2.X. By default (2.X) if you do 3 divide 5, you get ZERO, whereas in 3.X you get an answer with demicals. If you are using 2.X, you must add one decimal point to any one of the numbers. For 3.X, you are no longer require to declare this extra decimal, because by default 3/5 will print a rounded answer.

1
2
3
4
5
6
7
8
9
10
11

IDLE 2.6.4
>>> 15/2
7
>>> 3/5
0
>>> 3.0 / 5
0.59999999999999998
>>>
>>> 3/5.00
0.59999999999999998
>>>

Another way is to declare it a floating point, and round it up (check doc / google for answer).

Input Method
Before we jump into control structure, we must learn input method.
input("")
raw_input("")

Just remember that raw_input is safer and a better input method than input(). Once we get to list, dictionary and a few other topics, we will see variations like str(input("")), int(input("")) and etc. Basically if we add a type in-front of an input method, we are restricting the information being inputted, processed and outputted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

a = input("Enter a number: ") # a = 1, you get 1
print a
b = input("Enter a word: ") # b = fgdfg, you get error, by default input is integer
print b
c = int(input("Enter a number: ")) # c = 121, you get 121
print c
d = int(input("Enter a word: ")) # d = ere, you get error, self-explanatory
print d
e = raw_input("Enter a number: ") # e = 34, you get 34
print e
f = raw_input("Enter a word: ") # f = fgdfg, you get fgdfg
print f
g = int(raw_input("Enter a number: ")) # g = 343, you get 343
print g
f = int(raw_input("Enter a word: ")) # f = dfdf, you get error, another self-explanatory
print f

Control Structure
There is no need to go in depth with the things I just mentioned above. Here we will briefly discuss the if-else, for and while loop control structure in Python.

One thing to keep in mind: you must be careful with your INDENTATIONS.

IF-ELSE

1
2
3
4
5
6
7

# If-Else
a = int(raw_input("Enter any number: ") # restrict only number can be input

if a == 0: # notice that we use colon : after each operation
print "You won! It is zero"
else: # notice another colon :
print "You lost. It was zero, but you answered",a",try it next time!"

The interesting thing is the second print statement (things in bold)
print "You lost. It was zero, but you answered",a",try it next time!"
If we want to print our variable along with a string, we can just user comma to separate the result.
By default, this comma will automatically make a whitespace.

1
2
3
4

a = 10
print "We know a is equal to",a"." # will print --> We know a is equal to 10.
# if we do add an extra space before the end quotation
print "We know a is equal to ",a"." # will print --> We know a is equal to 10.

Try to hack this program by adding or changing with different variables, strings and numbers.

IF-ELIF-ELSE

1
2
3
4
5
6
7
8
9
10

# if-elif-else program
a = int(raw_input("Enter a number between 0 and 10: "))
if a == 0 or a == 10:
print "It contains a zero!"
elif a >= 1 and a < 5:
print "It is greater than or equal to 1, and less than 5"
elif a >=5 and a < 10:
print "It is greater than or equal to 5, and less than 10"
else:
print "Does not follow rule!"

Python has syntaxes like or, and, not for conditional statements. You will learn them all once you get through the next two lessons.

While loop
Notice the last line print "Hello". I show this so that you see unless the loop is satisfy (stops), the last line will not execute. Moreover, you must remember that Python does not has "end" syntax. So...

BE CAREFUL WITH YOUR INDENTATION.

1
2
3
4
5
6
7
8
9

# while loop program

a = int(input("Enter a number: "))

while a != 0:
print "Try again"
a = int(input("Enter a number: "))

print "Hello"

Here is the result
Enter a number: 1
Try again
Enter a number: 3
Try again
Enter a number: 0
Hello

For loop
Like many languages, by default Python starts counting from ZERO. So range(100) really means from 0 to 99 (there are total of 100 integers).

If you want to print from 1 to 100 (including 100), you can do
for a in range(1, 101, 1) # range(first element, end element, counting method ]1 is forward])

1
2
3
4

# for loop

for a in range(100):
print a

Here is the result

0
1
2
3
4
....
99

New Year 2010!!

John Wong — Fri, 01 Jan 2010 06:09:57 +0000

Welcome 2010 !!!

LOL I am tired of reading "Happy New Year" every year on AIM and Facebook. I do not celebrate New Year eve for a few years already because I am not a kid anymore.

A new decade!!

Yeah, it's 2010, another decade since 2000. So what? Just stay home, like we never had a new year before.

I have a boring life now. I really need some works to do over this break. I have a planned agenda before the break, but I am procrastinating. Oh my god, I need stop it.

Oh, I am reading Rainie Yang's bog recently. Her latest entry 心.煩... is here. Her blog says a lot about her life. I have read a few other artists' blogs before, yet, I find Rainie's one frankest, especially with her emotion state. For numerous times she mentions that she wants to be in love.

I start learning about the true face of Rainie Yang through various sources: drama, blog, news and interviews. At 娛樂百分百, she interpreted her new song "青春鬥" how she felt as being 25 years old. She said only love could keep her young. As an actress, as well as a star, she could not have an open relationship. She has at least five known love affairs and the only one she ever admitted was with 小鬼, whom was her first boyfriend in high school, and whom she thought she would marry with. Nevertheless, her parents' divorce had her lost faith in marriage and love. A week ago she told the reporters that she was still single, but she felt she was "in love" for the past couple months. She was referring to her role in Hi My Sweetheart. She once admitted that she wanted to be in love, but she would not promise because she could not.

Oh well, it is my time to sleep. I wish everyone has a great starting.

I am really bored without Hi My Sweetheart !!!! >3<

Got my room already

John Wong — Thu, 31 Dec 2009 03:23:39 +0000

After a few months of efforts, I finally got a room near school. It is right across the main campus, about 30 seconds away from the gate. I am very happy with it.

As I have mentioned before, I would share this room with a visiting phD Columbia student from Beijing. Nevertheless, the room is large enough to fit two people, enough space to sleep and work. The basic rent is $720 per month, shared by the two of us. Utility is electricity, and is shared among the four of us, probably between $20 - $30. To round up the total cost, $360 + $40, I am expecting $400 per month per person. This is not bad at all.

I will move in mid-Jan, probably around Jan 10 - 15.

I am looking forward with Hi My Sweetheart ep.10. Oh my god.

Anyway, tomorrow is December 31th, but I am going to stay home. It is too cold to join the crowds at Time Square tomorrow night. Oh well. I am still waiting for Ross to review my grade. I can't believe he gives me B+. My final project deserves an A.

Oh today the NYPD had an investigation near Time Squares because of a suspicious white van. By noon they found the van safe, with only clothes and tables. Man, terrorism is really bad-ass. Ruin people's life.

Si-tu-but seems to be ill today. I hope she gets well soon. <3 I love my hamsters.

Hi My Sweetheart (海派甜心)

John Wong — Tue, 29 Dec 2009 06:03:28 +0000

Oh my god. I am in love with this drama. I can't stop thinking about the characters and story. It is a really cute drama fantasy. I even image-cut a scene when she cries to her pink tiger doll, and makes it my AIM default.

Rainie Yang is really cute, and her acting is mature and good in Sweetheart. For the last few years, I refused to watch her drama for some unknown reasons. Nevertheless, I find her a good actress in Sweetheart.

I remembered her from Meteor Garden. I was surprise to find out that she was a former member of 4-In Love at age of 16.

Rainie is now 25, and is getting older. Yet, I find her now more attractive. She has femininity - I just like how she is now. Pure and lovely.

I know she has makeup on, Mike. But in my opinion I think she still retains at least 60% - 70% of her beauty without any makeup. I am serious.

Hi My Sweetheart is hilarious. I laugh to death for every 5 minutes. They make the love scene funny too. I am looking forward with ep 10 next Sunday.

I dream that I will find a girl like Chen Bao Zhu (寶茱姐). She is not rude, just very independent and assertive.

Fisher-Yates shuffle in python

John Wong — Fri, 25 Dec 2009 15:27:44 +0000

As I was writing a simple lottery program for TVBoxNow, I was wondering how module random actually worked. I wanted to write my own random module, but it turned out the mathematical philosophies were beyond my calculus knowledge. It was probability and probably also had to deal with linear algebra.

Great people from Stackflow had provided a lot of insights and useful links. There was a brief overview of what Fisher-Yates shuffle on Wikipedia.
Fisher-Yates shuffle

Mersenne Twister

It turns out that Python's random module implements Fisher-Yates shuffle and Mersenne Twister methods. Not exactly the same, of course, there are changes made for better optimizations and greater unbiased result.

1
2
3
4
5
6
7

# only run this loop from 0 to 19 (20 times)
for player in range(20):
num_player = len(lst_shuffle) # get the total numbers of players
k = random.randrange(num_player)
random.shuffle(lst_shuffle,random.random)
print player, lst_shuffle[k], "random:",k
del lst_shuffle[k]

Additional Reading: The Fisher‐Yates shuffle algorithm

I was wondering why there is an optional random.random() function in the end (I know it's optional). Here was a statement I found from the additional reading:

Pseudo random number generators
Most, if not all programming languages have libraries that include a pseudo-random
number generator. This generator usually returns a random number between 0 and 1 (not
including 1). In a perfect generator all numbers have the same probability of being selected but
in the pseudo generators some numbers have zero probability.

Christmas Eve? Hungry.

John Wong — Fri, 25 Dec 2009 05:53:27 +0000

Yes. Christmas Eve already. Happy Christmas.

Nevertheless, what I really want to do is work. Well, actually, I want to eat first, but my refrigerator is empty.

So I have been looking for a room near City College for two months already. I have visited one, which is only two blocks from City and with utilities I am expecting $550 a month. The landlord is a nice lady, but I really want to minimize my expense.

After spending more than a thousand dollar on Wendy last year, I am really broke. I did have a summer job and it was quite good bonus. Two months ago I decided to save all my money into my bank account, and I have $2200 left.

A Columbia PhD student spoke to me if I would share a room with him, between $600 - $700 a month. The deal is that if we divide it half, each of us will only pay $300 - $400. Although I always hate sharing a bedroom with another person, I guess I just have to learn it since MIT and Cornell only provide shared dormitories.

After speaking to an admission staff at Cornell, since I have course conflict this year, I would have to apply as a junior standing. For MIT, it's worth a try this year, just to get the experience. To get admitted to MIT, one must demonstrate its unique potential contribution to MIT community, and I already have a concrete idea about what I need to do. It's worth that $70 this year and next year again.

Double standard!? phpBB4

John Wong — Wed, 23 Dec 2009 23:18:11 +0000

I am very disappointed with phpBB team. Their team members are so double standard. While their own people proposing feature implementations, and have no problem with those, they would warn users not to jump ahead the schedule.

While there is no specific restriction or vision what they want since the beginning, they police my thoughts and ideas. I am totally sick of their tones and attitude. I was the first one asked people not to draw any tangent, and later they came back to lecture me.

What a shame to these experience software engineers. I am only a freshman in college, and I find myself a better engineer than they are. They tell users their expectations implicitly. They want to discuss archeiture, then please have the developers start the discussion first. Users' engineering experiences do not matter at all. It is about correcting the attitude.

They make users uncomfortable to give in. Users are penalize when their comments offend the developers even if they are facts. They police users' thoughts and ideas. I agree that we need to monitor every reply and to keep our discussions relevant to the subject, however, phpBB team does not let users know their expectations.

"Introducing ideas..."
"Architecture..."

So why wouldn't you people say it all once, make it obvious and state your goals before any user jump in?

They do not want too many inputs at the moment which I also understand very well. However, their attitudes have made users like me leaving the community. I will never returned to phpBB because they are a punch of attitude-problem people. I have a problem with their prejudice on the Chinese and Asian users. In the past some of their team members even made racism remarks.

phpBB4? Please. I am just going to write my own one and make it a commercial (yet, still open source). Goodbye, phpBB. You guys really suck at defining software engineering.