cs50-part-1

27 Apr 2020

Been nearly a week, longer than I thought, but I’ve been keeping steady by working through CS50.

Concepts

It’s been interesting finally getting some exposure to a lot of these topics I’ve been circling around, whether I’m aware of it or not. I’ve said it before, and I’ll say it again, learning Python really spoiled me, especially since I did take a semester course in Java that I’ve managed to completely forget. What I am enjoying about the CS50 course is looking at a lot of the lower level concepts which kind of come for granted in Python.

Week 1 was interesting in that the problem set involved a lot of looping. Both functionally, but also mechanically by literally figuring out a way to mechanically move through the digits of a number without the ability to just literally move digit by digit like I would in Python was frustrating and rewarding.

Week 2’s problem set also involved a simple encryption exercise. However, a subproblem arose in how to confirm that there were no duplicate letters in a shuffled alphabet string. I tried this one method which involved comparing the ASCII values of the shuffled alphabet against a sorted alphabet, recording the differences, and then summing the differences, which should come to 0. The problem arises when say, a user inputs something drastically off. For example, it’s possible to have two duplicates create symmetrical differences that cause the sum of the differences to equal zero. As an edge case, if the user enters all “A”s. The sum of the differences still equals zero so it looks like there’s no duplicates, when in fact there are only duplicates. Trying to solve this problem at a “fancier” level was interesting, and also kind of ultimately pointless. At the end of the day, a solution is better than no solution.

But it did lead me to google possible solutions afterwards, which led to two interesting methods: one involving using the values as pointers. In this case, the key has already translated to ASCII capital values. So subtracting each value by 65 should create a minimum value of zero. And you begin iterating through, treating each value as a pointer to the next value. So if the first value in the array is 14, you go to location 14, and you change it to a negative. Now you go to the second value, and you find where that value is “pointing”. This repeats multiple times, and the trick is that every time, you check and see if the “pointer” leads to a negative value. If it does, there’s been a duplicate equal to that location value.

There was also a fascinating method involving looping through with a “fast” and “slow” pointer, where like above the values act as pointers, but this involves two pointers incrementing by 1 and 2 respectively, and where duplicates are detected whenever the fast and slow pointer are equal. However, it also requires a cycle detection algorithm inside of it to provide a sort of failsafe, I suppose.

Week 3 is what I’ve taken a pause from grappling with today. Very interesting this week to learn some of these sort algorithms. I covered time complexity briefly in one course, and I have to say this wasn’t quite as intricate and detailed as I would’ve liked on the same topic. But it’s a refresher and a seed for more self-learning in this area. Where this week really shined was learning recursion. I saw this and instantly remembered a challenge from Google Foobar which in hindsight was clearly designed solely for testing recursion.

This turned into a longer post in review, but it’s been interesting. Currently trying to navigate through trying to understand some problem syntax, and hopefully the next step is on to doing a Merge Sort implementation.