Week 12 - Constant-Time Access & Review (Final Blog!)

    This week was basically a review period for us and we were just told about the exam and how to succeed in it. Danny also gave us a quick tour of how to make our own "dictionary" class. The school year is finally done and now it is time for yet more exams then... summer! I hope those who read this blog enjoyed my CSC148 journey I took them on.

Farewell.

Week 11 – Sorting and Efficiency

              Sorting is a powerful tool to find an item very quickly at a low computation cost. There are plenty of algorithms to choose from, each one has their advantages and disadvantages. Sorting can be used for many data types. An example of a sorting algorithm is the quick sort where you choose a pivot point; decide where the pivot point goes with respect to the rest of the list, and quick sort the remaining partitions until you have none left. This sorts our list very quickly and we can now find and pull out data out of the list fairly quickly, better than when it was unsorted. Another sorting algorithm is known as the merge sort where you divide the list in half and merge sort the halves (think recursion), after you merge the sorted results back into one list. Once again, a very simple and quick sort to have lying around. Efficiency is also known as Big-Oh, an upper bound for the runtime of an algorithm. The algorithm will never run longer than the upper bound that it was after a point C. The quick sort algorithm is Big-Oh of n lg n which can be rewritten as O(n lg n). This means that quick sort will never take longer than n lg n and will always be below it, thus it has a great efficiency of getting its job done.

              Something new I learned in class this week was how to make a sorting algorithm using recursion. Big-Oh was already known to be from a class from the last semester (CSC165). Nothing this week frustrated me and it was all clearly understood by me. Overall I feel very confident with the material this week. This week’s tutorial was the last tutorial which was saddening because the TA was one of the best I’ve ever had yet.

Week 10 – Sorting Big-Oh

                The first thing we did in this lecture this week was getting a better understanding of assignment two. Danny went over the four functions with us for half an hour giving us a complete understanding of what we have to exactly achieve and some ways to achieving the functions requirements. The functions that Danny went over with us were the following: is_regex, all_regex_permutations, regex_match, build_regex_tree. After his talk on each one I understood my task much easier and what it was that I was exactly trying to accomplish for assignment two. After the assignment two help, we moved onto sorting. The first type of sort we covered was quick sort. You have to choose a pivot by deciding with respect to the rest of the list and repeat on the left over slices of the list. We had a digression mid lecture to show what happens if you put a default value of an empty list in a function definition if no value is specified. After that we headed over to merge sort. The idea here is to divide the list in half and merge sort the halves until it is completely sorted. After that you merge the sorted results together.

               

                We got our assignment one marks back and I have to say that I’m really glad with my results. I couldn’t have asked for anything better. The lab this week was not as challenging as the previous labs. I found this one much easier. I was able to complete about three fourths of the lab before running out of time. Midterm test two is coming up and will probably be more challenging than the first one. It’s time for me to start studying. So I’ll have to cut this blog short to stick my head back into my notes and start reviewing.

Week 9 – Binary Search Trees, big-Oh

                Something new that I learned in class this week was binary search trees. I learned about big-Oh in CSC165 and it wasn’t new to me. Big-Oh during lecture was a good refresher since I did it last semester. Big-Oh is basically the performance of a programming being executed. The best programs run at constant time and the worst run at a time of factorial. In a binary search tree the data in the left sub tree is less than the value of the root. While the data in the right sub tree is greater than the root. This makes searching much more efficient. We learned about deletion of data from a binary search tree. This task can be very difficult because of the massive amounts of conditions needed to satisfy. A binary search tree in comparison to a list, a binary search tree will finish to task much faster on a large set of data. In a binary search tree, each time we narrow down the data to search by fifty percent which is extremely good. In lecture we also revisited selection sort and insertion sort from CSC108 last semester. We also looked at some running time analysis for various examples of code. The most enjoyable thing in class was binary search trees since I already knew about big-Oh.

                The lab was the most frustrating thing. We found out near the very end of the lab that we have to use recursion to solve our problem. Overall, I’m confident with this week’s material except for the lab we had this week. I’ll try to do the lab on my own during the next week in preparation for the midterm. We had an exercise due on trees. It was relatively easy and took about two hours to complete. 

