Sorting, Efficiency and Big O

So far, this course has been fun and interesting. Earlier we were learning about various aspects of python as well has strategies to code. However, now we began learning about the efficiency of code. We were told that programming is one thing, however, programming efficiently is another thing. Writing code that is inefficient will be useless as it will take too long to run (running time determines efficiency), therefore a programmer needs to make sure his code runs accurately as well as efficiently. This can be done by avoiding repetition (one major problem that makes a program inefficient).  

The examples we took up in class, to show how efficiency can vary, were the examples of various sorting algorithms. The reason behind this was that all algorithms performed the same task, however, in a varied manner.  The algorithm that sorted in the least possible steps was the most efficient and the quickest. We also looked at how the problems given impact the efficiency of various codes. This was done during the lab where we ran 3 types of problems. In the first case, we gave the algorithms a sorted list. In the second case, we gave the algorithms a randomly unsorted list . In the third case, we gave the algorithms a list that was unsorted and in the order of largest to smallest. Various algorithms performed differently due to the difference in code. We then mapped the run time and found that the bubble sort algorithm took the longest for all 3 cases and the insertion and selection sort’s times varied depending on the situation. We then also saw how tweaking the algorithms could improve the run time, for example preventing the repetition of the function-len(). Other than these sorting algorithms, in class we also learned about the tim sort and quick sort.

We also learned about Big O notation. We learned that Big O is used to classify algorithms by the manner in which they respond to a change in input size n. The best response of an algorithm could possibly have is O(1)-(where the algorithm completes the task in one step), and the worst was O(n!)-(where the algorithm does the task in n factorial steps). We then classified various algorithms using big O notation including the various sorting algorithms. We were told that programmers always look at the worst case when classifying an algorithm (however, average case and best case are also looked at). Regarding the sorting algorithms, we learned how Selection sort works by repeatedly selecting the smallest remaining item and putting it where it belongs therefore having a time complexity/Big O of  n^2 under both the best and worst case. This is clearly because it has to go through n items n times. We also learned that Insertion sort works by repeatedly inserting the next item where it belongs in the sorted items at the front of the list therefore having a best case of O(n) when the list is sorted and O(n^2) when the list is unsorted(especially from largest to biggest). As we know that bubble sort compares each item to the item next to it no matter what, therefore it has best case scenario of O(n) if the list is sorted and worst case O(n^2) if the list is completely unsorted.

Overall, I found this section of the course very helpful and interesting. It taught me that a programmer doesn’t only aim to make his/her code work, he/she aims to make the code work and that to efficiently and quickly.

SLOG 4

This week was an exciting week. On one side, reading week is approaching. On the other side, term tests are nearing as well.  

During class, we learned about the application of recursion in the form of trees. We went through the use of trees in computer science. We learned about the jargon used whilst talking about trees. We were taught aspects such as nodes(each circle), roots, parents(the node that is connected to a node below it), leaf(node with no children), subtree(tree formed by any tree node together with its
descendants and the edges leading to them). We also learned about the height of a tree and various paths.  We went through code for preorder traversal and inorder traversal. We also went through the code to initialise the class of a tree. Surprisingly, the week ended with an assignment being posted based on trees, just two days after we submitted Assignment 1.  I read through it and look forward to solving it.

SLOG 3

This week was an interesting week. I was busy working on the assignment with my partners. The assignment initially seemed easy. However, later on the Tour.py file brought up challenges. The assignment was the primary focus of the week.

In class, the primary focus was also various parts of the assignment. Then we also talked about scopes and did some tracing. This week was an interesting week that helped me advance in my assignment and learn more in the field of computer science.

SLOG 2-Recursion

This week was another new chapter in my journey through computer science. We learned about recursion and its importance in Computer Science.  We learned how recursion is the process in which the final result of the code depends on many small iteration. We first went over nested lists and saw how the sum of nested lists are important before the sum of the primary list can be computed. This was the first example of recursion. Then we went through tree_burst.py This was a program that used recursion and helped me understand the inner dynamics of recursion. I believe that Recursion is a building block that is vital in programming.

SLOG 1

Having never programmed before, I was thrilled when I joined the University of Toronto in order to study Computer Science. The manner in which we can manipulate computers to do what we want has always been very exciting for me. So far, Computer science is a course that has never disheartened me.  CSC108 was a fun course where we learned the basics of programming in an interesting manner.  I enjoyed the videos. However, the moment I was told that CSC148 will not be having video lectures, I began to worry. Knowing that I had videos to go back to, always gave me confidence. However, the moment Professor Heap began his lecture, I knew that not having videos was no disadvantage in this class as every concept was made crystal clear within the classroom.

Coming to the content of CSC148, so far, it has been challenging yet interesting. Within the last few weeks, we focused on Object Oriented programming.  This caught my attention as it taught me how we as programmers can write code that help both us and other programmers, as it acts as building blocks to create other programs. This is code that could be reused in order to save time and is written using Classes (working towards the lazy aspect of programming talked about in class). This helped me as it made me fluent in using Classes. Then we were taught about Abstract Data types, in which we focused on the class Stack. Stack was another ADT that impressed me. I thought about the various applications this could have in my life, which made me even more excited to learn about it. Hence, I learned how to write code for creating a class: Stack, making it Push, Pop and finding out if it is_empty. I also played around with it, to increase my fluency.  During the lab, the tasks were very helpful, as it removed any knowledge gap that was present in my understanding.  I enjoyed writing code to create a Queue as well and testing the time the code took.

Overall, I enjoyed the content taught during the last few week. Its real world applications make me curious to find out what we will learn next. This SLOG, I believe is an ideal method by which I can portray my thoughts regarding the content being taught. It will also tell me if my thought process is correct or whether I misinterpreted some concept taught in class. This week, my biggest achievement was mastering the code behind this ADT and experimenting with it.

Siddharth Gautam

CSC148

Professor- Danny Heap