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