Here is the final assessment paper for your reference.

In Question 1, we explore a taxonomy of in-game actions and try to discover why some actions are more sensitive to delay and consistency, while some are not. Here, we introduce two new notions, precision and deadline, or an action. In Part (a) and (b), you are asked to give two examples, one for high-precision, loose-deadline (HP-LD) action, and the other for low-precision, tight-deadline (LP-TD) action. Most of you got these questions correct. My favorite example for LP-TD: player is on-fire and need to jump into the river.

Next, you are asked to explain the relationship between precision and tolerable response time, and between deadline and tolerable response time. Many of you answered that there is no relationship between precision needed for the action and the tolerable response time. In fact, the higher the precision needed, the lower the tolerable response time is. Case in point: have you tried clicking on a few target pixels on screen when your mouse cursor movement is delayed after you move the mouse? It is really annoying. Most of you got the relationship between deadline and tolerable response time correct though (loose deadline means higher tolerable response time).

Finally, in Question 1, you are asked to explain what type of actions is good for short-circuiting, which reduces response time and increases inconsistency. About half got this correct: LP-TD. Since low precision is needed, inconsistency is tolerated, but low response time is good for tight-deadline action.

For Question 2, if you understand the question and DDM, the first two parts are giveaways. S_L will never overlap with U_R, and S_R will never overlap with U_L. On the other hand, S_LR will always overlap with U_LR.

Next, you are asked to sketch a recursive algorithm. The idea is basically, to call split() on S and U to partition the input into six partitions. The pairs in S_LR will always overlap with U_LR. For the rest, we recursively call DDM on the following pairs: S_L and (U_L union U_LR), S_R and (U_R union U_LR), and S_LR and (U_L union U_R). There is no need to consider those that never overlaps. Some of you got partial credits because you only recusrively call DDM on S_L and U_L, and S_R and U_R.

Now, for Question 3, Part (a) is mostly a give away: delayed ack is implemented in the receiver only; fast retransmission and exponential backoff on the sender only; and redundant data bundle needs to be implemented on both sides (since receiver needs to make sense of the bundled data from the sender). Part (b) is also quite straightforward. If the NIC sleeps for too long, it could cause the connection to idle for more than RTO, and the connections’ congestion window resets. If it sleeps even longer, the TCP connection might time out and three way handshake is needed to reestablish the connection. Either way, the connection restarts from slow-start phase again.

Question 4 receives several answers that do not use virtual network coordinates and got 0. For the rest, as long as you explain how players can establish its network virtual coordinate (by obtaining a few landmarks from the server, measuring RTT to them, then reporting the RTT or coordinate back to the server) and how the server does matchmaking (by clustering the players using distance computed from the coordinate), you get 15.

Finally, Question 5 is the one that stumped most of you. The answer can be summarized in two words: frontier region. If two players have no chance of entering each other AOI, there is no need to exchange position update, and this can be achieved through frontier region.

It is disappointing that many of you answered: if two players are not in each other’s AOI, then there is no need to exchange position update. The problem is that, if two nodes do not know the latest position of each other, how do they know that they are in each other’s AOI or not? A similar answer is that two players are very far apart, then they do not have to exchange position update. But did not explain “how far”, nor did the answers explain how can a node know if the other node is far, without know its latest position!

The other popular answer that received a small partial credit is that, if two players (say, A and B) have a common neighbor (C), then they need not exchange position update, since C can tell A and B when A and B enters each others’ AOI. This is correct but incomplete. If A, B, and C are mutually enclosing neighbor of each other, then by this rule, they would not exchange position update so C would not know A and B’s latest positions!

I am, however, quite delighted that a few of you came up with an unexpected answer that is correct: if A is moving away from the last know position of B, it need not update B (and vice versa). The rational is that if A and B are not in each other AOI’s to begin with, then this movement would never cause A and B to enter each other’s AOI.

I hope you had fun answering the paper, which ties up quite a few disparate ideas together, and learn something new in the process. Cheers.

1. Final examination is now known as final assessment in NUS.
2. The final assessment for CS4344 will be on:
   • Date: 29/04/2015 (Wed)
   • Time: 9:00 AM
   • Venue: SR2
3. There will be 5 long questions, a total of 100 marks.
4. Roughly, you should spend X minutes on questions worth X marks.
5. The final assessment is an open book assessment. You may bring in any analog material that you like.
6. No Javascript coding is required during the final assessment. But you may be asked to sketch one or more algorithms to solve a problem.