This should be the last post about college coursework. However, it was the most important course I took as part of my Computer Science degree at Rice.
The first exposure to algorithms and data structures at Rice was in a course called Advanced Programming. (I would have written a post about how awful that course was, but I’ve already written about a course that was much worse). 90% of that course was doing “team programming”, and the rest was an introduction to data structures and algorithms. One of the reasons I did so poorly in that course was the “team programming” was only 60% of the grade.
I had also not done particularly well in COMP 481 Automata and Formal Languages, which is the mentally most challenging course I ever attempted. I took it once from Hans Boehm, who I mentioned in this post, and dropped it. And then I took it from the late Michael Perlman, and almost failed.
I did much better in the hands-on-keyboard, programming work, than I did in the theory work.
Algorithms is a theory course. An algorithm is a way to solve a problem. They have all kinds of characteristics, and many ways to measure them. A good use of an algorithm can mean the difference between a website handling lots of traffic, or crashing.
I took this course from Dr. Robert Hood. He was great. Friendly, approachable, and understandable. As was typical, I got behind almost immediately, and struggled with the work the first 3 or 4 weeks.
The fourth week, one of our homework problems was a problem called The Stable Marriage Problem. We had to come up with an algorithm to come up with solutions for the problem. (And we did not yet have the Internet to help us.)
I sat in my apartment with TV dinners, lots of Dr. Pepper, and a radio, and spent 2.5 days doing nothing but work on this problem. But I finally had an “aha” moment. I figured out a solution in my mind Sunday around lunch, and spent the rest of the day writing it down and refining it.
When I got to school on Monday, I started talking with some friends. We decided to form a study group. It may seem obvious, but I had not really been part of a study group before, except for the one that formed around a woman I dated when I took Differential Equations.
I really started digging the course. I thoroughly enjoyed the material, and the three of us in our study group kicked butt and took no prisoners.
This should have been my last semester, but I had to withdraw from school the previous semester, so I had one more semester left. However, a lot of my friends were graduating. Rice had a thing whereby graduating senior finals had to be completed a week earlier than the rest of the finals so that final grades could be calculated and diplomas printed. The final for 482 was on the last day of senior finals, and it was my last final, and all of my friends were partying afterwards. I was really motivated to finish the final and get out of there.
I started the final, and breezed through the first 9 questions. 10 and 11 had some meat to them, and some proofs, so they took me a few minutes each. At 1:00 into the 3 hour final, I had one problem left.
Some poor woman turned hers in around this time. She looked like she was about to break down and sob; she evidently had not done well.
I looked at the last problem, and it was a classic “prove this problem is really really hard when there are lots of inputs” problem. The thing is, if you can prove that one of those can be transformed to a different one that you know is already “hard”, you are done. There was a note on the white board though:
“On problem #12, I am willing to give you a hint for a 5 point penalty on the grade for the test.”
I looked outside. It was a beautiful day. I knew that the parties were already starting. I could hear the music blaring out of Radio Free Sid (a high-rise dorm on campus) through the walls. I was done.
I walked up to Dr. Hood, and whispered, “I would like the hint, please?” He looked startled, and said, “Really? Are you sure?” I said, “Please.”
The hint was what known problem to transform it to. That made it easy; about 10 minutes later I turned in the test, and left to party with my friends. The 3-hour final had taken about 1:20.
I went by Dr. Hood’s office a couple of weeks later to pick up the test. I got an 88 out of 100, after the penalty was accessed. Dr. Hood asked me, “So, what on Earth made you ask for the hint? Without the penalty, you made one of the highest five scores on this test out of the entire class. Even with it, you are in the top 10…”
I said, “Dr. Hood, I was done. I was supposed to graduate this semester, and I am somewhat burned out. I wanted out of there, and I figured I had done well enough to absorb the penalty in return for freedom.”
He laughed. He the put his elbows on his desk, put his hands together in a triangle, and said, “So, what are you going to do when you are finished with your bachelor’s?”
“Oh, I’m going into industry.”
“Have you thought about grad school?” He looked thoughtful, and he looked at me like he was appraising me for something.
“You’ve seen my grades. I don’t think anybody would take me.”
He put his hands down, and said, earnestly, “I would take you. You could get your Ph. D. at Rice.”
I was speechless, and almost ready to cry. He continued.
“You showed me what you are able to do this this semester. You started slow, but came on very strong. And, as I said, you made one of the best grades on the final. And I talked with Hans about you; he said you had grown up between the two courses you took from him. We think you could do well. You would have to do well on the GRE. You would have to retake all of the computer science courses you made D’s in. So it would take you a little longer.”
I sat up straighter and looked him in the eye. “Thank you so much for the invitation. This is the nicest thing anybody has said to me about my career here at Rice. I am honored.
“That being said, I have one more semester for my degree. It will be my 11th semester. Spending 3-5 more years at school I think would make me absolutely crazy. And I am hoping to get out of Houston. So I think I am going to have to decline. But, thank you so much.”
“Well, if you change your mind, give me a call.”
He’s not a professor anymore, so I can’t play that card now. Still, it was very nice.
Oh, and as for Algorithms, it is the cornerstone of Computer Science. It is also the basis of all modern interview processes at most big companies, like Amazon, Google, or Facebook. Anybody wanting a good programming position should know this material cold. I am thankful every day at work that I took this course and did well in it.
One thought on “COMP 482 – Algorithms”
Pingback: Gulf Coast Oilfield Equipment – Fall 1987 – Recruited by Tech