Feb. 15, 2017
Welcome back to part 2 of my review of Harvardx’s CS50x. If you read part 1, you’ll know I left off at week 3 of the course — right where things got interesting. The first couple weeks lured me in with easy problem sets, and in PSET 3 the difficulty really started to ramp up. We’ll see today that weeks 4–7 didn’t exactly let up.
Week 4: Doing Real Stuff
Week 4 (and a bit of Week 3 that I left out last time) covered how to write to and read from files, how to use While and Do While loops, and a little bit about how some common file types are structured. .BMPs and .JPGs got special attention in particular as they were the focus of this week’s PSET.
For PSET3 (I left ouf part of it last time), I also had to implement a version of the “Game of Fifteen” that ran in a text terminal. The only catch was it had to be of user-defined height and width (up to 9 x 9). This was the first time where I felt like I had met the problem set’s requirements, but the automated grader wasn’t giving me a 100%. I may not have mentioned this before, but each of the assignments was graded by automated unit tests rather than an actual person. I guess it’s a little much to expect a real human to look through thousands of internet students’ homework for free.
Anyway, the way the program has to work (per the specs) is that there has to be a grid of size 9 x 9 where only the user-defined n x n spaces are visible. Seems complicated, but that’s what they wanted. I filled all of the hidden spaces on the grid with the number 82, because I knew I’d never need it since 9 * 9 is 81. Apparently all the blank spaces had to be the number 0, hence me not getting a 100% the first time I ran the tests. This would not be the last time I had this type of problem.
PSET4 was all about .BMPs and .JPGs. To make a long story short, the first thing I had to write was a program that would resize a .BMP file by a whole-number value; i.e. if the user gave the number two, I had to make it twice as big. If the user gave me the number 3 it had to be three times as big, and so on. The second part was unscrambling an image that looked like one of those secret message games with the red plastic decoder. The final exercise in PSET4 was to extract .JPGs from a block of memory that simulated a corrupt SD card. For this I had to scan for .JPG headers and write each block of memory I found into a new file so it could be viewed.
A Pause for Ethics
It’s tough to talk about the solutions to the above problems without violating the class’s honor code policy. Even though I’m not a real Harvard student, I have noticed that in all of the forums, subreddits, and message boards, people generally stuck to the policy. I feel like working through these problems without spoilers available really made sure I learned the material I was supposed to. In that spirit I'm going to keep this review spoiler-free. ON WITH THE REVIEW!
Week 5: Data and Stuff
This is the week I personally feel like I got the most out of this course. The focus for Week 5 was building data structures, searching through them, sorting them, and then clearing them from memory. This is a big topic, and describing each data structure used is beyond the scope of this blog. Here are some links to types of structures covered in the class instead:
All of these came in handy in PSET5: Speller. The goal was to write a spell-checker. Given a .txt file containing approximately 145,000 words, I had to check other .txt files for spelling. The assignment was graded on how fast the program could correctly spell-check texts like War and Peace. This assignment was especially fun because I got to compare my solution against the CS50 staff's solution for speed. This incentivized me to try solutions based on different data structures for comparison. If that doesn't sound fun, this isn’t the PSET for you.
Weeks 6 and 7: The Fake Out
The first thing I had to write was a function that would parse an HTTP request (given as a char*) and return the different parts in different formats depending on the type of request. If you (the reader) came here from reddit or StackExchange and are looking for spoiler-free hints, you should look into switches and the <string.h> library. If you still need help feel free to send an email.
The second function in the PSET was to take the name of a file (again given as a string), find its suffix, and return a directory address for the folder that contains that type of file. <Str.h> to the rescue again. The third was to parse a url and ensure that it was valid. If invalid, I had to return the proper error code. More switches; More <str.h>.
At this point I must confess that this isn’t the assigned order, I just tackled the easiest parts of the problem first.
WARNING: DENSE PARAGRAPH AHEAD.
The final thing I had to write for this assignment was a function that loaded a file into memory and returned a pointer to that block of memory. This doesn’t sound that difficult, but the arguments the function had to take were crazy. I HAD to accept (per the PSET specs) a file pointer (FILE*), a pointer to an unsigned value (size_t*) and a pointer to a pointer to a custom data type of BYTE (a BYTE**), and place the contents of the file into the block of memory at the final address of that double pointer.
DENSE PARAGRAPH OVER
If the paragraph above looks like garbled nonsense to you, don’t worry. It took about 8 hours of reading extra-curricular source material, looking for code examples, and feverishly studying the source code for clues for me to gain what understanding I have now. To put this in perspective, 8 hours is longer than I spent on the entire previous PSET. I still didn’t pass the unit test 100% because my function failed to read two rapid consecutive requests and failed to correctly deliver .php files. This was the only PSET I turned in without getting a 100%.
PSET6’s Fatal Flaw
After finishing the rest of the course, my failure to get a 100% on PSET6 still haunted me. I dug back into research and stumbled upon the fact that .php files (and any other files containing programs or scripts) need to be served as strings. With the help of CTRL+F I looked through all of the instances of str or char*. In the header of a file that was 1000 lines long, stuck among the defines, includes, and function declarations, was the following line of code:
typedef char BYTE;
That line of code defines a BYTE as having all of the same properties as a char (character). In C a char* is different than other types of pointers. Most pointers are just a way of naming an address in memory so you can read from and write to its location. Achar* is a string (C doesn’t have built-in strings) and gets read from start to finish automatically. The computer knows it’s reached the end of a string when it gets to the character \0, or the null character.
Since a BYTE had been defined as a char*, that meant that a BYTE** was acting as a pointer to a block of memory that was getting read as a string. I didn't know that, and I didn't add the \0 to the end.
After this, I crawled into the next phase of the course mentally worn out and defeated. Read all about it in Part 3!