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....
Disclaimer TBD Course Contents Lecture 03 Discussed how to represent integers, floating point numbers, and more. For detailed notes, see data representation
Module: CS2100 Discussed how to represent the four basic data types in C: Integer Float Char Double For detailed notes, see data representation.
Module: CS2100 Lecture: Lecture 03 There are four basic data types in C. Namely, they are: int - 4 bytes long, which is equivalent to 32 bits. float - 4 bytes long, which is equivalent to 32 bits. double - 8 bytes long, which is equivalent to 64 bits. char - 1 byte long, which is equivalent to 8 bits. In this article, we are going to explore the underlying data structure that represet the 4 data types in C....
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;...
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....