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.

Nuvation

It’s Velocity Dinner May 29 2014 and the guest speaker is Michael Worry from Nuvation.
When he graduated from uWaterloo in ‘97, he and his cofounders moved to California to do a startup, which led to Nuvation. Today we have him as a guest speaker and he’ll talk about his startup experience. Here are some things I found interesting.

Flinch price

This negotiation strategy focuses on trying to get the most money for the seller. How it works is, as a seller, ideally you want to name a price that is so high that the buyer flinches at the thought of buying it at that price. The buyer needs that product — but at that price, it is painful to think about. Starting a sale like this maximizes the amount you can sell.

Decision made on information

Make decisions based on information. If there are no new information, do not change the decision.
Opinions are not information; but may lead to new information.

Crab bucket mentality

The story goes that if you put one crab in a bucket, it’ll attempt to climb out. But if you have two crabs, when one tries to climb out, the other would pull on its legs and try to prevent it from leaving.
This is analogous to one trying to do a startup — when you want to get somewhere, you’ll have people drag you back. I.e. your parents want the best for you and they want that to be a safe and secure route, which typically is a steady job for steady income.

Fundamentally different skills

Engineers, management, sales are different skills. Those who are good at being engineers may not be good at the others. Michael’s story is that when he initally wanted to scale, he naively promoted his three best engineers to become managers. This was a poor decision in hindsight.

CEO gets the blame

As ceo, when things are going well then my staff gets the credit. When things go poorly, it’s ceo fault.

​