Week 12: Dictionaries and Exam Review

In class this week we looked over how dictionaries work and have constant time, as well as doing some exam review. Having a dictionary as a built-in data type is a fairly uncommon feature; as seen in the lecture, the way they work is complex. Having this ADT built in is fairly convenient for the programmer; otherwise, they would have to code it themselves. Dictionaries can find and insert items in constant time, meaning that the number of elements it contains has no effect on runtime. Lists also perform these operations in constant time, but they do not have option to have strings (or other immutable data types) as keys. The way a dictionary indexes its data is by hashing (giving a piece of data a numerical value) the immutable key values (mutable key values will not work because their hash values change if their are modified). If there are two different items with the same hash value, then a linked list is used, so no matter what, finding or inserting data will have a constant runtime value.

We reviewed all the major topics covered in this course during the exam review: ADTs, class design and inheritance, testing, exceptions, Python idioms, recursion, runtime analysis, linked structures (trees and linked lists) and sorting. I personally think that recursion is the single most important concept in this course (which is why it has been emphasized so frequently) because of how powerful it is. The sorting algorithms and the linked structures we examined all utilize recursion, so it is clearly a fundamental concept.

Overall, I enjoyed this course, although I did find it difficult at times. I liked how we focused more on abstract concepts than on details specific to Python (like CSC108 did). There was nothing to memorize; critical thinking was more important. The grading and marking schemes were pretty fair as well. The weekly labs certainly aided me in understanding the course material. I think I'm a better programmer (with enough knowledge to at least learn the basics of other languages) as a result of this course. 

This comic has essentially nothing to do with what I wrote above.

