Category Archives: Academica

The undergraduate blog of academia.

Parallel Algorithms: Prefix Sum Application On Graph

Preparing for advanced algorithms exam (CS450 at EPFL), and I just truly understood a problem. First reaction is: "TIL prefix sum is a stack. So powerful!".


The problem:

You are given a cycle of n vertices with an additional set T of edges between these n vertices (in addition to the n edges that form the cycle). You are to determine whether it is possible to draw the edges of T inside the cycle in such a manner that no two edges cross. Develop a parallel algorithm that runs on O(logn) time and uses linear total work to solve this problem.

Continue reading

A Beautiful Nash Equilibrium

I just re-watched one of my favourite movies again - A Beautiful Mind. Lately I've been reading about artificial intelligence, in particular, multi-agent systems and cooperation methods. (The textbook our class uses is called MultiAgent Systems Wooldridge, 2009.) And of course, agents have some autonomicity and need to work together to cooperate. We can't discuss cooperation without talking about strategies, and consequently, economics. John Forbes Nash influenced a paradigm shift in perspective in how we look at negotiations, through the Nash equilibrium. It states: "Every game in which every player has a finite set of possible strategies has a Nash equilibrium in mixed strategies". By mixed strategies, it means a strategy that allows you to choose between possible choices by introducing randomness into the selection. For example, in rock-paper-scissors, the crucial mixed strategy is to choose between rock, paper, and scissor at random, with equal probability. This strategy is in Nash equilibrium with itself.

I've been feeling unmotivated to work recently, falling behind in all of my courses. Homework wise, I think having partners gave me a (wrong) impression that I can do less work and still make it through the course. I'm very much aware that I'm falling behind, but feel helpless to stop it. It feels like tumbling into the rabbit hole. In my spare time, instead of studying things I'm interested in learning about, I often find myself playing dota. I desperately need to fix this. I'm writing this just after I watched the movie, and I feel so much more motivation now. I can't help but tear up during the pen ceremony, recognition of one's achievements is quite touching.

Artificial Intelligence

Background

Lately I've been fascinated about learning about AI. I've been reading AIMA (aima.cs.berkeley.edu), the entire book from front. I do this for fun, it's very enjoyable. Sometimes friends ask me how I've been and what I've been up to, and they're often surprised to hear that I enjoy reading an textbook. Well this isn't the first textbook, and those that I do read, I love to get a deeper understanding. Some textbooks I loved reading were CLRS,  Operating System Concepts (Silberschatz, et al.), uC++ book on concurrency and parallel programming (Buhr, http://plg.uwaterloo.ca/usystem/pub/uSystem/uC++book.pdf). Currently it's AIMA, and also http://neuralnetworksanddeeplearning.com/chap1.html. They're fascinating stuff.

Thoughts

Oh while on the bed and letting mind wander, I had a thought. Self taught learning is better than following instructional learning. Because self taught is like an informed search in AI whereby you have an idea of what you want to learn about, so in a sense you have a heuristic function.

And although unproven, brain memory is limited. And so to cope with that, we "forget" things over time. This means we need to review things periodically to freshen up, and it's a way of the body deallocating and allocating memory.

Stanford Technologies Ventures Program

 My notes on the 2004 Guy Kawasaki video lectures.

Make meaning in your company

Companies that succeed are those that make meaning. If you set out to make money you probably won’t succeed.

Key motivations to start a great organization:

  • Increase the quality of life
  • Right a wrong
  • Prevent the end of something good

Don’t write a mission statement

Make a mantra - three or four words that capture the essence of your organization.

E.g.
Wendy’s “healthy fast food”
FedeEx “Peace of mind”
Nike “Authentic athletic performance”
Mary Kay “Enriching women’s lives”
Kawasaki “Empowering entrepreneurs”

Dilbert mission statement generator website for mission statements.

Get up and get going

Think different, build the product/service that you love.
The best source of entrepreneurial spirit are people under 30 years old and solving a personal problem.
Think different.

Do not be afraid to polarize people. Ideally some people love your product, some people hate your product.

Find a few soul mates. When one person is down, you need the other person to pick you up and help you. Keep you warm.

The new business model

A specific person. Not “we’ll capture millions of eyeballs”. Not “enterprise software”, but “what size, who, and what they do”.

Keep it simple. We want innovate products/technologies.
Fundamentally, you make something, you sell it, you make money — that’s the model a VC can handle.

Ask women. Men has the “killer gene”. Start company to kill another company. Men are predisposed to want to kill things. Women don’t have this predisposition. Don’t waste your time asking men.

Continue reading

What Really Happens When We Visit a Web Page

What Really Happens When We Visit a Web Page

The journey down the protocol stack for a perspective of the many, many protocols that are involved in a simple request: downloading a web page.

