In week 8, we learned about a new data type called linked lists. Python has a built in data type called list, where data can be stored in a specific order. There are many methods for the class list which allow one to add, remove, sort, and analyze data within the list. Data at any position in the list can be mutated or manipulated with the correct usage of list methods.
In contrast, linked lists can also store different types of data, but their use is very different. For linked lists, two classes are used, the node class, and the linked list class. The node class refers to a single point of data within the list, and the linked list organizes a collection of nodes into the linked list by assigning one node as the front, and another as the back. The way the data is connected is that each node has a property "next" (or .nxt) which points to a new node. Each node is referred to by another node, and refers to a new node unless it is the beginning or end of the linked list. Because of the structure of linked lists, a lot more work must be done to use the data in a linked list as compares to a list. To add data in the middle of a linked list, one must change the .nxt of the node before, and use the .nxt of the node to be added to add to the list properly. Additionally, to access data in the middle of a linked list, one must walk through each node in the list until the desired node is available. Recursion must be used for some methods with linked lists.
So far, I don't see the use of linked lists. It seems like everything they can be used for, the built-in list class can also do, and often times can do more efficiently. I can't think of a specific type of problem or data where a linked list would be the ideal class to use. Since recursion must be used for some methods, and others have to access many unneeded nodes before finding the desired node, the runtime for linked list methods would be significantly longer than for lists if one is using a large set of data. I'm curious to see if we revisit linked lists before the end of the course, and to find out if there is a type of problem which this data type is optimal for.
Sunday, 15 March 2015
Sunday, 8 March 2015
Impressions of Week 7
In week 7 we learned about the data class Binary Trees. To explain what a Binary Tree is I'll first have to explain what a Tree is. A Tree is a data class which we had learned about in previous weeks. Trees start at a single node which is at the "top" of the tree. This node contains some type of information, and also has "children", which are other nodes. These children also contain data, and can also have children of their own. Each node within the Tree functions as a starting node for its own "sub-tree", which can be accessed the same way as the original node. Trees are a class which can be used to give data a structural organization, and link certain pieces of data together (parent-children relationship). Additionally, all the data in a tree can be accessed via recursive functions, which go through the tree until there are no children.
A Binary Tree is a specific type of Tree, which has the unique property that each node has a maximum of two children. This gives the data a more organized structure than a normal tree which facilitates some specific functions. Two examples we were shown in class are Binary Expression Trees and Binary Search Trees. With Binary Expression Trees, each interior node (a node with children) is an arithmetic operator, and any leaves (nodes without children) contain numbers. A recursive function can then be used to evaluate the numbers using the arithmetic expression until one reaches the top of the tree. For Binary Search Trees, each node contains a number, and the left child is always less than the value at that node, and the right child is always greater. This allows for numbers to be searched for very quickly.
Binary Trees seem to be a very useful and efficient way to store data. By limiting the number of children to two, Binary Trees have a much more rigid structure than normal trees. This allows for efficient storage and retrieval of data. However, though they are efficient, Binary Trees are only useful for very specific sets of data. For example, Binary Search Trees are incredibly efficient for searching a group of numbers, because with each step down the tree one can eliminate a significant amount of the remaining data. However, this class only works for a set of data containing only numbers, and is only really useful for searching data sets and related functions. Though Binary Trees are very good data storage systems, the fact that they are limited to specific types of data reduces their usefulness to a computer scientist.
A Binary Tree is a specific type of Tree, which has the unique property that each node has a maximum of two children. This gives the data a more organized structure than a normal tree which facilitates some specific functions. Two examples we were shown in class are Binary Expression Trees and Binary Search Trees. With Binary Expression Trees, each interior node (a node with children) is an arithmetic operator, and any leaves (nodes without children) contain numbers. A recursive function can then be used to evaluate the numbers using the arithmetic expression until one reaches the top of the tree. For Binary Search Trees, each node contains a number, and the left child is always less than the value at that node, and the right child is always greater. This allows for numbers to be searched for very quickly.
Binary Trees seem to be a very useful and efficient way to store data. By limiting the number of children to two, Binary Trees have a much more rigid structure than normal trees. This allows for efficient storage and retrieval of data. However, though they are efficient, Binary Trees are only useful for very specific sets of data. For example, Binary Search Trees are incredibly efficient for searching a group of numbers, because with each step down the tree one can eliminate a significant amount of the remaining data. However, this class only works for a set of data containing only numbers, and is only really useful for searching data sets and related functions. Though Binary Trees are very good data storage systems, the fact that they are limited to specific types of data reduces their usefulness to a computer scientist.
Sunday, 1 March 2015
Tuesday, 17 February 2015
Object Oriented Programming
Object oriented programming is a very useful tool for computer scientists. Python (and other languages) have built-in objects or classes which give the user simple data types to work with. Examples of these are integers, strings (which function as sentences), and floats (numbers with decimals), as well as more complex structures such as lists of objects, and dictionaries (one type of object is paired with another type or a list). Object oriented programming allows a user to create their own classes/objects, which can provide more detailed and user friendly programs. A programmer can also write specific methods for their own classes, which can also make these data structures easier to access and manipulate. These classes use the basic python built in data structures, but can combine them more easily, keeping all the data together in one convenient place.
An example of a user created class that we saw in lab was a Patient Roster for a doctor. This class was created with a setup for a dictionary of the actual patients, but also built in restrictions (gender ratio and maximum number of patients). Additionally, we wrote a method to add patients to our class which checked if the gender ratio or maximum number was violated before adding the patient. This eliminated a lot of steps that a user would have to take themselves when using basic data structures, and made things much more simple.
In addition to creating classes, a user can create subclasses, which are a part of the superclass. These subclasses will inherit the methods which are written for the superclass, and they can have separate specific methods written for themselves. An example of this we saw in lecture was the superclass Shape, with its subclasses Triangle and Square. Shape was initialized with a position, and had a method to change its position. These properties were inherited by both Triangle and Square, but they each had individual methods called draw and get_area, which were specific to themselves.
When a subclass inherits a method from a superclass, there are 3 things that can happen. The method can be: inherited, extended, or overridden. Normal inheritance was discussed above, where the method in the superclass works for the subclass. The method can also be extended, meaning it does everything it does in the superclass, but also some more. Lastly, the method can be overridden, meaning the method in the subclass is completely different than the one in the superclass.
All these properties of object oriented programming allow for a computer scientist to create very specific structures and methods. This specificity is extremely helpful for future use of the program, and one would not be able to replicate the specificity using the built-in Python data types.
An example of a user created class that we saw in lab was a Patient Roster for a doctor. This class was created with a setup for a dictionary of the actual patients, but also built in restrictions (gender ratio and maximum number of patients). Additionally, we wrote a method to add patients to our class which checked if the gender ratio or maximum number was violated before adding the patient. This eliminated a lot of steps that a user would have to take themselves when using basic data structures, and made things much more simple.
In addition to creating classes, a user can create subclasses, which are a part of the superclass. These subclasses will inherit the methods which are written for the superclass, and they can have separate specific methods written for themselves. An example of this we saw in lecture was the superclass Shape, with its subclasses Triangle and Square. Shape was initialized with a position, and had a method to change its position. These properties were inherited by both Triangle and Square, but they each had individual methods called draw and get_area, which were specific to themselves.
When a subclass inherits a method from a superclass, there are 3 things that can happen. The method can be: inherited, extended, or overridden. Normal inheritance was discussed above, where the method in the superclass works for the subclass. The method can also be extended, meaning it does everything it does in the superclass, but also some more. Lastly, the method can be overridden, meaning the method in the subclass is completely different than the one in the superclass.
All these properties of object oriented programming allow for a computer scientist to create very specific structures and methods. This specificity is extremely helpful for future use of the program, and one would not be able to replicate the specificity using the built-in Python data types.
Sunday, 8 February 2015
In the last week, we learned about recursion, recursive functions, and how to trace the action of a recursive function.
Recursive functions are functions which use themselves within their own definition. At first it was a bit of a weird concept to wrap my head around. If someone were to ask for a definition of a word, and you used that word, it wouldn't help them at all, but with recursive functions they can actually work.
The key to how recursive functions work is the base case. We have been working with functions that deal with nested lists (lists inside lists), where the base case is anything that isn't a list. The code written splits the cases into 2 options: if it encounters a list it uses itself on the list and returns an output (for example, tracking the items in the list), and if it encounters anything else it does something (usually returns a number, like 0 or 1). This non-list item is the base case for functions dealing with lists.
What helped me understand how recursion works was actually tracing the action of the function. To trace how the function works, you start with the base case, a non-list. The function acts on the base case to do something, and then returns that. Then you go onto the next simplest case, a list of depth 1. When the function acts on the list, it calls itself on each item of the list. Since all the items are the base case, it performs its action on each of them, which then allows it to give an output for that list. Then if we look at the next simplest case, a list of depth 2, we see that once we enter the list, the remaining items are either lists of depth 1 and non-lists, both of which we know the output for since we already traced them. This can continue to infinitely complicated levels, or infinitely nested lists, because we can always trace them down to a base case, and then work backwards to get the output.
Talking about how recursion works can be very abstract and confusing. I'm sure my description of how it works has been vague and hard to follow, but that was how I felt while learning it. The act of tracing through how the function works was the key to understanding recursion. Simply walking through the steps from the base case upwards will demonstrate how the function works, and facilitate understanding.
Recursive functions are functions which use themselves within their own definition. At first it was a bit of a weird concept to wrap my head around. If someone were to ask for a definition of a word, and you used that word, it wouldn't help them at all, but with recursive functions they can actually work.
The key to how recursive functions work is the base case. We have been working with functions that deal with nested lists (lists inside lists), where the base case is anything that isn't a list. The code written splits the cases into 2 options: if it encounters a list it uses itself on the list and returns an output (for example, tracking the items in the list), and if it encounters anything else it does something (usually returns a number, like 0 or 1). This non-list item is the base case for functions dealing with lists.
What helped me understand how recursion works was actually tracing the action of the function. To trace how the function works, you start with the base case, a non-list. The function acts on the base case to do something, and then returns that. Then you go onto the next simplest case, a list of depth 1. When the function acts on the list, it calls itself on each item of the list. Since all the items are the base case, it performs its action on each of them, which then allows it to give an output for that list. Then if we look at the next simplest case, a list of depth 2, we see that once we enter the list, the remaining items are either lists of depth 1 and non-lists, both of which we know the output for since we already traced them. This can continue to infinitely complicated levels, or infinitely nested lists, because we can always trace them down to a base case, and then work backwards to get the output.
Talking about how recursion works can be very abstract and confusing. I'm sure my description of how it works has been vague and hard to follow, but that was how I felt while learning it. The act of tracing through how the function works was the key to understanding recursion. Simply walking through the steps from the base case upwards will demonstrate how the function works, and facilitate understanding.
Wednesday, 4 February 2015
Overview of the First Couple weeks
So far this course has been a lot different than I expected. I took CSC108 last semester and I was expecting a similar type of course. However, CSC148 is much different in 108 in the teaching style and the expectations of the course, which has been an interesting change.
CSC148 is run much differently than CSC108 was. I really enjoyed the "inverted classroom" method of teaching, where the course content was introduced in videos before the week, and the lecture time was spent on review and questions about the material. Additionally, the exercises after the videos at the end of the week were a good way to reinforce what we learned in class. This was a good way to teach the basics of python and keep us using it, which seemed like a good way to introduce a completely new subject to people. However, CSC148 is a very different course. We have more standard lectures, no videos, and no quizzes to keep the material fresh. Though it runs like a more traditional course, after taking 108 it feels strange for a computer science course.
One of the main differences I've found so far is that things are a lot more abstract. For CSC108, there were very specific answers which were expected and we were provided with a lot of help to lead us in the right direction. The best example of this is the starter code and instructions given to us for assignments. However, for CSC148, the first assignment had vague instructions and no starter code. This was a big shock to me, and at first I didn't know where to start. However, at the end it felt really satisfying to have built the entire program from scratch with my partner, knowing that the end product was entirely our work and ideas.
So far I would say I've enjoyed the course, and I hope that I continue to learn and improve my computer science skills.
CSC148 is run much differently than CSC108 was. I really enjoyed the "inverted classroom" method of teaching, where the course content was introduced in videos before the week, and the lecture time was spent on review and questions about the material. Additionally, the exercises after the videos at the end of the week were a good way to reinforce what we learned in class. This was a good way to teach the basics of python and keep us using it, which seemed like a good way to introduce a completely new subject to people. However, CSC148 is a very different course. We have more standard lectures, no videos, and no quizzes to keep the material fresh. Though it runs like a more traditional course, after taking 108 it feels strange for a computer science course.
One of the main differences I've found so far is that things are a lot more abstract. For CSC108, there were very specific answers which were expected and we were provided with a lot of help to lead us in the right direction. The best example of this is the starter code and instructions given to us for assignments. However, for CSC148, the first assignment had vague instructions and no starter code. This was a big shock to me, and at first I didn't know where to start. However, at the end it felt really satisfying to have built the entire program from scratch with my partner, knowing that the end product was entirely our work and ideas.
So far I would say I've enjoyed the course, and I hope that I continue to learn and improve my computer science skills.
Thursday, 22 January 2015
The main question for this first blog post is: Why should geeks write? In my opinion, there are two main reasons why geeks should write. Firstly, for their own benefit, and secondly, for the benefit of others.
Writing is a great form of self-expression. Writing allows you to organize your thoughts and opinions, and put them in a place where you can have access to them again in the future. This allows you to better understand your own thoughts and opinions by having a collection of posts about them. Understanding yourself better is something that all people could benefit from, including geeks. Additionally, writing is something that many geeks don't do on a regular basis. By writing in something as simple as a blog, it helps broaden your horizons, and make you a better communicator in general.
In the prompt for this assignment, it was mentioned that writing is something which is done in the humanities, and is almost the opposite of what is done in computer science. But this itself is the reason why more geeks should write. If the only people who write are those interested in humanities, then a significant amount of our written work would be from people who are similar. Geeks have a different perspective on the world, different experiences to share, and different approaches to life. These are things which should be shared with the world, to give people different views. Additionally, many people don't know much about computer science, even though computers are a part of everyday life now. Even if they only write in the most simple terms, writing about computer science could allow people to understand better something which they use every day.
Broadening horizons and giving people different experiences is always a good thing. If a geek writes a blog, it broadens both their own horizons, as well as those of the readers.
Writing is a great form of self-expression. Writing allows you to organize your thoughts and opinions, and put them in a place where you can have access to them again in the future. This allows you to better understand your own thoughts and opinions by having a collection of posts about them. Understanding yourself better is something that all people could benefit from, including geeks. Additionally, writing is something that many geeks don't do on a regular basis. By writing in something as simple as a blog, it helps broaden your horizons, and make you a better communicator in general.
In the prompt for this assignment, it was mentioned that writing is something which is done in the humanities, and is almost the opposite of what is done in computer science. But this itself is the reason why more geeks should write. If the only people who write are those interested in humanities, then a significant amount of our written work would be from people who are similar. Geeks have a different perspective on the world, different experiences to share, and different approaches to life. These are things which should be shared with the world, to give people different views. Additionally, many people don't know much about computer science, even though computers are a part of everyday life now. Even if they only write in the most simple terms, writing about computer science could allow people to understand better something which they use every day.
Broadening horizons and giving people different experiences is always a good thing. If a geek writes a blog, it broadens both their own horizons, as well as those of the readers.
Subscribe to:
Posts (Atom)