(http://xkcd.com/936/) 

Week 11: Sorting and Efficiency

Sorting a list or array of items is a common problem in the world of computer science and can be solved in various different ways. Each method of sorting a list has its advantages and disadvantages, as well as efficiency. Quick and merge sort were two algorithms we looked at last week (see my last post for more detail), both of which used recursion and both which had a worst-case runtime of O(n log n) (given that quicksort is modified, otherwise the worst-case runtime is O(n^2)). Merge sort recursively splits the list into sublists and then merges them to produce a final sorted list. Quicksort chooses a pivot (any item in the list, it could be random) and moves the items to the left (items less than the pivot) and right (items greater than the pivot) sublists and then recursively repeats the process. The reason why recursion has been stressed so frequently in this course is becoming more clear; recursive sorts and searches have a better runtime than other sorts. Bubble (compares each item to the next), insertion (inserts items into a sorted sublist) and selection (selects the largest element and moves it to the end) sorts all have runtimes of O(n^2) because of the repeated passes on the list, and hence, are not as efficient. Sorting is an important and common issue in computer science, so making these algorithms

run as fast as possible is important.

Timsort is the sorting algorithm built into Python. It is meant to perform quickly and with various sizes of data. This sort has elements of both merge and insertion sorts. The worst-case runtime is O(n). The implementation is fairly advanced; it uses insertion sort on (relatively) small sublists, which are already ordered, and merges the rest of the data. The procedure is adaptive and depends on the size of the list, so the way this sort orders data varies for different lists.

Parenthetically, the term test this week was much more difficult than the first. I've also noticed that the labs gave gotten more intense over the last few weeks.

xkcd's explanation of terrible sorts. Panicsort resembles my style of coding.

https://xkcd.com/1185/

Week 10: More Sorting and Runtime

This week we looked at more efficient sorting algorithms. As I suspected, faster sorting methods do make use of recursion. The two algorithms that we examined were quicksort and merge sort. Quicksort lives up to its name; it is very fast and takes roughly O(n log n) times on average, much better than O(n²) (for selection sort). The worst case is O(n²), but this case is rare. The algorithm works by first choosing a pivot (it's easiest to choose the first item in the list, but to avoid the worst case runtime as much as possible, we modified it to take a random number in the list). The list is then rearranged so that the elements are either greater than or less than/equal than the pivot element. The two sublists are then recursively sorted in the same manner.

Merge sort is another sorting method which I have seen before, but not using recursion. It also has a runtime of O(n log n). It works by splitting the list into two parts (more or less of equal size, depending on if the number of elements is odd or even), and recursively sort each of these sublists, and merge the two results.

This week we also talked about ways to approach the second assignment. I think I've more or less have my code working. I didn't fully agree with the class design that was given to us, I feel that the way I did it was simpler (if I did it right). But I digress.

Explanation of quicksort. 
http://www.nczonline.net/blog/wp-content/uploads/2012/11/quicksort_21.png

Week 9: Runtime Analysis

This week we mainly focused on algorithm runtime analysis, which is an estimated amount of “steps” (lines of code) which an algorithm takes to complete a task. This analysis is not specific to any programming language, and an algorithm can be mathematically proven to be O(x) (where O means big O and x is some function or a constant). This provides an upper-bound (ie. worst-case runtime) on an algorithm or function. For example, the binary search tree example we went over in class had an approximate runtime of O(log n) (instead of n, so it was faster). The reason that we have been focusing on linked and recursive structures (such as binary search trees) is that they often can reduce runtime and are more efficient.

We also went over the selection and insertion sorts and analyzed their upper-bounds. These sorts are not very efficient, and I have a feeling that recursion will be a key element in other, more efficient sorting algorithms. I already took CSC165 as well as CSC108, so most of what we did in class this week was review for me. I started the second part of the second assignment, as well as finished the third exercise this week. 

 

Some sort of runtime analysis for a merge sort algorithm. 

(http://i.stack.imgur.com/j1mZV.png)

Week 8: More Linked Structures

This week we went over more linked structures (and hence, more opportunities to use recursion), specifically linked lists and binary trees. These ADTs made sense to me, and were somewhat similar to regular trees. The idea of wrapper classes and the difference between __str__ and __repr__ methods was also discussed. A linked list has a node (with a value) which points to another object (another linked list, until the end, where the value is None), and we made a wrapper class to keep track of the size and the front of the list. As seen in last weeks lab, adopting these ADTs and wrapper classes can be used to cut down on runtime and make programs more organized.

A binary tree (and the binary search tree wrapper class) is a tree with only two children, so the children are represented as left and right. In this instance, a __str__ method that is different from __repr__ is useful for the programmer to visualize the structure. I think I'll do a similar thing for the second part of the second assignment. A traversal was used for the _str method, and recursion for the _insert method. Binary trees are another way which runtime can be reduced.

I was pleased with my result on the term test, and I finished and understand the first part of the assignment. I've already done some code for the next part.

A graphic of a linked list

http://www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists/ll2.gif

Week 7: More Recursion

I think that the most important and most focused on concept of CSC148 has so far been recursion. This is a powerful way of approaching programming which I was not previously aware of. However, I think that recursion is an intuitive concept which everyone can grasp. In computer science specifically, recursion is when a function or method calls itself in order to achieve a task. Recursive functions generally have a base case which tell them what to do when a certain point in the execution has been reached and recursion is no longer necessary (as to prevent infinite recursion). A simple way of understanding recursion is to look at an visual example of it, such as the one I provided below. In very basic terms, something that is recursive contains itself within itself.

Recursion is so useful because of how flexible it allows code and functions to be. In the nested depth and sum list examples we worked on in class, the functions took the nesting depth and sum of the list, regardless of how many nested lists there were. Without recursion, these functions would only work for certain configurations of lists and nested lists. Some functions or formulas cannot exist without recursion, as seen in the first assignment, where the formula for the minimum amount of moves called itself, as well as in the function which solved a three stool Hannoi game. Recursion also saves time; writing a base case and a general case is much less time consuming than thinking of every possible input or combination. Trees and linked lists (as seen this week) are ADTs which are recursive, so certain methods written for these data types naturally involve recursion and cannot be properly used without it.

I now feel that I understand recursion fairly well. The term test written this week seemed to not be overwhelming for me, and I also started the second assignment, but am somewhat confused about how to approach it. The linked list examples that we went over in class made sense to me and I saw how they are recursive in nature.

Recursion explained through a demotivational poster.

http://img.photobucket.com/albums/v394/civilwarman/recursion.jpg

Week 6: Trees

This week we mainly discussed trees (an abstract data type) and designed methods to work with the trees and their data. The example we did in last weeks lab (with the SearchList) makes more sense; I found that seeing just the nested list representation of a tree was not as useful to me as a graphic or the __repr__ representation for a Tree object that we coded in class. A tree basically is a hierarchical data structure with a “parent” node (the origin node at the very top is called the root node) on top with children (maximum of two children in the binary trees we looked at), and those children may have children as well. The parents/children are connected with edges, and each node (parent or child) can have a value/label associated with it. There is only one unique path between nodes and the height of the tree is the maximum number of edges between the root node and the bottommost one. The traversal methods that we coded were confusing to me at first, but I found out that these methods simply return the data within the tree in a certain order (preorder or postorder).

There is clearly an abundant use of recursion when working with trees, so the examples that we worked on in class helped me practice writing more recursive code. The readings posted on the website also made me realize the uses of trees. I finally finished the first assignment, with the recursive methods to solve the four stool Hanoi problem working at last. Also, my GUI also works properly now. I managed to code the bonus problem, and hopefully I did that right (the tests pass). The assignment was a challenge but it was an interesting problem and it helped me understand recursion better. I've also looked over past term tests and am beginning to review the course material more thoroughly. 

 

Graphic representation of a tree data structure. 

http://www.powayusd.com/pusdtbes/images/tree_example.gif

Week 5: Hanoi Recursion and Scope

This week we went through a 3 stool recursive Tower of Hanoi solution, as well as going over scope. The Hanoi algorithm we went through really helped me understand the problem and I started working on a 4 stool recursive solution, which works somewhat so far, but getting it to work properly is proving to be fairly difficult. It also reminded me of that scene in Rise of Planet of the Apes when that ape was solving the problem. I think Danny was right when he said that the last 10% of the problem takes 90% of the the work; I'm done basically everything else for the first assignment. I feel fairly confident after another recursive example and the lab we did this week.

As my lab partner CrustyBlogger notes, the labs in this class are significantly more difficult than the ones in CSC108. The labs do help me learn the material and our lab partnership is an efficient one, and this week with the addition of Infernvs to our group, we were elevated to the status of dream team. Infernvs notes in his SLOG that the concept of OOP is a “trivially simple concept to explain”, which I agree with. His analysis of the Sierpinski triangle was pretty intense and went way over my head. I found I understood the scope concept fairly well because I have come across this idea before while learning Java. The prefix global allows a variable/function to be accessed throughout the class/file and nonlocal allows for access exclusively in the module (function). I already see the potential uses of this and I may implement it into my A1 code.

 

                         Hanoi is so simple an ape can solve it.               (http://static1.wikia.nocookie.net/__cb20120530021256/planetoftheapes/images/6/61/Bright_Eyes_2.jpg)

 

Week 4: Recursion

This week we did more examples of recursion, along with an explanation of the first assignment. I now fully understand what the assignment is about and what we are expected to do, and I started writing the code for it this week. This is definitely an interesting example and I like how the included GUI is very interactive. I think the console based version would not be user-friendly. I also like how the GNU General Public Licence is included in the starter code. I also finished the second exercise, which I did not find overly difficult, and now I'm comfortable with using exceptions.

The examples we did in class (nested depth and drawing with a turtle) strengthened my confidence in understanding recursion. Tracing the code also helped me, and made me realize that everyone has an intuitive understanding of how recursion works; personally I just find the application of it into computer science the difficult part. The turtle drawing example was very interesting, and showed the connection recursion has with art. This made me think of M.C. Escher's recursive and mathematical paintings.

I think if I start writing recursive functions in exercises and assignments I'll fully understand this concept. However, after numerous examples done in class I feel fairly comfortable with the material.

 

Drawing Hands by M. C. Escher, 1948, Lithograph.

(http://www.merretts.info/fullsize/escher/escher_hands.png)

Week 3: Object-Oriented Programming

So far the focus of CSC148 has been on object oriented programming (OOP) and recursion. I programmed in Java for 2 years in high school so I'm already familiar with the OOP concept as well as inheritance, but not with recursion. My interpretation of the OOP concept is that it is a style of programming that focuses on creating classes (and objects of these classes), and both classes and objects are abstract data types (ADTs). A class contains methods for operating on/modifying data, while an object is a representation of a class which contains data and can access the classes methods. Inheritance allows a subclass (the “child” class) to inherit some or all of the methods of the superclass (the “parent” class), as well as being able to add new methods or modify/override superclass methods. Recursion involves a function calling itself to increase flexibility and efficiency. These OOP concepts are very efficient and can save both time and code. The flexibility provided by creating custom ADTs is also very useful and has a broad range of applications.

So far, I am enjoying this course, mainly because the programming concepts that we are being exposed to can save a lot of time (I like how Danny emphasizes that laziness is one of the central concepts of computer science), and because the material is more complex that of CSC108. However, I did like the hands-on approach that the CSC108 lectures had, however I find that being exposed to many examples of OOP and recursion (like we have been) is also beneficial to me. What I will start doing is tracing more code and playing around with the posted example code to get a more complete knowledge of how to practically apply the theoretical programming concepts that we are learning. I study the posted readings, but often find them to be fairly intense and complicated. I should further benefit if I look over these more carefully and do whatever practice exercises that are found at the end of some of them.

Overall, I like this course so far and find that it is interesting so far without being overwhelming.

 

The xkcd interpretation of Python

(http://xkcd.com/353/)