The most difficult and assignment-intensive class I have had so far at Denison is Intermediate Computer Science, which I took last semester. In this class, I covered a new programming language, C++, and learned how to work with the Linux Operating Systems. C++ is a much more raw / bare-boned coding language than Python, which I learned previously; thus, it takes way more effort to grasp concepts like abstraction and remember all the syntactic nuances. Continuing my tendency to reflect on academic materials I learned, this post shows some of the important concepts in C++ programming and their real-world applications.
Sorting Algorithms: Sorting is a key to Computer Science theory, basically to sort is to order a list of objects. There are a few key sorting algorithms, and we rank them based on their algorithmic complexity, running times, startup costs, space requirements, use of recursion, worst-case behavior, assumptions about input data, caching, and behavior on already-sorted or nearly-sorted data:
- Bubble Sort: The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. In other words, the largest element has bubbled to the top of the array. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.
- Selection Sort: The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.
- Insertion Sort: To sort unordered list of elements, we remove its entries one at a time and then insert each of them into a sorted part (initially empty).
- Merge Sort: Based on the divide-and-conquer paradigm, it involves the following three steps: 1> Divide the array into two (or more) subarrays, 2> Sort each subarray, 3> Merge them into one.
- Quick Sort: Also known as partition-exchange sort, it uses three steps: 1> Choose any element of the array to be the pivot, 2> Divide all other elements (except the pivot) into two partitions (one less than the pivot and one greater than the pivot), 3> Use recursion to sort both partitions, 4> Join the first sorted partition, the pivot, and the second sorted partition.
Merge sort and Quick sort have better running time than the other three, since they both use recursion in their running functions. Check out these cool animations to understand these algorithms better, especially if you are a visual learner: http://www.sorting-algorithms.com/. Some of their uses I can think of apply to statistical analysis – frequency distribution (to see which variables appear the largest number of times in a set), recruitment strategies – selection (to pick the most qualified applicants), element uniqueness (to identify which candidate stands out more), closest pair (measure the difference between two candidates), architecture – convex hull (an important building block for very sophisticated geometric algorithms)…
Stack and Queue:
- A stack is a data structure consisting of a list of items and a pointer to the “top” item in the list. Items can be inserted or removed from the list only at the top, meaning that the list is ordered in the sequence of entry of items. Insertions and removals proceed in the “LIFO” (last-in-first-out) order.
- A queue is a data structure that stores elements in a list and permits data access only at the two ends of the list. An element is inserted at the rear of the list and deleted from the front of the list. Elements are removed in the same order in which they are stored and hence a queue provides “FIFO” (first-in-first-out) ordering.
Sounds complicated aren’t they? But a non-CS related applications of stack and queue concepts in real life is, simply enough, your job: When reducing staff, many companies are bound by agreements and regulations to use the “Last In First Out” to decide who goes and who stays. The accountants like this because shorter service equates to lower redundancy payments. The unions or other staff representatives like this because it removes any possibility of favoritism and prejudice or victimization from the choices.
Singly and Doubly Linked Lists: Linked list is a linear data structure that is used to store a collection of data. A linked list allocates memory to its elements separately in its own block of memory and the overall structure is obtained by linking these elements as links in a chain.
- A singly linked list is made up of a sequence of nodes and each node has a reference to the next node in the sequence.
- A doubly linked list contains a sequence of nodes in which each node contains a reference to the next node as well as to the previous node.
An incredibly fundamental data structure, linked list is used heavily in many computer functions:
- A list of images that need to be burned to a CD in a medical imaging application.
- A list of users of a website that need to be emailed some notification.
- A list of objects in a 3D game that need to be rendered to the screen.
A very cool metaphor I just came up with when thinking about linked list: Deleting a node in the middle of the list requires cutting off its connection with the previous and the subsequent nodes, as well as pointing the previous node’s forward pointer to the subsequent node and pointing the subsequent node’s backward pointer to the previous node. This, to me, is very applicable to success in life. The most important thing you can do to become extraordinary is learning how to say “No.” And this involves getting rid of the negative influences that are a burden in your life (unnecessary materials, time-consuming activities, bad colleagues…) and all of their associations with other positive influences. It’s not easy, but it’s something that worth to be practiced.
Now turning to you readers, what technical concepts you have learnt in school that resemble many real-world applications in our daily life?