This post is edited from my original blog post. Find it, and other posts by me on kewbish.github.io/blog.

Introduction

This post'll go through weeks 3 and 4 of CS50, and include my notes and comments for both, because I couldn't be bothered to write up two separate posts. I'll go back to one a (CS50)week when we hit Week 5.

Week 3 goes through several common sorting algorithms and Big-O notation, and week 4 goes through memory and files. Both problem sets are slightly unrelated, but that's fine - I learned a ton this week as well. We're in the thick of it now - weeks 3 - 5 are apparently the most difficult in CS50. (And I can finally say... I finished Tideman!)

Skip to my thoughts.

Week 3

Let's start with the usual notes:

• there are many types of search and sort
  • some are more efficient than others
• for example, linear and binary search
  • linear goes through all the elements
  • binary effectively cuts the number of comparisons in half
• linear search
  • go through all elements one by one
  • if it matches target, congrats!
• binary search
  • choose a midpoint
  • if midpoint is the target, return index
  • otherwise, search the left and right halves, depending on the target and the current midpoint
• these two have different O times
  • simple mathematical expressions to return the worst case
• there are also lots of ways to do sorting
  • insertion, bubble, and merge are among a few
  • actually, I coded a bunch of these already on GitHub
• merge sort introduces us to recursion
  • a function calling itself with some arguments
  • make sure there's a base case set, or else it'll infinitely run
  • in merge sort, we check for the size of the array to check
  • more efficient than selection sort, O-wise
• C also allows us to declare custom structs
  • a form of class / object is how I understand it
  • used a lot in problem sets to simplify

Week 3 Problems

Personally, I found the lecture pretty unrelated to the problem set, which was all about voting. This was one week where I kind of regretted my idea to do both less/more comfortable versions of a problem - Runoff and Tideman were both super difficult. This was also the first week we got 'distribution code', or a template that takes care of most of the functions for us.

One thing that was a significant obstacle was the various structs and variables, and how we got the distribution code. I didn't spend much time poring over the given code, and as a result, it was a little difficult to remember the types and purposes of each variable. I kept having to refer to the walkthrough video to remember what each function was supposed to do. Runoff was clearer in this case, providing actual hints. I guess Tideman was supposed to be more difficult, but it would have been nice to have more hints along the way.

Tideman also involves a decent amount of graph theory, or at least knowledge of recursion. Nowhere in the lecture was the graph theory really covered, so I had to do a lot of figuring and drawing algorithms out on my own. It was helpful to draw dummy tables out and go through the algorithm step by step, at least.

Skip to my thoughts.

Week 4

Here are my notes:

• we learn about a new counting system of hexadecimal
  • what's used in colour codes
• - denote hexadecimal with 0x
• what even is the point of pointers?
  • given a variable stored somewhere in memory, it has a pointer
  • pointers give us the address of a variable
  • denoted with *
• the actual address can be found with &
  • represented in hexadecimal as well
  • &var gets the address
• combine with *&var, which goes to the address and gets the value there
• points at first character -> strings
  • CS50 library had abstracted this away, but now we have to use pointers
  • char * s
  • can also access individual characters, which map to the pointer + x
• week 4 also teaches us how to allocate memory
  • malloc -> allocates a space in memory
  • need to define a size that it needs to be allocated
  • can't be changed
• to copy a string, we can use strcpy or malloc and copy it with a loop
  • remember to copy the \0 byte as well, or else things will crash
  • doesn't know where the string ends
• after we allocate memory, we need to remember to free it
  • use the free function to free memory
• if we don't, we're going to end up with a memory leak
  • use valgrind to check for possible leaks
• computer memory is split into several sections
  • one is the code itself
  • another is the global variables
  • the heap is empty, where free memory gets pulled in
  • the stack is used by functions that are currently being called
• once a function is returned
  • is freed from the stack
  • any arguments get lost
• this is also where pointers and addresses come into play
  • by passing addresses into pointer arguments, you can actually change the variable itself
• overflows (like the website)
  • when there isn't enough memory in the heap to satisfy malloc, we get a heap overflow
  • too many functions loaded? stack overflow!
  • called buffer overflows -> might crash system, extremely fun
• can assign a variable just to NULL
  • doesn't point to anything
• with pointers, we can start to manipulate files
  • fopen opens a file with a character pointer (string), and a mode
    • like Python
  • fwrite and fread, well, write and read
  • fread is interesting, it takes the variable, block size, number of blocks to read, and finally the filepath
  • remember to close all files with fclose

Week 4 Problems

This week's problem set was a lot less painful. I guess it's just because week 3 was more focused on algorithms and abstract programs, whereas this week was more hands-on and practical. The distribution code this week was also less related to what we actually had to implement, so was much easier to just skim through.

Having experience with Python's file operations definitely helped a lot, and made the entire file open/read/close flow easier to understand. I think the most annoying part of this week was definitely just learning that fwrite != fprintf (one is bytes and the other is strings). Besides that, the photo filtering and recover algorithms were really well explained in the problem brief, and didn't require too much mental gymnastics to figure out.

(Also, brief note that Filter Less and Filter More are basically the same program. More just replaces Sepia with Edges, but Edges builds off Blur, anyhow. Again, do both parts of the problem, I promise it's fun!)

In general, I think that I prefer practical projects rather than more abstract problems, which also explains my difficulties with algorithms. Well, I guess that was why I took this course - more algorithms!

Conclusion

In my predictions, I'd thought that weeks three through five were going to be the most painful, and I guess now that I'm here I kind of agree. Week 4 was tolerable, but Week 3 was absolute torture, and I'm not looking forward to Week 5 either. (On the bright side, Week 6 means the glory of Python once again.) Can't wait!

What are your tips for understanding pointers and algorithms, in C and in general?