HarvardX CS50 - Week 1

Week 1 of HarvardX CS50

CS50 is a first year university course offered by Harvard University and more recently, Yale University, which dives into the basics of computer science, exploring algorithmic thinking and teaching students how to code in a variety of languages including Scratch, C, and Python, amongst others. In the last few weeks of the course, it offers a choice of three tracks - game, web, or mobile development that students can explore and create their final project which is encouraged to be something which is useful beyond the course.

The online course which is known as CS50x offers a stripped down experience of the real course. The assignments, known as problem sets (or psets), are marked against certain criteria and a number of test cases by an automated program. All of your coursework is pushed into individual branches of your own CS50 GitHub repository. I’ve copied these branches into a single repository for ease of perusal, which can be found here.

Week 1

Week 1 was a definite ramp up in difficulty as we have now moved on from Scratch to implementing real programs in C. CS50 provides a really awesome Linux sandbox in order for you to do all your assignments, with the instructions and hints on the left and terminal and text editor on the right. Most of the lecture this week related to explaining how the blocks in Scratch related to the equivalent syntax in C as well as a brief explanation of data typing.

I’ve never really coded in C before, so I struggled a bit with the language as I’m used to modern languages like Python and JavaScript which let you be more flexible with types and which actually have string types built in properly! Thankfully, CS50 offers a custom library which makes it easy to take user input without having to verify that what the user is entering is actually of that data type, as well as other helper functions like implementing a string type.

The first exercise in the problem set was another simple Hello, World in order to ease students into writing code in C and giving them a good parallel to the Scratch programs. The student then needs to alter the code to take input of the user’s name in order for the program to print out “Hello, ”. Not the world’s most interesting problem but a good introduction all the same.

The second exercise in the set contained two variants - one for those more comfortable with coding and one for those less confident. The exercise required you to take user input between 1 and 8 and dynamically create what looked like a set of stairs using the hash symbol (#). The twist was that although this is really quite easy to do with the straight edge left aligned, the exercise calls for the student to create one that is right aligned. A lot harder. I managed to get a left aligned one quite easily using a pair of nested for loops however I was stumped for a while on how to get them right aligned. I ended up enlisting the help of my partner, who had written C before, who told me that I could do this using some printf magic to create a certain number of spaces before an output.

Mario exercise - Less comfortable edition

Once I’d solved this, I decided to take the more comfortable edition of the exercise, which involves taking the above, adding two spaces and then mirroring the stairs - so a left aligned set. Easy, I’d already done one of those! Since the gap between the two sets of stairs was always going to be two spaces, I simply hardcoded those two spaces in the for loop for each line of output. Both of these exercises passed muster with 100%.

Mario exercise - More comfortable edition

Next I took on the cash exercise, which uses what’s known as a greedy algorithm to find the minimum number of coins that need to be given to make up a certain amount of change. This used US denominations of coins, which is a good thing, because it would’ve been somewhat harder in Australian dollars where the smallest denomination is a 5 cent coin, not 1 cent. Anyway, a greedy algorithm tries to take the biggest chunk out of the problem each time it’s run.

I probably could’ve solved this problem with a series of if statements inside a loop however I hate this as an approach, so I went with an array that I looped over each time to check if the amount we were subtracting was still greater than each element of that array, before adding to the total number of coins and breaking out of the loop. Took me a while to figure out I needed to break out but I got there in the end.

The final exercise in the set was, in my opinion, by far the hardest. Using a strongly typed language like C made this so much harder for me. The exercise required us to implement Luhn’s Algorithm to validate credit card numbers. As explained in the Wikipedia article, this involves taking every second digit, multiplying by 2, adding them up and then adding them to the remaining interleaved digits. Turns out this is really quite hard to do on a plain integer and because C doesn’t implement duck typing, this meant I needed to cast types around.

My partner helped me out quite a bit with this one, walking through it with me step by step to help me think about what I was doing analytically and although she thought of another, better solution to the problem, I implemented one that I understood fully. In addition to validating the credit card number, the program will categorise and output whether it is a MasterCard, VISA, AMEX or invalid card based on the first two digits.

Output from the credit exercise

This week challenged me and introduced me to the quirks of a language I’d never used before. I’m excited and a little nervous to see what Week 2 holds in store and how CS50 will break my brain next!

comments powered by Disqus
Built with Hugo
Theme Stack designed by Jimmy