FGA's Graph Algorithms Course Blog

(Quiz week 7, sep 29th )  Consider $f''$ and $g$ defined as follows: $f''(x) = x^{-(1/3)}$ $g = 4x^5 + 2x^3 + 5 + 3x$ Then, considering derivation, which option bellow is correct: $f'''(x) = -(1/3)x^{-(3/4)}$ and $g'(x) = 20x^4 + 6x - 3$ $f'''(x) = -(1/3)x^{-(3/2)}$ and $g'(x) = 20x^4 + 6x^2 - 3$ $f'(x) = (3/2)x^{2/3}+6$ and $g'(x) = 4x^4 + 2x^2 - 3$ $f'(x) = (3/2)x^{2/3}+3$ and $g'(x) = 20x^4 + 6x^2 - x$ None of the above Original idea by: Fábio Assunção.

(Quiz week 5, sep 15th, Question 1 )  Consider the table took from Barábasi's book, chapter 3 (http://networksciencebook.com/chapter/3#small-worlds): \[ \begin{array}{|c|c|c|c|c|c|} \hline \text{Network} & \text{N} & \text{L} & \text{$\langle k \rangle$} & \text{$\langle d \rangle$} & \text{$d\ max$} & \text{lnN/ln$\langle k \rangle$}\\ \hline Internet & 192,244 & 609,066 & 6.34 & 6.98 & 26 & 6.58\\ \hline WWW & 325,729 & 1,497,134 & 4.60 & 11.27 & 93 & 8.31\\ \hline Power\ Grid & 4,941 & 6,594 & 2.67 & 18.99 & 46 & 8.66\\ \hline Mobile-Phone\ Calls & 36,595 & 91,826 & 2.51 & 11.72 & 39 & 11.42 \\ \hline Email & 57,194 & 103,731 & 1.81 & 5.88 & 18 & 18.4 \\ \hline Science\ Collaboration & 23,133 & 93,437 & 8.08 & 5.35 & 15 & 4.81\\ \hline Actor\ Network & 702,388 & 29,397,908 & 83.71 & 3.9...

(Quiz week 5, sep 15th, Question 2 )  Consider the Yu-Gi-Oh! Trading Card Game. You have monsters that battle each other in order the reduce to 0 the opponent's life points, in short. An example of a monster card, is Subterror Guru, showed in the picture bellow. In the scope of our exercise, monsters have 5 features: attibute, level, type, attack and defense points. Also showed bellow, there is a spell card named Small World. The text of small world is " Reveal 1 monster in your hand, choose 1 monster from your Deck that has exactly 1 of the same Type, Attribute, Level, ATK or DEF, and banish the revealed monster from your hand face-down. Then add, from the Deck to your hand, 1 monster that has exactly 1 of the same Type, Attribute, Level, ATK or DEF as the monster chosen from your Deck, and banish the card chosen from the Deck face-down. You can only activate 1 "Small World" per turn. " In short, Small World card allows the player to search one monster from a...

( Quiz week 4, sep 8th ) Consider the Network defined bellow. Starting from node 0, perform the  BFS Algorithm proceeding in increasing order (labels of the nodes) throught the network. Then, choose which of the queues bellow corresponds to the correct visiting order: ($0$ $\rightarrow$ $1$  $\rightarrow$ $11$ $\rightarrow$ $12$ $\rightarrow$ $8$ $\rightarrow$ $10$ $\rightarrow$ $2$ $\rightarrow$ $7$ $\rightarrow$ $9$ $\rightarrow$ $3$ $\rightarrow$ $4$ $\rightarrow$ $6$ $\rightarrow$ $5$) ($0$ $\rightarrow$ $1$  $\rightarrow$ $11$ $\rightarrow$ $12$ $\rightarrow$ $8$ $\rightarrow$ $10$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $5$ $\rightarrow$ $4$ $\rightarrow$ $6$ $\rightarrow$ $7$ $\rightarrow$ $9$) ($0$ $\rightarrow$ $1$  $\rightarrow$ $12$ $\rightarrow$ $11$ $\rightarrow$ $8$ $\rightarrow$ $10$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $5$ $\rightarrow$ $4$ $\rightarrow$ $6$ $\rightarrow$ $7$ $\rightarrow$ $9$) ($0$ $\rightarrow$ $...

( Quiz week 3, sep 1st ) Consider the Activity Time Diagram defined below. The lines, $a$ to $e$, represent the nodes of the Network. The columns, $1$ to $10$, represent the $starging$ and $ending \ times$ of the nodes during a given  DFS Algorithm running, which starts at node $a$ and follows alphabetical order through the Network. So, the horizontal bar at row $a$, indicates that node $a$ has $starting \ time = 1$ and $end ending \ time = 10$, delimiting the time it is active, and so on for the others. Based on info of the diagram, we are able to infer some of the edges characteristics. Then, considering the definitions about Edge Classification , analyze the following statements: Edges $d$ $\rightarrow$ $c$ and $e$ $\rightarrow$ $d$ are cross-edges. Edges $a$ $\rightarrow$ $c$ and $a$ $\rightarrow$ $e$ are forward-edges. Edge $c$ $\rightarrow$ $a$ is a backward-edge. Given the statements, which of them are true : I and II. I and III. II and III. I, II and...