Class#1: Intro to Discrete Mathematics

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.

(more...)

Python 101: Intro to Python

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).
(more...)

Fisher-Yates shuffle in python

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.

My python final [simple database analysis]

My python final project was to write a simple database analysis based on any given data. I thought about it and I decided to have the entire class use the same sets of data. I created a Google form and let them fill them out. I sent out the result in csv and a few other formats, which really made the whole programming easier.

Python has a very nice module called csv. It is already included in 2.6.4 so there is no need to find it. All we need to do is to import it. After a few days fighting with this program, I finally had finished my project.

Here each student is an object. This program is not very complicated. It is very portable. We can control each column at any instance. It is not the best, but good enough to earn an A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
import csv
class Student(object):
    sports = []
    ftopics = []
    stopics = []
    genders = []
    movieyrs = []
    countrys = []
    def __init__(self,row):
        # we set up the row from the csv data
       self.lname, self.fname, self.ID, self.gender, self.sport, self.movie, self.movieyr, self.country, self.ftopic, self.stopic = row
        # we import each column into our pre-defined lists
       self.sports.append(self.sport)
       self.ftopics.append(self.ftopic)
       self.stopics.append(self.stopic)
       self.genders.append(self.gender)
       self.movieyrs.append(self.movieyr)
       self.countrys.append(self.country)
        # functions to print results anytime we want
    def print_information(self):
       return (self.lname, self.fname, self.ID, self.gender)
    def print_first(self):
       return (self.lname, self.fname, self.sport)
    def print_second(self):
        return (self.lname, self.fname, self.movie, self.movieyr)
    def print_third(self):
        return (self.lname, self.fname, self.country)
    def print_fourth(self):
        return (self.lname, self.fname, self.ftopic, self.stopic)

#########################   THIS IS OUR WELCOME MENU    #########################
#
#               Welcome to CSC 1000 (Fall 2009) - Final Project
#
#
#                           Author: John Yeukhon Wong
#                           E-mail: gokoproject@gmail.com
#
#       Select one of the following to retrieve speific database analysis
#
#           [0]: Basic Information (Last name, first name, ID, gender)
#           [1]: My Favorite Sport (Last name, first name, favorite sport)
#           [2]: My Favorite Movie (Last name, first name, movie title, movie year)
#           [3]: My Favorite Country to Visit (Last name, first name, country name)
#           [4]: My Favorite class topic (Last name, first name, first preference, second preference)
#
#
#           Each item has its own speific analysis result
#           A while = True loop to re-request a new analysis
#           Enter QUIT to leave this program
#
#########################   THIS IS OUR WELCOME MENU    #########################  


# let us initalize some stuff we will use throughout
# we use csv.reader module here to read csv data
choice_list = []
choice_dict = {}

# assuming our csv data in the same path as the python directory
reader = csv.reader(open('new_mondy_csc_data_revise.csv'), delimiter=',', quotechar='"')
header = tuple(reader.next()) # make sure our reading in tuple form

students = list(map(Student, reader)) # read all remaining lines
num_students = len(students) # get the total numbers of students in this survey

