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!”.
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
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.
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.
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.
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