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:...
Linear Systems A linear system is a set of linear equations. A linear system is consistent if it has 1 or infinite solutions, and inconsistent if it has no solutions. There are only 3 different situations to the solutions of a linear system: no solution (inconsistent) 1 solution (consistent) infinite solutions (consistent) A consistent linear system is different from a homogeneous one. Consistent means having solutions; Homogeneous means a linear system where all the constants are zero....
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....
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....
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....
If you are just here looking for the solution, this is my github link for the script. It should be pretty straight-forward. I am a DevonThink user. The thing that I love most about it is that it combines document organization tools with document viewing / editing tools. In one window, you will be able to edit the contents of a specific file while seeing the other files under the same directory....
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....
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....
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....
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)$