def search_function(x):
    if x == 0:
        print "%-17s|%-10s|%-6s|%s" %header[:4] # running header from column 0 to 3
        print "-" * 45
        for student in students:
            print "%-17s|%-10s|%-6s|%3s" % student.print_information()
        print '\n'
    # gender
        for s in set(Student.genders): # class attribute
            print s,":", Student.genders.count(s),"student(s)", "or",round(((float(Student.genders.count(s)) / num_students) *100),1),"%"

    if x == 1: # Basic information
        print '\n' * 2
        print "Students' Sport Preference"
        print '\n'
        print "%-17s|%-10s|%s" %(header[0],header[1],header[4])
        print "-" * 45
        for student in students:
            print "%-17s|%-10s|%s" %student.print_first()
        print '\n'
        # Printing all sports that are specified by students
        for s in set(Student.sports): # class attribute
            print s,":", Student.sports.count(s),"student(s)", "or", round(((float(Student.sports.count(s)) / num_students) *100),1),"%"

        # Printing sports that are not picked
        allsports = ['Basketball','Football','Other','Baseball','Handball','Soccer','Volleyball','I do not like sport']
        for s in set(allsports) - set(Student.sports):
            print s,":", "---", '0%'
        print '\n'
        # Here we list sports most favorite and least favorite
        choice_list = Student.sports
        for choice in choice_list:
            choice_dict[choice] = choice_dict.get(choice, 0) + 1
        print "The MOST favoritable sport is: ", max(choice_dict)
        print "The LEAST favoritable sport is: ", min(choice_dict)
       
    elif x == 2: # My favorite movie
        print "%-17s|%-10s|%-16s|%s" %(header[0],header[1],header[5],header[6])
        print "-" * 45
       
        for student in students:
            print "%-17s|%-10s|%-16s|%s" % student.print_second()
        print '\n'
        # number of old / new movie
        newyear = ['2001','2002','2003','2004','2005','2006','2007','2008','2009']
        counter = 0
        freq = {}
        for i in Student.movieyrs:
            if i not in newyear:
                freq[i] = freq.get(i, 0) + 1
                counter = counter + 1
        print "Numbers of students' favorite movies are OLDER than 2001: ", counter
        print "Numbers of students' favorite movies are NEWER than 2001: ", (num_students - counter)
        print '\n'
    elif x == 3: # My favorite country to visit
        print "%-17s|%-10s|%s" %(header[0],header[1],header[7])
        print "-" * 45
        for student in students:
            print "%-17s|%-10s|%s" %student.print_third()
        print '\n'
        for s in set(Student.countrys):
           print s,":", Student.countrys.count(s),"student(s)", "or", round(((float(Student.countrys.count(s)) / num_students) *100),1),"%"

        choice_list = Student.countrys
        choice_dict = {}
        for choice in set(Student.countrys):
            choice_dict[choice] = choice_dict.get(choice, 0) + 1
        print "The TOP country wanted to visit is: ", max(choice_dict)
       
    elif x == 4: # First and Second class topic preference
        print "%-17s|%-10s|%-15s|%s" %(header[0],header[1],header[8],header[9])
        print "-" * 45
        for student in students:
            print "%-17s|%-10s|%-16s|%s" % student.print_fourth()
        print '\n'
       
        # first topic preference
        print "My first most preferred class topic"
        print "-"*20
        for s in set(Student.ftopics): # class attribute
            print s,":", Student.ftopics.count(s),"student(s)", "or", round(((float(Student.ftopics.count(s)) / num_students) *100),1),"%"

        alltopics = ['Matrices','Probability','Object Oriented Programming','Matlab','Python']
        for s in set(alltopics) - set(Student.ftopics):
            print s, 0, '0%'
           
        choice_list = Student.ftopics
        choice_dict = {}
        for choice in choice_list:
            choice_dict[choice] = choice_dict.get(choice, 0) + 1
        print "The TOP class topic is: ", max(choice_dict)
        print "The LEAST wanted class topic as first preference: ", min(choice_dict)
        print '\n'
       
        print "My second most preferred class topic"
        print "-"*20
        # second topic preference
        for s in set(Student.stopics): # class attribute
            print s,":", Student.stopics.count(s),"student(s)", "or", round(((float(Student.stopics.count(s)) / num_students) *100),1),"%"
        for s in set(alltopics) - set(Student.stopics):
            print s, "---", '0%'
           
        choice_list = Student.stopics
        choice_dict = {}
        for choice in choice_list:
            choice_dict[choice] = choice_dict.get(choice, 0) + 1
        print "Second most TOP class topic is: ", max(choice_dict)
        print "The LEAST wanted class topic of all: ", min(choice_dict)

# Let us bring our menu interface, or instruction to the front

print """
#########################   THIS IS OUR WELCOME MENU    #########################
#
#               Welcome to CSC 1000 (Fall 2009) - Final Project
#
#
#                           Author: John Yeukhon Wong
#                           E-mail: gokoproject@gmail.com
#
#       Select one of the following to retrieve speific database analysis
#
#           [0]: Basic Information (Last name, first name, ID, gender)
#           [1]: My Favorite Sport (Last name, first name, favorite sport)
#           [2]: My Favorite Movie (Last name, first name, movie title, movie year)
#           [3]: My Favorite Country to Visit (Last name, first name, country name)
#           [4]: My Favorite class topic (Last name, first name, first preference, second preference)
#
#
#           Each item has its own speific analysis result
#           A while = True loop to re-request a new analysis
#           Enter QUIT to leave this program
#
#########################   THIS IS OUR WELCOME MENU    #########################
"""

while True:
    x = raw_input("Enter a number to print specific table, or enter QUIT to leave: ")
    print '\n'
    if x == 'QUIT':
        print "Thank you for using our service!"
        break
    search_function(int(x))
    print '\n'

(more...)

First Python program from csc 1000

The speaker today gave us a classwork and I did it using modules.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import datetime
import time
m = datetime.datetime.now()
k = datetime.date.today()
b = k.isoweekday()
b = time.strftime("%A")
mm = m.month
yy = m.year
dd = m.day
ds = datetime.date(yy,mm,dd)
hh = m.hour
mi = m.minute
ts = datetime.time(hh,mi)
print "It is now",ts.strftime("%H:%M:%p"),b,ds.strftime("%m/%d/%Y")

(more...)

First python lecture in csc1000

I didn't have time to write any blog due to heavy college work load. I apologized.
Last week we had our first guest lecture on Python. I enjoyed it because I liked my csc 1000 class. It was fun to do programming.

Here is the lecture presentation:
http://bitrocket.com/csc100/new_notes_1.html

Anyway, python is very different from many conventional languages. It emphasizes on reducing the size of the core and fewer syntax. But keep in mind that usually applications in Python aren't as powerful as those written in C and C++, for example. It is very expensive to write a web application in C because it is very powerful and time consuming. Python is therefore a great candidate. Google uses Python because, it's cheaper. The cost of adding servers is less than the cost of writing the application in C and C++ mainly.

