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 Parallel Algorithms: Prefix Sum Application On Graph

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 Stanford Technologies Ventures Program

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 What Really Happens When We Visit a Web Page