This week, we briefly went over constant time access on Monday then did review on Wednesday. I also got back my mark for term test 2. Even with the 3 mark boost I got, I did not do as well as I would have liked. I wish I had spent more time on LinkedLists because even though I understood the examples, I didn't write a lot of the code on my own. I need to practice writing recursive functions, especially ones involving LinkedList, binary trees, and other ADTs.
It's interesting to see other students' take on certain topics in the course because sometimes just the wording, or the example they present, makes it easier to understand. For example, I was having difficulty understanding the lab involving binary search trees, so I looked through the sLOGs and found this one: http://codinginmotion.blogspot.ca/. This person did an overview of rec1, rec2, and rec3 and included code of one of the functions. It didn't even use recursion! For me, sometimes I get caught up in all of the new concepts that we learn in class that I forget my basics. For instance, in exercise 4, we wrote functions for binary search trees, but we had to write it without using recursion. Modelling my function after the given insert function, I was able to figure out e4a and e4b using a while loop for each.
I don't think I personally will be keeping a sLOG after this post, but I will definitely refer back to others' blogs to see their take on each topic. It will help me with studying and my future endeavors in computer science. With that said, it's been a fun ride, CSC148. Now to take on the final exam!
Friday, 4 April 2014
Monday, 31 March 2014
Week 11: Sorting and Efficiency
This week in lecture and in the lab, we looked at sorting algorithms and their efficiency. The algorithms we looked at were insertion sort, selection sort, bubble sort, quick sort, and merge sort. We compared their efficiency to timsort, Python's built-in sorting method), but only by run time since no code was provided. Here are some observations I've made about each of the algorithms:
Insertion Sort
There were two versions of insertion sort, the second of which included a call to "del." This version of insertion sort ended up being faster than the first one. To compare, on a 2000 item list, insertion_sort_1 took 0.44 seconds while insertion_sort_2 took only 0.26 seconds. In insertion_sort_2, the algorithm will look for the insertion point, and once it is found, the item that needs to be sorted gets stored in a variable and deleted from the list. This makes the algorithm run time faster because once the insert method is called, the list is now one item shorter. Thus, it can put the item in the right spot by looping over fewer elements.
Selection Sort
Selection sort is interesting because it is always in O(n^2). It goes through the entire list to make comparisons to ensure that each element is properly swapped if need be. Compared to other algorithms, it is faster than bubble sort, but slower than insertion_sort_2. In the lab, my partner and I discussed ways of making this algorithm faster, and we discovered that since the while loop called "len" during each iteration, it made the run time a little slower. To fix this problem, we assigned len(L) a variable before the while loop so that "len" would only be called once.
Bubble Sort
Bubble sort is by far the slowest sorting algorithm. Although there were two versions of it included in the lab, both took approximately 0.7 seconds on a 2000 item list. Bubble_sort_1 simply makes swaps until the largest item is at the end of the list, which is the sorted section. Bubble_sort_2 checks if there were any swaps on the previous scan of the list, and if not, the algorithm will stop early. It was interesting to see that the second version was not actually faster as expected. Looking over the code, I think it was slower than bubble_sort_1 because of the extra while loop. It's one extra step to check, so if this version was used on the worst case, the run time would be much slower than bubble_sort_1.
Quick Sort
Quick sort is a fairly fast sorting algorithms, but unlike most sorting algorithms, it's slower on nearly sorted or sorted lists. Since it partitions smaller elements to the left and larger elements on the right of the pivot, there will be an unequal number of elements in the right half. The algorithm works much faster when used simultaneously on halves with a similar number of elements. Of the two versions of quick sort below, the second method has a faster run time because it doesn't make copies of the sub lists. Instead, it works with the original list all throughout. The difference is noticeable, with quicksort_2 being 0.3 seconds faster than quicksort_1.
Merge Sort
Merge sort works recursively by splitting the list into two halves, sorting those halves, then merging them together. We worked with two versions of merge sort: mergesort_1 works by creating new lists while mergesort_2 continually updates the original list. The second method is faster (0.010302 seconds vs. 0.009599 seconds). Similar to quick sort, this is because it takes more time and memory to create new lists each time, whereas only using the original list is more efficient.
Although there are six sorting algorithms mentioned above, there exist even more to do the same simple task: sort a list of numbers in non-decreasing order. This is one of the key aspects of computer science. Even though there may be a best way to do a task (in this case, Python's built in method was the most efficient), it's important to notice that there are multiple ways to look at a problem and solve it.
Insertion Sort
There were two versions of insertion sort, the second of which included a call to "del." This version of insertion sort ended up being faster than the first one. To compare, on a 2000 item list, insertion_sort_1 took 0.44 seconds while insertion_sort_2 took only 0.26 seconds. In insertion_sort_2, the algorithm will look for the insertion point, and once it is found, the item that needs to be sorted gets stored in a variable and deleted from the list. This makes the algorithm run time faster because once the insert method is called, the list is now one item shorter. Thus, it can put the item in the right spot by looping over fewer elements.
Selection Sort
Selection sort is interesting because it is always in O(n^2). It goes through the entire list to make comparisons to ensure that each element is properly swapped if need be. Compared to other algorithms, it is faster than bubble sort, but slower than insertion_sort_2. In the lab, my partner and I discussed ways of making this algorithm faster, and we discovered that since the while loop called "len" during each iteration, it made the run time a little slower. To fix this problem, we assigned len(L) a variable before the while loop so that "len" would only be called once.
Bubble sort is by far the slowest sorting algorithm. Although there were two versions of it included in the lab, both took approximately 0.7 seconds on a 2000 item list. Bubble_sort_1 simply makes swaps until the largest item is at the end of the list, which is the sorted section. Bubble_sort_2 checks if there were any swaps on the previous scan of the list, and if not, the algorithm will stop early. It was interesting to see that the second version was not actually faster as expected. Looking over the code, I think it was slower than bubble_sort_1 because of the extra while loop. It's one extra step to check, so if this version was used on the worst case, the run time would be much slower than bubble_sort_1.
Quick Sort
Quick sort is a fairly fast sorting algorithms, but unlike most sorting algorithms, it's slower on nearly sorted or sorted lists. Since it partitions smaller elements to the left and larger elements on the right of the pivot, there will be an unequal number of elements in the right half. The algorithm works much faster when used simultaneously on halves with a similar number of elements. Of the two versions of quick sort below, the second method has a faster run time because it doesn't make copies of the sub lists. Instead, it works with the original list all throughout. The difference is noticeable, with quicksort_2 being 0.3 seconds faster than quicksort_1.
Merge Sort
Merge sort works recursively by splitting the list into two halves, sorting those halves, then merging them together. We worked with two versions of merge sort: mergesort_1 works by creating new lists while mergesort_2 continually updates the original list. The second method is faster (0.010302 seconds vs. 0.009599 seconds). Similar to quick sort, this is because it takes more time and memory to create new lists each time, whereas only using the original list is more efficient.
Sunday, 23 March 2014
Week 10: Sorting Algorithms
This week I finished A2 finally. I went for help during office hours, and it gave me a lot of insight into how to use recursion and how to approach these problems by breaking them down. It helped me to do the doc string examples first before writing the code. I didn't get the regex_match one to work fully, so i will have to go back and work on it.
We did sorting algorithms in lecture, and honestly it's a little fuzzy to me. I understand how merge sort and quick sort work, but the implementation seems complicated. I'm going to look over the material and study for test 2 at the same time.
We did sorting algorithms in lecture, and honestly it's a little fuzzy to me. I understand how merge sort and quick sort work, but the implementation seems complicated. I'm going to look over the material and study for test 2 at the same time.
Week 9: Binary Trees
This week was probably the toughest one material wise. I had difficulty getting recursion to work on E3, and I'm unsure of how to write the functions for A2 part 2. I definitely need to ask for help when I need it. I think part of it is that I haven't taken enough time to review the material on my own time, and I also need to get clarification on certain parts of A2. There are so many cases to take into consideration, especially with the regex_match function. That will likely be the most difficult one to deal with.
Saturday, 8 March 2014
Week 8: Linked Lists
This week we did more on linked lists. We had done a lab for linked lists in week 7, but we did a continuation of it in this week's lab. My partner and I had a lot of trouble figuring out the different methods for linked lists. Even though we drew pictures, we still had difficulties. Clearly this is an important concept that I need to figure out not just for future assessments (like the final exam), but for my own understanding of computer science. I'm so used to the mechanical coding we learned in 108. This course is more in depth when it comes to problem solving, and it is something I need to work on.
Since I didn't finish either lab 6 or 7 during tutorial time, I want to work on it on my own time. I believe if I can do the labs on my own, I will have a solid understanding of linked lists and recursion.
Since I didn't finish either lab 6 or 7 during tutorial time, I want to work on it on my own time. I believe if I can do the labs on my own, I will have a solid understanding of linked lists and recursion.
Thursday, 27 February 2014
Week 7: Recursion
So I've written about recursion before, but now I think I understand it a lot better. After reviewing the recursive functions from class examples repeatedly, I can confidently break down what recursion actually means.
Recursion involves a function calling itself. However, there is always a base case, where there is no recursion involved. For example, take a look at the nested_depth function:
Here, the else clause is the base case. If L is an int, no recursion is involved, and 0 is returned. Recursion happens when there are lists, so if I have L = [1, 2, [3]], the function will go through the entire list before returning a value. Since L is a list, it will return 1. The first element of the list is 1, which is not a list, so it will return 0. Next, 2 is also not a list, so it returns 0. The next element is a list, which will add 1. for a total of 2. Now that the function has reached the end of the list, it will return 2.
Tracing through examples, starting with the base case, is very helpful because once I know the output of a simpler example, I can apply it to a more complicated example.
Recursion involves a function calling itself. However, there is always a base case, where there is no recursion involved. For example, take a look at the nested_depth function:
Here, the else clause is the base case. If L is an int, no recursion is involved, and 0 is returned. Recursion happens when there are lists, so if I have L = [1, 2, [3]], the function will go through the entire list before returning a value. Since L is a list, it will return 1. The first element of the list is 1, which is not a list, so it will return 0. Next, 2 is also not a list, so it returns 0. The next element is a list, which will add 1. for a total of 2. Now that the function has reached the end of the list, it will return 2.
Tracing through examples, starting with the base case, is very helpful because once I know the output of a simpler example, I can apply it to a more complicated example.
Sunday, 16 February 2014
Week 6: Tree ADTs
This week we looked at Tree ADTs, and I think they helped me better understand recursion. I'm still having a little bit of trouble writing recursive functions myself, but attempting to write functions for pre-order, post-order, and inorder helped me in a couple of ways: first, I practiced writing list comprehensions, and I increased my understanding of recursion.
I think what really helped this week was the lab that we did this week. It was a relatively short lab, but we still took the whole time because we really wanted to take our time to understand the recursion behind the functions.
I am still a little confused about namespaces and scopes, but there was this post on http://aheapofpythons.wordpress.com/ that helped me understand it a bit better. I think I work by myself too much at times. In 108, I did all the assignments on my own, and I always did the worksheets in class on my own. In 148, the only time I ever work with people is during the labs. I've realized that it helps a lot, and now reading other people's blogs, I will definitely make an effort to ask other people for help if I need it.
I think what really helped this week was the lab that we did this week. It was a relatively short lab, but we still took the whole time because we really wanted to take our time to understand the recursion behind the functions.
I am still a little confused about namespaces and scopes, but there was this post on http://aheapofpythons.wordpress.com/ that helped me understand it a bit better. I think I work by myself too much at times. In 108, I did all the assignments on my own, and I always did the worksheets in class on my own. In 148, the only time I ever work with people is during the labs. I've realized that it helps a lot, and now reading other people's blogs, I will definitely make an effort to ask other people for help if I need it.
Friday, 7 February 2014
Week 5: More Recurision and Namespaces
This week we looked into recursion for Step 5 of Assignment #1. In theory, it makes sense to me. I tried running it through the python visualizer, and honestly it was a bit of a mess in my mind. The steps were going all over the place. At least, that's what it looked like. I'm going to go back through simple recursion functions to make sure I understand the concept fully. Even though we did a recursion lab this week, I probably let my partner do more work than I should have. I was able to follow what she was doing, but writing the functions myself is a lot different. I need to be able to write some myself first. Only then will I write the recursive function for four stools.
On Wednesday, we went over namespaces. Words like local, non-local, global, and inner scope come to mind, but I don't know exactly what they mean. I wasn't entirely able to follow what was going on in class, so I definitely need to review that more. Someone else wrote "I learnt from this class that the class readings and lecture notes are so crucial to this course" (from http://endwithcolon.blogspot.ca/, if you're interested). It's a good point, and it seems obvious, but I haven't been keeping up with the course material as much as I did with 108. I really liked the inverted classroom format last semester, and I wish we had that, but I understand that as I advance in my computer science career, there won't always be structure. Maybe the freedom could be good too. It will give me a chance to discover my learning style (although I think I know how I learn best already) and try new things.
On Wednesday, we went over namespaces. Words like local, non-local, global, and inner scope come to mind, but I don't know exactly what they mean. I wasn't entirely able to follow what was going on in class, so I definitely need to review that more. Someone else wrote "I learnt from this class that the class readings and lecture notes are so crucial to this course" (from http://endwithcolon.blogspot.ca/, if you're interested). It's a good point, and it seems obvious, but I haven't been keeping up with the course material as much as I did with 108. I really liked the inverted classroom format last semester, and I wish we had that, but I understand that as I advance in my computer science career, there won't always be structure. Maybe the freedom could be good too. It will give me a chance to discover my learning style (although I think I know how I learn best already) and try new things.
Thursday, 30 January 2014
Week 4: Recursion
We've already briefly gone over recursion a couple of weeks ago, but it was nice to review it again. I still don't know if I have the hang of it because we've practiced tracing multiple examples, but I don't know if I'm proficient at writing recursive functions myself. So far, we've done the tree_burst example and the sum_list example. What other functions could I write myself? I think looking for some examples online might help.
I've looked over the assignment 1 handout a few times already, and I know I understand the Cheese class. The hardest part is writing all of the headers and function calls for the TOAHModel class. I don't quite understand how to model the stools. Is it a list? How do I add "n" cheese to each stool? Why do I need a function that asks how many moves I've made so far? There's already one in the MoveSequence class. I'm definitely going to ask for help on that. Once I understand what to do, I think I'll be able to get a good head start on the assignment. There's no way I'm leaving it to the last minute. Sometimes when I'm walking to class I'll suddenly come up with a way to solve the problem. It's the best feeling ever.
I've looked over the assignment 1 handout a few times already, and I know I understand the Cheese class. The hardest part is writing all of the headers and function calls for the TOAHModel class. I don't quite understand how to model the stools. Is it a list? How do I add "n" cheese to each stool? Why do I need a function that asks how many moves I've made so far? There's already one in the MoveSequence class. I'm definitely going to ask for help on that. Once I understand what to do, I think I'll be able to get a good head start on the assignment. There's no way I'm leaving it to the last minute. Sometimes when I'm walking to class I'll suddenly come up with a way to solve the problem. It's the best feeling ever.
Wednesday, 22 January 2014
Week 3: Object Oriented Programming
This week, the lecutres and labs were focused on object oriented programming. We worked on a Stack class mostly, and at this point I think I have a solid understanding of it. I know what a stack does, I know how to push and pop objects, and I know how to write simple method calls. The most difficult part was inheritance because I didn't quite understand how Stack and IntStack interacted. I was able to follow most of what was said in lecture, but I definitely need to review the examples on my own time.
Another thing I need to review is exceptions. I felt like we skimmed over the topic too quickly in lecture, and although we went through a couple of examples, there wasn't a lot of structure in terms of teaching us how to write an exception. With that said, my plan is to look over the class examples and make my own notes on how to write exceptions.
I really enjoyed the lab this week. My partners and I actually got through the entire thing within the allotted time (thank goodness), and the difficulty of the lab was just right. We struggled with finding a way to make the Queue class faster, though. We discussed it for a bit, but we weren't able to come up with anything. How can we preserve the indices' order so that it doesn't have to reset every time we add or remove something from the queue? I guess that's something I will have to think about for a while and possibly ask about later on.
Another thing I need to review is exceptions. I felt like we skimmed over the topic too quickly in lecture, and although we went through a couple of examples, there wasn't a lot of structure in terms of teaching us how to write an exception. With that said, my plan is to look over the class examples and make my own notes on how to write exceptions.
I really enjoyed the lab this week. My partners and I actually got through the entire thing within the allotted time (thank goodness), and the difficulty of the lab was just right. We struggled with finding a way to make the Queue class faster, though. We discussed it for a bit, but we weren't able to come up with anything. How can we preserve the indices' order so that it doesn't have to reset every time we add or remove something from the queue? I guess that's something I will have to think about for a while and possibly ask about later on.
Subscribe to:
Posts (Atom)