I'm taking a break from both studying and writing new CS/EE/Substack posts to just write about one of my favorite shows. I just found out from a friend that it's on Netflix, and said friend is also watching it for the first time. I watched this show during a time in my life where I didn't realize that I needed it, and I'm so glad that other people will get the chance to enjoy a show that's meant so much to me over the last several years.
I was a freshman in high school when I first watched this show. That period of time was difficult for me, because it was the first time I had truly entered an 'academically rigorous' environment. The amount of schoolwork that I had to keep up with made me feel like I was drowning in textbooks. I had little to no preparation to how much work I would get, and I can't say that I had anyone around to teach me how to manage and organize my time properly, let alone anyone in my immediate circle who could actually help me in any of my classes. It was the first time that I truly realized that I had to learn how to manage my own academic affairs. It was definitely an academic 'shock', for lack of a better term.
My mom was always insistent about learning from different cultures, and instilled in me to learn the history about not just our own culture but other cultures as well. It's certainly a belief that I've taken to heart the older I've grown. As a result of her interest in other cultures, growing up, we always had different cable channels from different countries (BBC, France24, and Aljazeera were some of the news channels we would commonly watch as a family, in addition to US news). I was watching BBC news when I saw an advertisement for the show. This is how I found out about it.
I remember taking study breaks to watch the show, and waiting for the premieres. This was also around the time that I found out about tumblr, and discovered the #CloneClub. It was nice being able to find others that were interested in the same show as I was, even if we were separated by a screen. I remember watching Cosima onscreen, the scientist of the group, and thinking to myself that if she could figure out complex biomedical research, then I can certainly get through my own biology homework. It was a show that at the end of the day I enjoyed watching, not only because of how good it was, but because the focus was on women, their lives, and their autonomy. They're not just experiments, but people with their own hopes, dreams, and aspirations, desperately trying to find more information about who they are and where they come from to form some sense of identity in their lives. That's what makes the show meaningful to me. Hopefully you'll give it a watch!
"Look. So, this spiral, this is the golden ratio and it's a mathematical pattern that just repeats itself in nature, in flower petals and honeybees, and you know, the stars in the galaxy, and in every molecule of our DNA." - Cosima Niehaus
This all started because I wanted to rip a phone book in half.
About a year ago, I was brainstorming different ideas to demonstrate search algorithms to my recitation section. I had done some of my own research on different videos to play in class [1] [2] [3] [4], but I hadn't come across anything specific to my needs in the classroom.
So, when you can't find a resource that you're looking for, just make your own!
I was inspired by the CS50 "Behind the Pedagogy" video [5] where David Malan mentioned that he used to rip phone books in half to visualize the concept of Binary Search. I though that would be a great idea to do this in recitation, but it was immediately questioned due to the lack of phone books in circulation and for the expense of having to obtain phone books every single semester. So, I thought the next best thing would be to record myself ripping a phone book in half, that way we would only need to rip a phone book in half once, thus decreasing our expense of the demonstration. I was successfully able to convince my professor to do this [6].
So, I enlisted the help of two other [7] TA's (Jonathan and Ronan) and the other [7] CSE250 professor, Oliver, with help for the project. I got to work, writing the script and setting aside time to record. It was genuinely difficult to set aside time to do all of this work while in the midst of my Electrical Engineering curriculum (and the others' CS curriculum) [8], but, we all made it work.
Coincidentally, the algorithms review at the end of CSE250 was removed that same semester, and I was never able to show this video during recitation. I was able to get this video finished to premiere it during a final exam review session, so there are students who did get to see it, which is a win in my book. Also, the video is in 4k because I forgot to turn off the 4k setting on the camcorder, mainly because I didn't realize that I rented a 4k camcorder in the first place. Using the school computers to edit and render the video was incredibly time consuming because it was shot in 4k, which added to the frustration of video editing. There were supposed to be fancy effects in the video, but I decided against including them, mainly due to time constraints and the frustration of every video editing software I used constantly crashing due to the excessive file size.
So, since I didn't add the effects in the video, I'll give a short summary of the search algorithms here.
Search Algorithms Performance Test:
Oliver, the professor, asks three students to perform a search in a phone book. Whoever finishes the query first gets an A in the "class" and everyone else still searching instantly fails.
Jonathan [sic], the first student, uses a method with hashing and chaining to find the requested information in O(1) time [9].
Gina (me), the second student, uses Binary Search to find the requested information in O(log n) time. This is still longer than Jonathan's method, so Gina (me) still fails the query.
Ronan, the last student, uses Linear Search, which runs in O(n) time, and is still searching for the requested information up until the end of the video.
Different search algorithms have different uses though, so just because a search algorithm doesn't perform in O(1) time doesn't make it completely useless. Some tradeoff speed for physical space, as hash tables can get pretty large on a physical storage device and can remove the ordering of data, but have a much "faster" search time. Or binary search, which really only works if your data is sorted. Hence why Binary Search (me), still fights for a B [10]. Linear Search is easiest to implement, and can get slow when dealing with larger datasets, but is always guaranteed to work. But since this particular "test" is only measuring speed, it gets an F in this case.*
Me and a few CSE250 TA's decided to make a silly video where we acted out different search algorithms and compared their runtimes by ripping
Honestly, I'm glad we went through with the video, we all had a lot of fun making it, and I know that someone might be able to look past the silliness and find something useful.
Now, before you ask, yes we have a bunch of bad takes, "bloopers", and general shenanigans. That's a separate video, which I've also included here.
Go forth and be educated, I guess. Until next time!
Sources & Side Notes:
[1] CS50 2019 - Lecture 0 - Binary Search
[2] Linear Search vs. Binary Search
[3] There are plenty more resources on youtube w.r.t. data structures, so I'm not going to include them all. I encourage you to look into some of these videos yourself.
[4] Unrelated, but I still wanted to share Nic Barker's Data Structures Video. He also has a side-project called Clay, which is a high-performance UI layout programmed in C. I recommend checking out the project.
[5] The CS50 Behind the Pedagogy Video
[6] He didn't want to appear in the video because he's camera shy, so I had to get Oliver to help me instead.
[7] former
[8] EE311 was an absolute monster of a course. That was easily the most difficult and time consuming course from my entire semester.
[9] In the general sense, just using a hash table with chaining would result in the bounds being O(n) and Ω(1). For the purposes of this algorithm and this video, the algorithm was able to find the query "Mike" in constant time because it happened to be the only name in that section of the phone book, which reduces the amount of material that the algorithm has to search through for that entry.
[10] Yes, a "B" for Binary Search.
*(Edit 4/16/26) This paragraph has been edited, because it incorrectly implied that other search methods are not actually "thorough" and might not be able to find what the user is looking for, which is an incorrect assumption to make. The original paragraph read: Different search algorithms have different uses though, so just because a search algorithm doesn't perform in O(1) time doesn't make it completely useless. Some trade off speed for thoroughness, or work better when adding or removing information much more frequently on top of searching for the material. Hence why Binary Search (me), still fights for a B [10]. Linear Search is easiest to implement, but can get slow when dealing with larger datasets, hence why it gets an F in this case.
Every semester, without fail, I get dozens of questions about tree rotations. It gets confusing to keep track of the direction of the rotation and the steps to reorganize the tree afterwards. It doesn't help that we don't spend too much time covering it in class either. This post seeks to make understanding tree rotations, their uses, and their algorithms just a little bit easier!
This post assumes familiarity with Binary Search Trees [1] [2] [3] and AVL constraints [4] [5]. If you're unfamiliar with either, then I recommend brushing up on those concepts before jumping into tree rotations. Before we start, it's important to note that tree rotations happen sparingly, and you'd only perform a rotation if a subtree is unbalanced. Otherwise, if your tree is balanced, there's no reason to do a tree rotation, and doing so might actually cause more problems. With that out of the way, let's get started!
Let's start with a Binary Search Tree. Since tree rotations are a way to balance our search tree, we'll make sure that our binary search tree is unbalanced. Since there are different ways to balance search trees [6], our goal will be for our tree to adhere to AVL balance constraints. Let's look at the example below:
Figure 1: A balanced AVL BST.
Let's say we remove Node F. Now our tree looks like this:
Figure 2: Our tree from Figure 1, with Node F removed.
Since this is an AVL tree, the balance factor of Node F's ancestors has changed, which causes Node C to have a balance factor of +2. Before removing Node F, Node C had a balance factor of +1. We'll have to rebalance our tree in order for it to adhere to AVL constraints. This is where tree rotations come in!
Our Special Rotation Algorithm:
We'll need to rotate Node F's parent, Node C, the node with the +2 balance factor, over to the left.
Figure 3: Our tree from Figure 2, but now we're preparing for a left rotation around Node C.
A leftward rotation will allow for Node C's right child, Node G, to become the parent of that entire subtree, while Node C becomes the new left child of Node G [7]. Node H becomes the right child of Node C. This preserves the ordering of the BST, since we want to make sure we maintain those constraints as well (a value smaller than the parent goes to the left, while a value bigger than the parent goes to the right).
Figure 4: Our new AVL tree after rotating around Node C.
Note that Node I doesn't change its position ever, it just stays put relative to the rotation. The Node G's former left node, Node H does change; it becomes the right child of Node G's "new" left node. If Node H were to have subtrees, those subtrees would not need to be changed.
Note that our new balance factor for Node G is -1 and Node C is +1. These are now within an acceptable range for our AVL tree constraints.
Final Algorithm:
Now that we know the steps we need to take, let's write down our algorithm in a cleaner way.
Since we just performed a left rotation, we can now infer the steps for a right rotation. Let's start with a slightly different AVL Tree (which, with the correct values, could also be a heap! [8]).
Figure 5: A brand new AVL tree, oOoOoOo...
Let's pretend we removed Node E. This would change our balance factor for Node B to -2 [9]. In order to fix this, we would need to do a rightward rotation around Node B. After doing so, Node B's balance factor will be 0, with Node D's balance factor becoming +1.
That's all there is to it! I recommend practicing drawing your own tree with different balance factors, then removing or adding a node, and trying to use a rotation to balance your tree. It's good practice that will help you visualize the process. Until next time!
Sources & Side Notes:
[1] Stanford's BST Lecture Slides.
[2] CMU's BST Notes.
[3] UB's BST Lecture Slides.
[4] Stanford's AVL Lecture Slides.
[5] AVL Tree Visualizer.
[6] AVL vs. Red Black Trees.
[7] UB's Tree Rotation Lecture Slides.
[8] Algosaurus - Heaps, Please note that you shouldn't do tree rotations on heaps, they'll break the structure of a heap. Please.
[9] Removing Node E doesn't affect Node A's balance factor because the height of its children never changes.
I'm at a watch party right now, geeking out about NASA sending a rocket to space. The first manned space mission since the 70's -that would get anyone excited. I should be studying for my midterm that's later this week... but this is MUCH more interesting.
I hear about standards all the time in my engineering classes. When working in a "social" field [1], it's important for everyone to have a shared set of (technical) rules and guidelines so as to avoid confusion [2]. There are plenty of different standards in the engineering world- IEEE, OSHA, ISO, ASME, etc. etc. But, sometimes I can't help but think about the standards that we as engineers set for ourselves both in and out of the classroom.
Engineering is one of those majors that forces you to time-manage, prioritize, and analyze your likes and dislikes. No one makes it through an engineering school because they hated it the entire time. No one [3]. The problem is that in order to do well in your coursework, there's a lot of sacrifice that needs to be made to your personal life [4]. As I watch the NASA launch, I think about how many of those engineers didn't get calculus for the first time, or maybe weren't the best at their statics course, or maybe couldn't wrap their head around probability while in their undergrad. But they're still able to work together (maybe even with people who did understand calculus, or statics, or probability) to build something bigger than themselves. They get to send people to space.
"Failure is not an option". [5]
When I fail a class I just fall behind in my degree program, and maybe waste some money. Maybe I'll experience some frustration, but otherwise I can continue on and do better. When NASA fails, people die.
How high do I set a standard?
I'm only human, but as an engineer, it's hard to find the right balance between "just get this homework done" and "my understanding of the material is lacking, I need to study more". Sure, I can just try my best and get the grade I deserve... but sometimes that's not enough. Sometimes it's necessary to set a higher standard for yourself. If not for yourself, then for your future. I've heard it said somewhere that your brain needs a certain amount of external pressure to truly commit something to memory in a short amount of time. There's a point where you have to worry about your grades, because it's the easiest signal to show that you understand the material you've learned. But what's also important is that you can't go at it alone.
Just like NASA relies on hundreds of people who know their stuff to send people to space, you have to connect with students who understand things that you don't. Progress can't happen in a vacuum [6], and it takes teamwork to build projects that are better than any one individual could've done on their own. It's good to study and worry about grades, but it's also good to reach out to classmates and struggle together, have study-groups and hackathons that run into the early hours of the night, because that's how real progress is made. Failure is not an option, but also, don't go into it alone.
I know that it's easy to set the bar for myself too high, and maybe take on things that are much too challenging for my (current) skill level. But maybe that's not a bad thing. As long as I have people in my corner to help me through those challenges, maybe it's not so bad to have a bar set so high.
Side notes:
[1] About as "social" as engineers can get.
[2] XKCD's Standards.
[3] No one that I've met so far.
[4] Especially if you're not a genius, billionaire, playboy, philanthropist... or if your math skills are just rusty.
[5] Source
[6] Unless you are literally in a space vessel in space.
