What is the duty of a computer science student?
If you ask the system, it would say "the duty of a computer science student is, of course, to study computer science."
GPT3, a language artificial intelligence model, would agree. If you ask it the same question, it would reply, "the duty of a computer science student is to study the science of computers. This includes the hardware, software, and networks that make up a computer system."
Even a human like Arthur would say the same thing, perhaps adding that "a computer science student should learn to solve problems using computers."
Yes, to study computer science was the core duty of a computer science student.
"So why on earth have you taken a month and a half to even start learning computer science?" asked the system.
Lexus looked up from the current book that he was reading, "Introduction to Algorithms".
He was sitting in his usual seat at the library - tucked away in a corner, at the end of the long wooden table. This didn't mean that there wasn't anyone nearby though. From the corner of his eye, Lexus could count at least three others sat comfortably within hearing distance. All of them were staring at their laptop screens, and one or two of the even had their headphones on, but Lexus didn't want to take the risk of someone overhearing and so decided not to reply to the system's remark.
Verbally, that is. He simply stuck his tongue out, then continued with his work as if nothing had happened.
To Lexus, learning mathematics first seemed like the obvious choice. After reading his first book, "How to think like a mathematician", and discovering that the book he read determined the type of experience point he obtained, he decided to level up as quickly as possible by focusing his efforts on a single subject. Min-maxing is the way to go, he thought.
Now that he had exhausted all of the mathematics textbooks on the quest list the system gave him, he could refocus on learning computer science.
He was finally in his zone, like a fish that had to struggle on the edge of the beach to finally roll itself back into the water. It felt great to be learning things he was truly interested in.
"Introduction to Algorithms" was a book that he owned, unlike any of the previous books where he had to borrow them from the library. He had previously bought the book while in high school, but the looming threat of exams and university admissions meant that he never really had the time to sit down and read through the book in peace and quiet.
Now that he had this opportunity, he wasn't going to let anyone disturb him from reading this book, not even the system.
Poor timing for the system to start bugging him again. "Cat got your tongue?" The system sounded very proud of itself for learning how to use idioms.
"Shhhh, be quiet," Lexus whispered. "This is a library."
The system snorted. "You're the only one that can hear me."
"Yeah, but you're not the only one that can hear me."
"Then you can just keep quiet and listen to me talk," the system replied.
Why was Lexus even wasting his time trying to talk sense into the system? He shook his head and forced himself to focus, determined to completely ignore external distractions, which happened to include a voice inside his brain.
=====
"I knew you would be here." Arthur walked up to the table where Lexus was and sat down at the adjacent seat.
Lexus looked up from his work, and smiled. "Heya."
"Playing favourites, much?" the system muttered. Lexus ignored it.
Arthur leaned over and glanced at the textbook that Lexus was studying. "Ooh, CLRS. The crème de la crème of CS textbooks."
"Why, have you read it?" Lexus asked.
"I've skimmed a few chapters here and there, but not cover to cover. It doesn't really help much for competitive programming. Too much math, proofs and niche algorithms that aren't that helpful," Arthur replied.
Arthur loved competitive programming. He joined all of the programming competitions in high school, being a Codeforces grandmaster and IOI silver medalist. It was his go-to hobby, and he spent pretty much every waking minute doing it. Lexus was always astonished at the persistence and vigour with which Arthur pursued competitive programming, and admired him for it.
Lexus, on the other hand, never really delved deep into competitive programming. He had tried it out a couple of times, but never really saw the point and so gave up early. To Lexus, he enjoyed learning about the algorithms and the proofs behind them, but training for competitive programming felt a bit too much like practicing for an exam and not learning for the sake of learning. At the end of the day, Lexus didn't find much enjoyment in competitive programming, so there was no point training for it.
"Looks like a good book for me then," Lexus said.
Arthur chuckled. "Yeah, sounds like something you'll like."
Arthur settled down into the seat next to Lexus, pulled out his laptop and soon started typing away, presumably at one of his coding projects. Lexus also returned to reading "Introduction to Algorithms", and the atmosphere returned to silence.
=====
Lexus was taking an algorithms course this term, so much of the initial chapters of the book wasn't new to him. However, he made sure to learn the content thoroughly, completing all of the exercises and reading through each sentence carefully.
He knew that this wasn't the best way to earn as much experience as possible in the shortest amount of time, but he didn't care. Lexus was enjoying the process of thinking through the exercises, coming up with code, and proving that his algorithms were correct.
This tale has been unlawfully lifted from Royal Road; report any instances of this story if found elsewhere.
Consider the searching problem:
Input: A sequence of n numbers A =
Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.
Write code for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct.
It was a simple question meant to teach the principles of loop invariants, but Lexus completed it anyways. It served as good revision for the course, and it wouldn't take up a lot of time, so why not?
Lexus took out his laptop, and typed:
int LinearSearch(vector
for (int i=0; i if (A[i] == v) { return i; } } return NIL; } Loop invariant: at the start of each iteration of the for loop, the first i elements of the array A do not contain v. 1. Initialisation: at the start of the first loop, i=0. The first 0 elements of the array A, trivially, do not contain v. 2. Maintenance: If the next element is equal to v, then the termination condition is reached, at which point there is no next iteration. If the ith element is not equal to v, and we have shown that the first i-1 elements do not contain v, then before the next iteration the first i elements do not contain v, and the loop invariant still holds. 3. Termination: The loop terminates when the element at position i (i+1 when counting from 1) is equal to v or when i = A.size = n. The loop invariant states that the previous elements are all not equal to v, so the index output would be the index of the first element for which the value is equal to v. --- Computer Science EXP +1 --- The occasional experience point was nice, too. ===== The next day, Lexus headed alone to the ground floor study area, where Professor Emerson liked to have his supervisions. Arthur had a rowing competition that day and couldn't attend the supervision. Apparently that was the reason he went to find Lexus in the library, but then promptly forgot when he saw the book that Lexus was reading. Lexus waited for a few minutes for Professor Emerson to show up, and explained the reason for Arthur's absence. "Ah, no worries. I had something to talk to you about anyways," the professor said. Confused, Lexus waited for the professor to elaborate. Did he forget to do a problem sheet again? But that couldn't have been the case, he made sure to do the problem sheet each week after his previous ordeal. He didn't want to relive the experience of having to rush a problem sheet in a single afternoon having missed a lecture. "Lexus, you've made good improvement over the past few months," Professor Emerson said. Before Lexus could even open his mouth to answer, a cynical voice rang in his head. "Of course, if reading the whole of 'Discrete Mathematics', 'Mathematics for Computer Science' and 'A First Course in Probability' would't help I don't know what would." Even though he knew that the system couldn't hear him, Lexus mentally shouted a "shut up" before answering politely, "I've been reading a few books here and there, which helped a lot during my studies. And the problem sheets are still quite challenging for me, so they're very helpful." Lexus paused. The professor wasn't accusing him of cheating, was he? Sensing the change in Lexus' facial expression, the professor gave a small smile. "Relax. I know you've been working very hard, and it's good that your hard work paid off." He handed Lexus the marked problem sheet that Lexus had submitted for that week. "And it's not like you're getting everything right on these either, so there's still room for improvement." After Lexus obtained the Mathematics Level 1 feature [Right or Wrong], the number of careless mistakes in his work had decreased to essentially 0. He didn't want to seem too suspicious, so he decided to keep a few of his original mistakes in the work while gradually reducing the number of minor errors in each week's problem sheet. Was being too good also a sin? On the other hand, the feature did nothing to help Lexus when he got stuck on a question. For those, he relied on Professor Emerson to guide and teach him through it. One such question was this one: For a set A, prove that there is no injection P(A) → A. "For this question, there's an intermediate step where you have to prove a proposition involving an injection and a surjection," Professor Emerson explained. "If there is an injective function f:A → B, can you prove that there is a surjective function g:B → A"? Lexus paused and thought it through for a while. If an injective function exists then f(x)=f(y) implies x = y. So every element in B corresponds to exactly one element in A and vice versa. For a surjective function, for every y, there exists an x such that g(x) = y. So for every element in A, there exists an element in B for which the function g maps the element in B to the element in A. Wait. He just had to define a surjective function g which satisfies the conditions. Lexus picked up his pen, and started writing. Define g as follows: g(b) = f-1(b) when b ∈ Rf and g(b) = a when b ∉ Rf where a is some element in A and b is any element in B. Then g is a surjective function, therefore the proposition is true. "Good," said the professor. "What does this proposition then tell you about the relationship between A and P(A)?" Lexus looked back at the question, trying to reverse engineer his way to the solution. The question was asking him to prove that there is no injection from P(A) to A, so by the proposition that he just proved, it would mean that he would need to show that there was no surjection from A to P(A). Which, now that he thought about it, he always knew from Cantor's Theorem. Ding! --- Mathematics EXP +1 --- Lexus wrote down his thought process, but this time in reverse order so that it made sense logically. Going from Cantor's Theorem, proving the proposition, then showing that an injection did not exist, as if it did, it would contradict Cantor's Theorem. Lexus noted the tiny little screen that only he could see: --- Correct --- Proof complete.