Welcome to Part 4 of The Harvard CS50x Adventures, where I talk about my experiences taking the CS50’s Introduction To Computer Science course on edX. In this post, I will show you what I learn as a complete programming beginner.
In Part 3 of The Harvard CS50x Adventures, I learned about arrays. The topics were understandable and straightforward. The problems hardly took any time. This week, however, was completely different. In fact, I took more than a week to figure out the final problem of Problem Set 3.
Algorithms are tough. I definitely need to practice working with them a lot more. Let’s get more detailed.
Searching And Sorting
This week was all about algorithms based around searching and sorting. We learned two algorithms used to search, and four algorithms used to sort.
These algorithms were all based on our knowledge of arrays. We were focused on learning how to sort and search through arrays. Here are all the algorithms we learned.
- Linear Search
- Binary Search
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
I won’t go too much into how each algorithm works in this blog post.
Efficiency And Nice Code Design
Along with algorithms, we learned about efficiency and code design, specifically regarding recursion. Each algorithm has its efficiency score, which we notate as Big O and Omega for worst and best-case scenarios, respectively.
Big O is how many steps your program will take to find the solution in the worst-case scenario. The steps are represented by the slopes of various lines on graphs. For example, in the worst-case scenario for an algorithm like linear search, we can describe as a Big O of n, where n is the size of the array.
Recall that linear search is an algorithm where the program will search an array one variable at a time until it finds the item you’re looking for. Thus, in the worst-case scenario, the application needs to examine everything in the array, and Big O will equal the number of elements in the array.
The best-case scenario, or Omega, for linear search will be 1. In the best case, this algorithm will find what you’re looking for at the first index, and the program will end.
Most computer scientists will focus on Big O. After all, the best-case scenario can occur infrequently, so it would be better to prepare for what would happen in the worst case.
In Part 3 of the CS50x Adventures, I talked a little about how I could have coded some things more efficiently. As you’ve read, this week we touched on algorithm speed, but we also talked about recursion.
Recursion is where a function calls on itself to execute. First, you need a base case where your program will finish if the conditions match the base case scenario.
The CS50 Short about recursion helped me understand the concept of recursion much better.
Doug Lloyd from the CS50 Short explained recursion with a factorial function. In math, a factorial of any number is the product of all whole numbers from 1 to n where n is the number.
For example, the factorial of 4 is 4 x 3 x 2 x 1. The factorial of 3 is 3 x 2 x 1. The factorial of 2 is 2 x 1. And the factorial of 1 is just 1.
If you were to write a recursive factorial function, you would start with a base case checking if your input is 1. If the input is 1, then your function would return 1 because the factorial of 1 is 1. Otherwise, it will continue to run asking for n times the factorial of n – 1 calling on itself.
As an example, if your input was 3, the function will call on itself asking for the factorial of 2. When it calls on itself for the factorial of 2, it will call for the factorial of 1. And since the factorial of 1 is 1, it will return 1 so that the factorial of 2 can do 2 times 1. Now that the factorial of 2 has an value, it will then return that value to the factorial of 3.
It sounds a little complicated, but it is quite interesting.
How Do I Implement These Algorithms?
One of my biggest problems after watching the lecture was, how do I implement these algorithms?
With the exception of linear search, they did not have any real code in their examples. Only pseudocode was shown, and I often didn’t understand how to implement certain elements of the pseudocode.
For example, there was pseudocode that involved the words “swap.” I didn’t understand how I would actually implement a swapping mechanism in C until I searched it up and got a bit of an idea. Once I found out about creating new temporary arrays to allow for swaps, it made things a lot easier.
However, I did not tie up all loose ends. Learning how to swap things allowed me to work with bubble sort and insertion sort, but I still don’t understand how to work with merge sort.
How do you just merge two arrays together? I will need to clean that up.
Luckily, you can do all of the problems in Problem Set 3 without merge sort, but it sucks because I know merge sort is one of the more efficient algorithms and I won’t be able to use it.
CS50 Tideman, The Hardest Problem Ever
The first two problems in problem set 3 were fairly straightforward. Tideman, the third problem, was the most difficult programming assignment I have ever experienced.
I had to break my rule of not looking at someone else’s code. I couldn’t figure out how to lock any of the cycles in the problem. I had no idea how to solve the problem.
I was searching all over the Discord chat looking for any hints for the problem. I didn’t get it. All I learned was that Tideman was the hardest problem in all of the CS50 course.
It took me weeks to try and solve this problem. In the end, I had to look at someone else’s code to get an understanding of what’s really happening. Most people used recursion to build the lock cycles function. That’s a hint I’ll give you.
Admittedly, because of Tideman, I went on a small hiatus. I wasn’t getting anywhere and lost all my momentum. But it’s time I started to rebuild momentum.
Get ready for Part 5 of the CS50x Adventures as I jump into Week 4 of the CS50 course. If you haven’t read Part 3 of the CS50x Adventures, make sure you check it out. If you have any questions or comments as well, don’t hesitate to leave them down below. Have a great day!