Sorting and Efficiency

Sorting is the process of placing elements from a collection in some kind of order. For example, a list of words could be sorted alphabetically or by length. A list of cities could be sorted by population, by area, or by zip code.

There are many types of sorting, like bubble sort, selection sort and insertion sort. In CSC108, we learned selection sort and insertion sort. In CSC148, we learned two new sorting called quick sort and merge sort.

Quick sort is the idea to choose a pivot, decide where the pivot goes with respect to the rest of the list and then repeat on the partitions. Merge sort is the idea to divide the list in half, (merge) sort the halves, then merge the sorted results.

Here are the examples for the two sorting method.
Depends on the different ways we sort, the problem of efficiency appears.
For efficiency, "Big O" is used. Here is a description of "Big O" on wikipedia:

Big O notation has two main areas of application. In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic expansion. In computer science, it is useful in the analysis of algorithms.
Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n² − 2n + 2. As n grows large, the n² term will come to dominate, so that all other terms can be neglected—for instance when n = 500, the term 4n² is 1000 times as large as the 2n term. Ignoring the latter would have negligible effect on the expression's value for most purposes. Further, the coefficients become irrelevant if we compare to any other order of expression, such as an expression containing a term n³ or n⁴. Even if T(n) = 1,000,000n², if U(n) = n³, the latter will always exceed the former once n grows larger than 1,000,000 (T(1,000,000) = 1,000,000³= U(1,000,000)). Additionally, the number of steps depends on the details of the machine model on which the algorithm runs, but different types of machines typically vary by only a constant factor in the number of steps needed to execute an algorithm. So the big O notation captures what remains: we write either

or

and say that the algorithm has order of n² time complexity.

Well, this is how "Big O" works.
And I will show an example of "Big O" by merge sort:

Therefore, sorting helped us to makes objects listed in some kind of order. And efficiency of sorting helped us to choose the most efficient to sort elements.

Week 9 -- Binary Search Tree

In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.

• The right subtree of a node contains only nodes with keys greater than the node's key.

• The left and right subtree each must also be a binary search tree.

• There must be no duplicate nodes.

Because of the special structure of the binary tree, it's easier for us to search an element which is in the tree. We just need to make a recursion: if the element is greater than the root, we search the right tree in the same way; if the element is smaller than the root, we search the left tree.

Week 8 -- linked List

There are two ways to represent linked list. One of which is as lists made up of an item (value) and the remaining list(rest), the other way is as objects (nodes) with a value and a reference to other
similar objects.

For the first type, the class for LinkedList is initialized like this:

And for the second type, a class call LListNode is defined first to represent the objects in the linked list:

Linked list makes each elements related(linked) one by one.

For this example, the nodes will be linked like this:

Week 7 -- Recursion

Recursion is a very useful method in python. It's basically using itself in its own function. By using recursion, programmers can write shorter and easier functions.
For example, when we want to sum up the numbers in a list:
We can write:

This function works when s is just a simple list with numbers. But when s is a nested list, the problem appears:





And this is when we can use recursion:

We can see that when recursion is used, the function become easier to built.

OBJECT-ORIENTED PROGRAMMING

In the first week of csc148, we learned object-oriented programming. Object-oriented programming (OOP) became the main programming paradigm used in the creation of new software in 1980s. It is a programming language model organized around objects and data. Once an object has been identified, it is generalized as a class of objects which defines the kind of data it contains and any logic sequences that can manipulate it. Each distinct logic sequence is known as a method. And the object is known as the instance of the class. 

The reason why OOP is popular today is that it provides important benefits. It forces a more thorough data analysis, reduces development time, and ensures more accurate coding. And python, what we are learning in csc148, is also an object-oriented programming language.