Week 8 – Linked Structures

                This week in class we continued our discussion about linked structures. Especially linked lists and how they can be represented using the tree class. Linked structures are more efficient than regular python lists. If you have a data structure of millions of items, a linked structure is your best bet for efficiency and speed. If you were to remove the first item from a list of millions of elements, it would take very long for the process to complete. Whereas with a linked list, you just change the head and tail of the element you are wanting to remove. We were taught two different concepts in linked lists this week. They are both useful but different. The first method is as a list made up of an item (value) and the remaining list (rest). The second method was to represent it as objects (nodes) with a value and a reference to other similar objects. This week we used the second method. We learned about a wrapper class for linked list, insertion into the list, deletion, reversing and string representation. We almost created a binary search tree that represents data as a tree. You can search the tree very efficiently for an element.

               

                In class I enjoyed the binary search tree the most. Learning about new data structures always sparks an interest in me. The most challenging and frustrating part was in tutorials when we had to use a recursive algorithm to create the functions of the class. It took us a long time to figure out we had to use recursion. I feel confident with the lecture material but not the lab material. We got our test marks back. I was satisfied with mine even after a huge mistake on the final question. 

Week 7 – Recursion

                A function in python is a recursive function if it calls itself again within the body of the current function. Recursion is a powerful tool as it was seen in Assignment 1. We had to create a recursive function for Tower of Hanoi with four stools. It saved a great deal of time compared to loops and other methods. One of the most important things in a recursive function is to understand what you are exactly trying to accomplish. If you are trying to calculate the sum of the numbers in nested lists, you would use recursive to get the sum. This makes another issue arise. How do you know when to stop the recursion? You need a well-defined stopping state so it will not lead into an infinite loop. Another thing to note is that there is a maximum number of recursive steps Python can do before it runs out of memory and crashes. You can use recursion for many purposes, such as; factorials, sum of nested numbers and Fibonacci numbers. Recursion is a tool you really need to understand when learning programming, it will help you a great deal and save a lot of time when programming more complex systems. If you question when to or when not to use recursion, just thing about this: Do I have to do the same thing more than once?

                Because Week 7 occurred on a reading week, this blog entry may be a little shorter than the other blog entries. We had no lectures or tutorials this week. We have our first midterm on Wednesday. Reading week gave me the time to let me prepare for the midterm and I feel confident going to write the test. I reviewed all the material and I feel like I need to learn a little bit more about recursive structures to feel fully confident.

               

                Assignment 2 part 1 was handed out a few days ago. I took a quick glimpse at it but I have not begun one bit yet due to midterms. I will put all my time into it after the midterm.

Week 6 – recursive structures

                Something that I encountered in lectures this week was trees, it was completely new to me. The name tree comes exactly from the tree out there in nature. The trees can grow and shrink. There are roots, branches and leafs. You can only reach a leaf with one unique path. There is only one node in each tree and it is distinguished as root. Each non-root node has only one parent. You can calculate the height of the tree and branching factor of the tree. In class we did many examples with trees using recursion, such as: summing up the number of nodes in the tree, height of this tree, leaves and the branching factor. I enjoyed learning about trees, it gave me new insight on structuring data sets. I understand the majority about trees but there are some areas where I lack. I’ll be going over it during the reading week to gain a much better understanding where I lack. My confidence about trees is high, I feel like I understand the concept and where I could apply it. Now when I see trees outside, I’ll be thinking of trees in computer language.

                This week in the lab we worked on recreating given functions without using certain methods. It was a challenging lab but fun at the same time. We also did some unit testing, something that takes up a lot of time, I think. The hardest part of the lab was Pythagorean triples. We had to find every combination for Pythagorean’s triangle given the hypotenuse. It felt like an achievement once my lab partner and I finished it.

                Assignment one was due on Thursday. I was able to complete it all including the bonus. It felt like my biggest programming achievement to date. The biggest issue I had was with the recursive step. It took me a few hours to complete with my partner. Eventually we got it and moved on after a tiny celebration. We tested for an hour to ensure everything was working properly and we improved our docstrings.