Binary Search Tree

Recall that in binary search, we find the middle element of a list, compare the element that we want to find with the middle element, and then chooses to go to the left part of the list or the right part. A binary search tree is using a similar approach. The difference here is that in a binary search tree, we store the elements in a tree structure. Say that we have a list that looks like this:...

March 9, 2022

Tutorial Q3 Economic Research

You are an economist doing a research on the wealth of different generations in Singapore. You have a huge (anonymised) dataset that consists of ages and wealth, for example, it looks something like: 24 150,000 32 42,000 18 1,000 78 151,000 60 109,000 That is, each row consists of a unique identifier, an age, and a number that represents their amount of wealth. Your goal is divide the dataset into “equi-wealth” age ranges....

February 16, 2022

Quick Sort Revised

In the previous article, I discussed the brief idea behind quicksort. However, I wasn’t clear about the details, therefore creating much trouble for my own implementation of the quick sort. This article will build on top of the ideas discussed in the previous article. More specifically, it will focus more on the details of the implementation of quick sort. Specifically, we shall be discussing quicksort with 3-way partitioning. I also have to give a shout out to my friends Anis and Bruce....

February 16, 2022

Quick Sort

I apologize for the poor quality of this article. To be honest, writing this article was a huge mess. I spent a lot of time writing the article, but then I realized that I didn’t really get the details right. The idea was correct, but I vaguely described the implementation. When I went on to write the code, I realized that quick sort is actually all about details. Vaguely understanding the idea of quicksort makes it hard to implement it correctly – I spent hours debugging my code....

February 7, 2022

Selection Sort

Idea One way of sorting a list is that we iterate through the list, and for every iteration, we pick out the least item and move it to the front. Suppose below is the list that we want to sort. 1 9 7 5 4 6 8 10 3 2 Firstly, we find out the least item in the entire list through iteration. In this case, the least item is $1$, which happens to be the first item of the list....

January 31, 2022

Bubble Sort

Suppose that we are given the following list: 1 9 7 5 4 6 8 10 3 2 The idea of bubble sort is that we iterate through the entire list several times, and for each time, we swap the adjacent values if their relative position is not correct. So, for the first iteration, we start looking at 1 and 9, and find out that their relative position is correct. We then go on to look at 9 and 7, and find that their relative position is incorrect....

January 31, 2022

Insertion Sort

In merge sort, our goal was to make sure that the first $i$ items are sorted and are the least items. However, the process of finding the least item in each iteration is actually quite expensive - you’ll have to iterate through the whole least. Hence, an alternative idea would be to simply make sure that the first $i$ items are sorted, and nothing more. Therefore, we do not need to search for the least item....

January 31, 2022

Week 03

This week’s lectures mainly focused on the different sorting techniques. Below is a table detailing the techniques. Technique Big-Omega Big-Theta Big-O Bubble Sort $O(n)$ $O(n^2)$ $O(n^2)$ Selection Sort $O(n^2)$ $O(n^2)$ $O(n^2)$ Insertion Sort $O(n)$ $O(n^2)$ $O(n^2)$ Merge Sort $O(n\log n)$ $O(n\log n)$ $O(n\log n)$

January 31, 2022

Merge Sort

Suppose we have a list 1 9 7 5 4 6 8 10 3 2 and our goal is to sort the list. Merge sort’s idea is to divide the list into small segments and recombine them. Here, we have the list sorted. Code Java Implementation public class MergeSort{ public void sort(int[] nums) { copy(nums, _sort(nums));; } static void copy(int[] arr1, int[] arr2) { assert arr1.length == arr2.length: "trying to copy two arrays that do not have the same size"; for (int i = 0; i < arr1....

January 31, 2022

Lecture 03

This lecture discusses the Big-O Notation and Binary Search. Big-O Notation Big-O notation is used to describe the order of growth of many types of things. In CS2040S, we use it to describe time complexity of algorithms. Note that: $O(f(n))$ describes the upperbound of the growth of $f$, i.e. the worst case-time complexity; $\Omega(f(n))$ describes the lowerbound of the growth of $f$, i.e. the best-case time complexity;...

January 18, 2022