Our setting consists of: a student, Bob, connecting his laptop to his school’s Ethernet switch and downloads a web page (www.google.com).

Getting Started: DHCP, UDP, IP, and Ethernet

Bob boots up his laptop and then connects it to an Ethernet cable connected to the school’s Ethernet switch, which in turn is connected to the school’s router. The school’s router is connected to an ISP, comcast.net. Comcast.net is providing the DNS service for the school; thus, the DNS server resides in the Comcast network rather than the school network. We’ll assume that the DHCP server is running within the router, as is often the case. When Bob first connects his laptop to the network, he can’t do anything (e.g. visit a web page) without an IP address. Thus, the first network-related action taken by Bob’s laptop is to run the DHCP protocol to obtain an IP address, as well as other information, from the local DHCP server:

1. The operating system on Bob’s laptop creates a DHCP request message and puts this message within a UDP segment with destination port 67 (DHCP server) and source port 68 (DHCP client). The UDP segment is then placed within an IP datagram with a broadcast IP destination address (255.255.255.255) and a source IP address of 0.0.0.0, since Bob’s laptop doesn’t yet have an IP address.

2. The IP datagram containing the DHCP request message is then placed within an Ethernet frame. The Ethernet frame has a destination MAC addresses of FF:FF:FF:FF:FF:FF so that the frame will be broadcast to all devices connected to the switch (hopefully including a DHCP server); the frame’s source MAC address is that of Bob’s laptop, 00:16:D3:23:68:8A.
Continue reading

Programming Languages

Low level programs contain a lot of ad hoc, buggy, and slow implementation of higher level languages. Paul Graham described an excellent idea in "Hackers and Painters"

If you solve a hard problem, the question is not whether you will use a powerful enough language, but whether you will (a) use a powerful enough language, (b) write a defacto interpreter for one, or (c) yourself become a human compiler for one."
[...]
For example in the OO world you hear a good deal about "patterns." I wonder if these patterns are not sometimes of case (c), the human compiler, at work."

In short, as developers we like concise, unbloated languages that is sufficient for what we need.

In-list functions

I was reading Peter Norvig's spell correct and discovered python had in-list comprehensions. It's a nice feature which allows you to easily construct a list.


>>> [ x**2 for x in range(1,11) if x % 2 == 0 ]
[0, 4, 16, 36, 64]

It looks very readable. Now, ruby being my favourite language over python, I wanted to see if ruby had a similar feature. The best I can come up with is this:


2.0.0-p247 :017 > (1..10).to_a.map{|x| x**2 if x%2 == 0 }.compact
=> [4, 16, 36, 64, 100]

This isn't as easy to comprehend. For instance, why is it necessary to have .compact?
Why do we need to call .to_a? Python wins in this case. I'm now a lesser fan of ruby and more of python.
Lastly, I checked this out in haskell - which many consider to be a dense language. It's also a language I'm looking to do some coding in.


Prelude> [ x^2 | x [4,16,36,64,100]

Not bad. I'd argue that this is as easy as pythons - provided that you understand haskell syntax. Syntax wise, I suspect python is more wordy than haskell.

Ruby lambda vs. procs

In ruby, lambda and procs are pretty much the same, but not quite. Syntactically, they are similar.


lambda_larger_than_4 = lambda { |num| num if num > 4 }
proc_larger_than_4 = Proc.new { |num| num if num > 4 }
(-1..8).to_a.collect &lambda_larger_than_4
=> [nil, nil, nil, nil, nil, nil, 5, 6, 7, 8]
(-1..8).to_a.collect &proc_larger_than_4
=> [nil, nil, nil, nil, nil, nil, 5, 6, 7, 8]

However, there are two main differences.

    Lambda checks number of arguments passed to it and throws error. Proc ignores unexpected arguments and assigns nil to any missing.
    When lambda returns, control is passed to caller. When proc returns, control does not get passed back to caller.

Interesting Consequences of Undecidability

In the book Introduction to Automata Theory -- Languages and Computation. The following paragraph is interesting:
av

What this means is that if we were given a source code of a program, we would be unable to decide what the program does. Only lexical or syntactical properties of the program may be decided. This is interesting because it's really counter-intuitive! You'd think that given the source code and read through it we can systemically figure out what it does. Not true. This means is that another program, B, cannot figure out what program A does.

Interestingly enough, this implies that no anti-virus will ever be totally effective, or any other types code detection software, because it is undecidable what a program does. There will always exist programs which can't be detected. I knew this when I was young, from the fact that AV programs always update their virus databases, so naturally that meant there was no systemic way to detect mischievous programs. I wondered if the updates would ever stop in the future. Now I know this will never happen because of this consequence of undecidability.