As the days passed by, Lexus slowly worked through the chapters of "Introduction to Algorithms", learning interesting concepts like randomised algorithms, quick sort, hash tables, minimum spanning trees and much more. Each chapter felt like a whole new world to explore, full of mysteries and perplexities.
Lexus was having fun treasure hunting in the forest of knowledge: finding rare items, equipping new tools, fighting strong monsters and eventually leaving the forest stronger than before. He went in wearing nothing more than beginner armour, his hand holding a shoddy dagger, and walked out with a bulletproof Kevlar vest over his chest and an assault rifle strapped on his back.
Oh, except the fact that trying to understand something was bloody hard. Lexus had to grit his teeth and grapple with each and every mathematical monster, going through the book line by line, searching up the things he didn't understand. When that didn't work, he would try to program the concept using C++.
C++ wasn't the programming language he was the most familiar with. Like everyone else, he started off his programming journey with Python, known for its resemblance to natural language. But he had wanted to learn C++ for a long time, and now was as good a time as any.
Ding!
---
Computer Science EXP +1
---
And he discovered that he would earn more experience points, even though it increased his pain ever so slightly.
By slightly, he meant a lot.
He was too ashamed to ever admit it to anyone, but he spent over an hour just trying to get the merge sort code to work. Was it the vector initialisation in line 20 that was the problem? Or did he pass in the wrong parameters to the MergeSort() method? By the end, he had over ten print statements littered all over his code in an attempt to catch the error. And he did catch it eventually - it was an off-by-one error.
As the famous saying goes, "There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors."
Frustrated, Lexus leaned back on his chair. When he looked up, he could see the multitude of books that filled his shelf. A few were textbooks that he had borrowed from the library, but there were also books that he had brought with him to university. Popular science books about physics, maths and computer science, as well as biographies about famous scientists like Alan Turing and Albert Einstein.
With all their intelligence, did they ever experience the feeling of being stuck and stupid?
“Feeling stuck?” said the voice in his head.
“Hey system, am I an idiot?” Lexus asked into the empty room.
The system snorted. “You’re only realising that now?”
“Tch.” Lexus suddenly felt more determined, if only to prove the system wrong. He was going to make it big!
In order to get through the thousand-page book without going insane, he needed a change of strategy.
It was time to use his “phone-a-friend” lifeline. Except he didn’t have to literally phone them, since that friend was right down the corridor.
So Lexus got up from his chair and walked over to Arthur's room. Knock. Knock knock.
"Come in," a voice called.
Lexus pushed open the door. The first thing he noticed was the sound of chants, beats and hype music that originated from somewhere to his left. He looked over to see Arthur reclined on his study chair with his attention fully focused on his switch, fighting a Pokémon gym battle.
Without even looking up to acknowledge Lexus' presence, Arthur spoke.
"Hold on, Duraludon's the last Pokémon I have to beat," Arthur said.
Lexus walked over and leaned against the corner of Arthur’s table. "How did you know it was me?"
Arthur replied, "Who else would come knocking at my door at this time of the day? Do you even know what time it is?"
Lexus took a moment to ponder before coming to the conclusion that no, he didn't know what time it was.
"What time is it?" Lexus asked hesitantly.
Arthur stopped. He placed his switch down on the desk, picked up his phone and shoved the screen in Lexus' face. "Look. Look at this."
A glaring "00:39" appeared before Lexus' eyes.
The first thought that came to his mind wasn't oh no it's so late I should apologise, but instead it was, "Oh, it's not as bad as I expected!"
The moment those words came out of his mouth, Lexus knew that he had made a mistake.
"I'm sorry," he quickly added.
Too little too late.
"Well, my night is officially taken up by Pokémon, so you can come and find me tomorrow morning," Arthur said. "Unless it's urgent?"
"No, it's fine," Lexus replied. He had wanted to ask Arthur some questions about a few of the algorithms he had come across in the book, but it could wait. Disturbing Arthur while he was gaming was typically not a good idea, and this rule was doubly true past midnight.
Lexus shut the door as carefully as he could and scampered back to his room, only now noticing how eerily quiet the corridor was.
=====
Lexus woke up at 8am in the morning, but opted to wait another two hours before heading over to Arthur's room. Arthur was most definitely not an early bird, and 10am was just about the earliest acceptable time if there wasn't a 9am lecture that morning.
Just as he expected, Arthur had just woken up.
"You're always so freaking early," Arthur grumbled.
Lexus watched as Arthur climbed out of bed and started getting ready.
If you come across this story on Amazon, be aware that it has been stolen from Royal Road. Please report it.
"I've already had breakfast, a morning run and spent an hour doing the breadth-first-search tick," he said.
Finding the later chapters of "Introduction to Algorithms" too strenuous to do right after waking up, Lexus chose instead to do something he did know how to do: the optional programming exercise set for his Algorithms 2 course.
"Why am I even wasting my time trying to reason with this machine?" Arthur mumbled.
=====
Arthur sat down on his study chair and swivelled it to face Lexus, who sat down on a stool he grabbed from the other side of the room.
"So, what's the question that you wanted to ask me last night?" Arthur asked.
"How did you kn- never mind," Lexus said. "I don't really understand the concept of strongly connected components and the algorithm to find them."
Lexus could tell that Arthur was interested the moment the words "strongly connected components" was said.
"Oh! Kosaraju's algorithm. It's a good one, this one," Arthur said as he leaned over to the other side of the table in order to grab a sheet of paper and a pen. "I've used it in multiple competitions."
Lexus watched as he started writing on the piece of paper.
"So let's say we have a di-graph," Arthur said as he drew a couple of circles on the page and randomly added arrows from one circle to another.
original [https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Felizabeth%2F6UByMC-pb8.drawio.png?alt=media&token=4a4243a8-3e9b-48b2-92c4-5fbbf1e6fd4f]
"Then a strongly connected component is one where every node is reachable from another node - like for example if we have this triangle over here in the middle, you can go from any one of these three nodes to any other node while following the arrows," Arthur explained.
circled [https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Felizabeth%2Fcrb5IKico9.png?alt=media&token=590f3a4b-f21f-4cac-a5ea-c9d95e958303]
Lexus nodded and said, "So if you want to get from node number 1 to node number 3 in the directed graph, you can just go through node 2. But 4 isn’t in the same strongly connected component as 1, because you can get from 4 to 1 but you can’t get from 1 to 4."
"Exactly," Arthur replied. "Then Kosaraju's algorithm makes use of the fact that the transpose graph of any di-graph, basically a graph with all the arrows pointing the other way, have the same strongly connected components as the original graph. If I draw the transpose graph of the one we already have-"
transpose [https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Felizabeth%2FlYIvbsAAj3.png?alt=media&token=e9df10dd-3b78-4cb3-b424-c8d6667cf1e2]
"- the triangle of nodes in the middle are still strongly connected, and so we can find the strongly connected components by exploiting this property."
Lexus made a note to himself to attempt to prove that statement when he got back. It was pretty intuitive, but could he prove it from first principles? Before he could get any further along that line of thinking, Arthur's voice brought his focus back to reality.
"The procedure for Kosaraju's algorithm is: first, you perform a depth-first-search of the entire graph, storing the nodes in the order for which they run out of output edges in a stack, then you transpose the graph, then you do another depth-first-search for every node by popping the stack."
"Wh-what." Lexus said. He had no idea what was going on.
Arthur paused, as if to think, and Lexus looked at Arthur incredulously. Did this guy just think he would listen to that and go "Oh that makes total sense, I get it now"?
To be fair, he'd done that before in Professor Emerson's supervision.
Arthur contemplated for a while more before he said, "I've always just used the algorithm without thinking too much about it... maybe it's better if I just show it to you."
And so Arthur led Lexus through the procedure for Kosaraju's algorithm step by step, showing him which elements would be added to the stack in which order. By observing the algorithm as it solved the problem, Lexus was able to have a better grasp of what exactly was going on in each step of the way.
1st DFS: 0 → 1 → 2 → 3 then 4 → 5
stack: 3 2 1 0 5 4
2nd round of DFS:
DFS(4) → 4
DFS(5) → 5
DFS(0) → 0
DFS(1) → 1 2 3
Therefore there are 4 strongly connected components: {4}, {5}, {0} and {1, 2, 3}.
---
Computer Science EXP +1
---
As he listened to Arthur's explanation, Lexus was also able to finally figure out why the algorithm worked.
"Oh, I think I get it! The first depth-first-search gives the order of the starting nodes for the second round of depth-first-searches! This makes sure that in the second round, searching from a node would only return the nodes in the same strongly connected component," Lexus said.
---
Computer Science EXP +2
---
"Yeah okay, I guess that kind of makes sense," Arthur replied. Lexus could tell that Arthur didn't really care about the reason why the algorithm worked, it was enough for him to know that it did what it was meant to do.
But to Lexus, there was a huge difference between knowing and understanding. It was akin to knowing how to drive a car versus knowing how to build a car, the latter was vastly more interesting than the former.
Hmmm. Was that why the system picked him?
Lexus didn't know, and he probably wouldn't until much later. For now, all he had to do was focus on learning, gaining experience points, and levelling up. With the help of the system, Lexus was sure that he would be able to go very far in his academics. All it took was some effort, and a little bit of time.
Maybe, just maybe, one day he would be mentioned in textbooks and classrooms, just like many of the great scientists he admired?
Nah. The likes of Isaac Newton and Alan Turing couldn’t be reached just by having a system. But he was curious to see just how far he could go.
=====
For the next month or so, Lexus focused primarily on reading through "Introduction to Algorithms". He had also started "Algorithm Design" in parallel, reading the chapters relating to the same concept. It gave him a new perspective on the same topic, allowing him to form a better understanding of the algorithms involved.
It was also simply much more efficient.
Lexus would ask Arthur about problems he had with implementing the algorithms, but when it came to the mathematics behind them, Arthur wasn't able to help, so Lexus eventually turned to Professor Emerson for guidance.
Having specialised in theoretical computer science, Professor Emerson had extensive knowledge about many of the algorithms covered in the book, including the mathematics behind it. Initially, Lexus’ questions were limited to the few minutes at the end of every supervision, but eventually the questions piled up so much that the professor set up another weekly meeting with Lexus just so Lexus could ask all his questions at once. The meetings were so enlightening that Lexus gained at least 5 experience points each and every time.
Granted, his head felt like it was about to explode from all the new things that he learnt, but that was a small price to pay.
By the time he had completed the two books, Lexus had accumulated so much experience that he was already close to a level up.
"System, can you show me my status?" Lexus asked.
---
Name: Lexus Kagan
Current Quest: Background Knowledge [8/10]
Computer Science: Level 0 [EXP 94/100 (94%)]
Mathematics: Level 1 [EXP 115/1000 (11%)]
Physics: Level 0 [EXP 0/100 (0%)]
Engineering: Level 0 [EXP 0/100 (0%)]
Chemistry: Level 0 [EXP 0/100 (0%)]
Biology: Level 0 [EXP 0/100 (0%)]
---
Yes, 6 points to go!
"Introduction to Algorithms" and "Algorithm Design" brought him 64 experience points - more than 3 mathematics textbooks combined. It might have been due to the sheer length of the books, but it also probably had to do with how invested he was in the learning process, and how much he actually took out of the words he read.
If he was honest, most of the experience probably came from the weekly meetings with Professor Emerson. It just went to show how much of a difference a good teacher could make. Damn, he should have started asking questions earlier!