This week, I'm revisiting an old SLOG and analyzing how I've changed over the course. I am choosing to revisit my third SLOG, which was about recursion. During the time of that SLOG, I was very confused about recursion and I found it very difficult to understand. Now that we are in the final weeks of CSC148, I have had more practice with recursion both conceptually and when programming. I'm even using it in my current program in Assignment 3!
I now understand recursion as a very vital asset in terms of programming. It can make searches, creation, and the like so much more easier when you can recurs over the entire function. While it is sometimes very frustrating to implement in a program, it makes complex problems seem like a thing of the past.
This week in class, we learned about the run times of programming and what we can do to increase or decrease run time. This was also like an introduction to CSC165, which is a computer science course on mostly the "science" part of CS. For example, the run time of a search, say n in L, is dependent on the length of the list. This means the run time has a direct relationship to the length of the list.
We also learned that there is a formula for the maximum number of nodes in a binary tree, (2^n) - 1. Not only that, but the maximum number of leaves the last row of a tree can have, 2 ^ (n - 1). When talking about the height of the tree, we know that n ≤ (2^h) - 1, or log(n + 1) ≤ h.
We can also look at run times in sorting algorithms. Back to CSC108! We discovered that bubble, selection, and insert sort all have a run time proportional to the list by n^2. This means that the run time is quadratic. This makes the algorithm very slow, so we created a new sort, quick sort, which has a run time of log(n), proportional to the list. This makes the sort speed super fast!
This whole logarithm thing still confuses me, so I'm hoping if and when I take CSC165 that I will understand the logic behind all of the run times and I will better learn how to do the science behind the programming.
Tuesday, 31 March 2015
Saturday, 21 March 2015
8 - Eliminating Redundancy
This week we learned about why minimax in Assignment too was slow. We, in great detail, examined a Subtract Square game where the starting value was 9, and it turns out that there are many paths and branches that are exactly identical. Because minimax looks through every single path and does not overlook identical paths, it makes the function very slow, especially on starting numbers that are very high.
We discovered that there are a few ways of taking care of redundancy; the first thing we can do is check if the game are equal with immutable objects. If we used it on mutable objects, there is a chance that the client might change said mutable object and therefore will effect the reliability of the check. One method we could use to check equal game states is the __eq__ method, which we were required to write in both assignments so far. I know see why they can be so useful, especially in Assignment 2.
The next thing we can do is pruning, which is checking whether we can do better than a win, lose, or tie in the current game. If this is so, then the program will only look at the paths that will produce a game state that is better than the current available game states.
We discovered that there are a few ways of taking care of redundancy; the first thing we can do is check if the game are equal with immutable objects. If we used it on mutable objects, there is a chance that the client might change said mutable object and therefore will effect the reliability of the check. One method we could use to check equal game states is the __eq__ method, which we were required to write in both assignments so far. I know see why they can be so useful, especially in Assignment 2.
The next thing we can do is pruning, which is checking whether we can do better than a win, lose, or tie in the current game. If this is so, then the program will only look at the paths that will produce a game state that is better than the current available game states.
7 - More Adventures on Linked Lists
This week, we had the second term test in CSC148. This time, I put more on my cheat sheet to help me with Linked Lists and Binary Search Trees, which helped me write my functions during the exam. Overall, I thought it was a very fair exam. There was no class after the exam, so I have started to look over the final assignment, A3.
I am very glad that we now have a choice in what we want to do during this exam, because my partners and I had a lot of trouble with minimax and it was a very strenuous and lengthy process trying to solve it. I am very interested in doing Option B and figuring out how to count all of the game states as well as figuring out how to count repetitive games.
I am very glad that we now have a choice in what we want to do during this exam, because my partners and I had a lot of trouble with minimax and it was a very strenuous and lengthy process trying to solve it. I am very interested in doing Option B and figuring out how to count all of the game states as well as figuring out how to count repetitive games.
Saturday, 7 March 2015
6 - A Wild Linked List Has Appeared
The TA strike has commenced this week, so classes have been crazy this week. Nevertheless it's good to know Danny is an unrelenting force and term tests and assignments will go on as scheduled!
This week, we learned about a new data structure, linked lists. They are nodes that not only have a value, but also have a reference to another node that may also have a value and may also have a reference to another node and so on. This at first sounds confusing when written in words, but Danny told us to draw a picture when thinking about lists which really helped my understanding of this type of list.
As seen in the above image, the first two nodes in the linked list have both a value and a reference to another node. The third node, similarly, has a value but refers to None, indicating that this is the end of the list. Linked lists are recursive, and takes advantage of embedded references
To me, linked lists still seem a little confusing but I'm happy I know how to write them and such. I am hoping by the end of this week when I study them enough I'll understand why they are used in programs.
This week, we learned about a new data structure, linked lists. They are nodes that not only have a value, but also have a reference to another node that may also have a value and may also have a reference to another node and so on. This at first sounds confusing when written in words, but Danny told us to draw a picture when thinking about lists which really helped my understanding of this type of list.
To me, linked lists still seem a little confusing but I'm happy I know how to write them and such. I am hoping by the end of this week when I study them enough I'll understand why they are used in programs.
Monday, 2 March 2015
1 - Why Do Geeks Need To Know How To Write?
Many people underestimate the power of putting your thoughts down on paper. Although many math-oriented students want to avoid essay-writing by taking math and science courses, writing can also help with these courses. By simply writing your thoughts down, your mind begins to think more clearly about what it is being written about, causing you to write more and more. This, in turn, can help with clearing out muddled thoughts about a problem, such as figuring out how to solve an integral, or understanding where a bug could be in your code.
Scientists use it all of the time when researching and creating experiments. They write down their problem, possible solutions to solve this problem, and eventually get to the answer they have been seeking. Writing helps you track what you've discovered, what other problems you may have and may eventually lead to solving the problem at hand.
Writing is so important in math and science, which is why I find keeping a log in CSC148 very unique and different in a science course. I find the idea of keeping a log of sorts as the weeks progress very interesting because I have not seen it in any other math or science course so far.
That being said, the first few weeks of CSC148 have been going swell. This week, we extended our knowledge of different methods in a class and what we can do to enhance our classes. We also learned about inheritance, where when we are making another class, we can take whatever another class can do by inheriting it into the new class. It is very helpful, especially when you're adding different classes that you want to do similar, but different things.
Scientists use it all of the time when researching and creating experiments. They write down their problem, possible solutions to solve this problem, and eventually get to the answer they have been seeking. Writing helps you track what you've discovered, what other problems you may have and may eventually lead to solving the problem at hand.
Writing is so important in math and science, which is why I find keeping a log in CSC148 very unique and different in a science course. I find the idea of keeping a log of sorts as the weeks progress very interesting because I have not seen it in any other math or science course so far.
That being said, the first few weeks of CSC148 have been going swell. This week, we extended our knowledge of different methods in a class and what we can do to enhance our classes. We also learned about inheritance, where when we are making another class, we can take whatever another class can do by inheriting it into the new class. It is very helpful, especially when you're adding different classes that you want to do similar, but different things.
4 - Forestry in Programming Class
This week, we learned about making a Tree object in python. A tree is essentially an object that has nodes but also leaves and children. Nodes are values in a tree that can either be a leaf, which is a terminating node without children, or a subtree, which has both parents and children. Nodes are connected by edges and you can determine the length of a sequence of nodes by adding the number of edges in said sequence. Trees can be used in data that involves several possible outcomes, figuring out different combinations of objects.
When we want to find out something like how many leaves a certain tree has, it is usually very difficult to do since trees can sometimes be nested lists. Recursion, what we started to learn a week or so ago, can help with this. I am beginning to see how recursion can be helpful in programming, especially with trees.
I participated in an in-class example with a couple of friends. It first started off with two people standing up in the first row; they were the "roots" of the in-class "tree". Then those two "roots" can choose to have one or two "children", which they would indicate by pointing to people in the row behind them. Eventually it got to me and I was able to choose my "children" and so on. Then, Danny asked us to do a "search" by asking our "children" if their birthdays fell on the day he called out. If both original roots didn't find anyone with said day, they would "return" false. We did this until we found a day that at least one person had a birthday on, the original "root" would "return" true. This group example showed us how recursion and searching worked in a tree, which helped me understand recursion and trees a lot better.
When we want to find out something like how many leaves a certain tree has, it is usually very difficult to do since trees can sometimes be nested lists. Recursion, what we started to learn a week or so ago, can help with this. I am beginning to see how recursion can be helpful in programming, especially with trees.
I participated in an in-class example with a couple of friends. It first started off with two people standing up in the first row; they were the "roots" of the in-class "tree". Then those two "roots" can choose to have one or two "children", which they would indicate by pointing to people in the row behind them. Eventually it got to me and I was able to choose my "children" and so on. Then, Danny asked us to do a "search" by asking our "children" if their birthdays fell on the day he called out. If both original roots didn't find anyone with said day, they would "return" false. We did this until we found a day that at least one person had a birthday on, the original "root" would "return" true. This group example showed us how recursion and searching worked in a tree, which helped me understand recursion and trees a lot better.
Sunday, 1 March 2015
3 - Recursion, Nested Lists, and Tracing, Oh My!
Last week, we learned about this new method of solving programming problems called recursion. I am still not too keen on it because it sounds so confusing. Defining a function in terms of said function? I can't seem to wrap my head around it no matter how many turtle fractal drawings I see.
I understand the general form of it and how to trace it but I would definitely like to understand recursion and how it works in order for me to do well in not only the 148 exams but also in future programs I might need to write.
This week, we had our first term test for the class. It was only three questions but they were worth a lot of points and there was a lot of points you could lose for many simple things like indentation or not writing the correct __init__ method and of the sort. I am very grateful for the loose-leaf "cheat sheet" we were allowed to write because it definitely helped me write my classes and methods during the exam. Overall, I thought the exam was fair and manageable.
I understand the general form of it and how to trace it but I would definitely like to understand recursion and how it works in order for me to do well in not only the 148 exams but also in future programs I might need to write.
This week, we had our first term test for the class. It was only three questions but they were worth a lot of points and there was a lot of points you could lose for many simple things like indentation or not writing the correct __init__ method and of the sort. I am very grateful for the loose-leaf "cheat sheet" we were allowed to write because it definitely helped me write my classes and methods during the exam. Overall, I thought the exam was fair and manageable.
Subscribe to:
Posts (Atom)