About Here are my notes for the NUS Module CS2040S Data Structures and Algorithms.
Technically speaking, they are not notes, but rather my attempts to explain the contents covered in the class.
Disclaimer I titled this series CS2040S because it is the notes that I wrote while taking the CS2040S. However, I do not by any means represent the teaching team at NUS (I am only a newbie student taking this course), nor do the contents that I wrote represent what was taught in class....
Module: CS2040S
Lecture: Lecture 03
Binary search is HARD!
What is Binary Search? Bineary search is an algorithm that allows you to find the item you want in a sorted list in $O(\log(n))$ time. It accomplishes this by dividing the list into two parts, check which part the target value is in, and then go on to divide that part of the list into two parts ……
An Example by Hand Here is an example where we do binary search by hand....
Module: CS2040S
Week: Week 02
We use big O notation to denote the complexities of growths of certain things. Specifically, in the context of computer algorithms, we use big O notations to measure the time complexities. Below is a function:
$$ f(x) = x^3+2x^2+3x+1 $$
suppose that we want to learn about the order of growth of the function above. We would quickly realize one thing: as $x$ gets greater and greater, the $x^3$ seemed to become the component that contributes the most to the function’s growth, whereas the other components have a less and less contribution....