This statement is not entirely true and is very subjective in some aspects. But the overall context, we should agree that Python is consider a powerful programming language.
(more...)

working on matrices 3x3 in Matlab (2)

So after a few days of working on the matrices and its mathematical operations, theories and conceptional components (especially with matlab), I found a useful way to quickly determine whether a system is, either unique solution, no solution, or infinite solution.

First of all, I think I have thought too much about matrices and constructing a program. The objective, after spending a few days indeed, is probably just to find out "what number will produce" each of the three conditions. However, number goes on forever. But if we set a range for alpha and beta (the two variables we use) in the program, then there is a purpose for the program.

Matlab, just like any other programming language, has its own library, a collection of operations and pre-defined source-codes to use through the MatLab. For matrices, we do not need to worry about the operations. I probably had thought too much about "writing a program". I can still develop one, it isn't that hard once you know matrices' operations.

I can also make the program without doing the loop, simply just a program with the following sets of statements, and return a message to tell which condition is produce.

Now, the tools to determine each conditions quickly is to use the rule of "rank".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
>> alpha = 3, beta = 4, A=[(alpha) 2 0;0 1 2; 0 0 0], b=[(beta);0;1], rref(A), X=A\b, rref([A b]), rank(A), rank([A b])

alpha =

     3


beta =

     4


A =

     3     2     0
     0     1     2
     0     0     0


b =

     4
     0
     1


ans =

    1.0000         0   -1.3333
         0    1.0000    2.0000
         0         0         0

Warning: Matrix is singular to working precision.

X =

   NaN
  -Inf
   Inf


ans =

    1.0000         0   -1.3333         0
         0    1.0000    2.0000         0
         0         0         0    1.0000


ans =

     2


ans =

     3

if rank(A) = rank([A b]) = u.s and infinite solution may exit
else
no solution exit

if rank(A) = # of unknowns, u.s exit
else
infinite solution exit.

If these statements are valid and true, then the first half of the program is just to create a loop and set a range to alpha and beta. The computer will print out the pair of alpha and beta when (1) there is no solution and (2) infinite solution. For unique solution, there is no need to print out the alpha and beta. Clear enough?

working on matrices 3x3 in Matlab (1)

Okay, let's cut this short.

So far so good just need references to guide me through to crack down the concepts.

For Matrices, according to the alternative theorem,there should be 3 cases
1. Det =/ 0 and it's has unique solution
2. Det = 0, no solution
3. infinite solution

What I don't get is how do you determine something is infinite solution. To construct a program in Matlab isn't that difficult. All it takes is time to learn the ways to program in Matlab., The problem is the set of rules to determine the value of Alpha and Beta (input) and matrices (calculations). We can simply use det = or =/ 0 to determine something is either case 1 or case 2.

Well .... it seems something is working here.
when the last two numbers in the last rows are the same and the alpha and the first number in the last row are the same, it produces 0 det and infinite solution and also if we make the last row completely empty with zero, also infinite solution.
I guess I need to go through the references and see what I can do with it.

My first thought on Matlab

I will probably give another thought later when I get used to Matlab. As far as my study with the common programming languages, like Perl and C++, I do see a big difference in Matlab. This is more a mathematical language than what we usually expect from a programming language. However, people use Matlab for engineering projects because of the capacity of the mathematics offers by Matlab.

I don't know. I am the kind of person that needs real introduction to every language, from the most basic "Hello-World" script to the most advance (you write whatever you want!!!). I have to spend sometime finding a good book covering Matlab. There are some helpful sources online but the technical references they use, someone strike me down.

At the moment I am dealing with Matrices. Matrices aren't that difficult to understand, it's just math. But my pre-calc class was two years ago. I didn't remember any matrices operation at all. I probably need extra time to get use to the way Matlab writes program and how it works with numbers and command.

Here is the matrices

1
v=[1, 2, 3, 4], b=[4;5;6;7], v*b

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
v =

1     2     3     4

b =

4
5
6
7

ans =

60

Removing 99 99 Group files/directories from your host

Ok, this is a frequent problem to everyone. When a program [a script], for example, Wordpress or Drupal, created a file / directory, the permission and group assigned is usually 99 99 Group. It's a known issue. If someone wants to remove a file or a directory with 99 99 Group permission, then only the host support has the permission to do so.

To send a ticket, depends on the kind of host provider you have, usually take a day to complete. I don't like waiting for someone to solve my problem. I did the request a couple times with my host supporter. The very last time I requested to delete the directory, I didn't specificity it enough and he deleted the wrong directory [my old blog directory].It wasn't his fault but it took a few days for me to actually work on the recovery.

I like to do things as quickly as possible if I get a chance. So I decided to search for a script or something to help me to break through this 99 99 Group limitation. Here is the solution I used:

http://drupal.org/node/231401
There the author provided 3 scripts:

[1] Change the permission to 777 in order to delete them [for optional removing !!!!]

1
2
3
4
5
<?php
   $old = umask(0000);
   chmod("name of folder or flile", 0777);
   umask($old);
?>

(more...)

Page 1 of 3123»