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.

Week 5 – Stools, names, tracing

    This week’s lectures were a little unusual to me. The professor went over assignment one with us and helped us understand it. We spent an entire lecture just figuring out the requirements of the assignment and asking about difficulties we had with it. This gave me a better understanding of the assignment even though I had not started it at that point. In lecture we also learned about scopes and namespaces. Python looks for names in the following order: local, nonlocal, global and then built-in names. I never knew that we can have two of the same names in different functions, so that was pretty cool to learn! We also looked back at tracing a simple recursive function as further practice to strengthen our skills in recursion. We are told not to trace too far. Once you know the answer to something, just plug it in. It saves a lot of time for doing other things.

    Tutorials this week went smoothly just like last week’s tutorial. I was able to apply my newly attained knowledge to all of the problems presented in this week’s lab. Tracing the recursive functions wasn’t really challenging task for me but it provided me some good practice. However, writing the recursive functions was a much more difficult task for me. It was not impossible to do though; it simply took time and a lot of thought and effort. My partner assisted me with any difficulties I encountered while writing the recursive functions.
            
    Overall with the material covered this week I am fairly confident. I’m completely confident with the names and tracing portion. I will still however need to practice recursion a bit more to be fully confident with it. I feel like my achievement this week was achieved in the lab. I was able to make a recursive function to make a deep copy of a list. It felt nice knowing that I was able to rebuild one of the built in functions in python.

    I started the assignment on Thursday and was able to complete it on Saturday night. The first few steps were easy to understand and implement. The difficulty came when I had to make a recursive function for the four stools problem. That took me a couple hours but I was able to complete it and it felt great! I also did the bonus problem just to get some insurance points if something goes wrong with one of my functions.  

Week 4: More Recursion

                This week we went back to recursion and got a more in-depth look at recursion. A function that is recursive must call itself at some point within itself. A recursive function needs a well-defined stopping state so it will not run away and cause an error in python. Recursion was new to me and I had trouble understanding it at first. I slowly started getting more comfortable with it after we traced it on the tree burst example in lecture. Recursion is useful for problems that require the function to be used twice or more. I enjoyed when Danny brought his “turtle” to class to give us a visual example of the turtle class in action. The only thing we did this week was recursion, it challenged and frustrated me at the same time. I felt that if I did not learn it, I would fall behind in class. Luckily I started understanding it more by the second lecture of the week. Learning recursion was one of my achievements for this week.

                Overall, my confidence with the material that was done this week I am fairly confident with it. I will reread the lecture slides and trace the recursive functions in my own time at my own pace to gain a better understanding of recursive functions. I’m glad that I can finally find some time to learn about recursion, I’ve been trying to find some time in the past for it but never found any time for it due to my workload. Exercise two was due this week. I started it a bit late but was able to complete it within a fair amount of time. I only had problems with part a on the exercise, part b went flawlessly. The first problem in part a occurred when I forgot to reassigned x after I tried to convert it into an integer. The second error was a silly one… I just forgot to raise the error… quite embarrassing.

                The tutorial this week was enjoyable just like the last one. The teaching assistant is very friendly, knowledgeable and helpful. The tutorial helped me with more thorough testing of my functions by using the unittest class. It took a few minutes to get the hang of it since I usually just use doctest to test my functions. I used unittest only once in CSC108 but I forgot completely about it. The tutorial was a good refresher for more thorough testing of functions. We also got to play around more with inheritance which was not hard to comprehend because of my previous experience with it. The only question lingering in my head if when a loop would be better to use rather than a recursive function.  

Week 3: Object-Oriented Programming

                Object-Oriented Programming is a computer programming technique used widely across computer science. The focus of this style of programming is an object and this object is in its most basic form. Different methods are then added to the object in order for it to upgrade its functionality and make it more complex. For example, we have an object such as a car. We need methods for the car, such as a method to drive, stop, reverse, open and lock doors, roll down windows and to turn the car on and off. All of these methods would fall under the object car. These functions make up the car. A method that wouldn’t go under the object car would be to have the car transform into Optimus Prime as this function is not what a car was basically designed for. Object-Oriented Programming keeps everything much more organized as it can be seen in the example above. This style of programming also comes with multiple advantages, such as the reusability of existing code. Reusability is very useful, the world doesn’t only have one car on the roads. There are many cars on the roads so the object, car, would be used millions of times all around the world when required. The code would not need to be re-written for the car each time we make a new one.  We could create objects for anything we want, such as a clock, traffic lights and automated doors. Object-Oriented Programming is a powerful tool provided to programmers.

                The tutorials allowed me to bring my python abilities back to par after the Christmas Break. Not only that, but the tutorials allowed me to put my knowledge from the lectures to use. I was able to create an Object-Oriented Program without any problems and make the concept concrete in my head. Although I had some prior experience with Object-Oriented Programming, the information presented in the lectures required much more effort in order to understand. This experience probably gave me about one day’s head start.

I enjoyed the teaching style of the lecturer, he made sure to give us plenty of examples and went over each line of code until everyone in the class understood. I feel like my learning needs have been addressed by the lecturer and I believe, his teaching methods will help me learn above and beyond what is expected. Despite the ease in which I learned, there were some concepts I had issues with. The example of raising exceptions was a little difficult to understand. The part that troubled me the most was subclasses of exceptions. To solve my issue with exceptions, I plan to re-read the readings and lecture slides and attempt to trace the exception example given in lecture. Overall, I feel quite confident about the material covered in lecture this week, though in my spare time I wish to expand on the knowledge I was presented with.