#csc148

We are in Final period now! We are going to take CSC165 Final exam tomorrow, it really took me and my group members quite a lot time to review this course. I am quite familiar with Big O and Omega, Proof by contradiction and contrapositive, etc. Since I got 89% in the CSC165 midterm, and satisfied Quiz results, I am confident to get 90% in the Final grade! Wish me good luck, LOL!

The last week of this semester, the topics of this week are ‘hash tables’, ‘tracing code’, and ‘aliasing’. These contents are not that hard. The most thing I care about is the Final Exam. It will be held on April 26th. CSC148 is the last Final I will deal with, and it is the only exam in that week, which means I have quite enough time to review all over the contents of the whole semester again.

So…..the time has come! It’s almost time to test all my knowledge I gained in this course in the final exam! This last week we have learned about hash tables and Big O. FINALLY we are incorporating the material we have been learning in CSC165 and everything suddenly makes sense to me (Big O, running time complexity). It’s been a little hard to focus on the hashing material this week with all the distractions from finals and last assignments. From my understanding, a hash function is a function that takes input of a variable length sequence of references to objects and converts it to a fixed length sequence. It is a one way function. This means if f is the hashing function, calculating f(x) is pretty fast and simple, but trying to obtain x again will take years. The value returned by a hash function is often called a hash value. Most of the time a hash function will produce unique output for a given input. However depending on the algorithm, there is a possibility to find a collision due to the mathematical theory behind these functions.

Once you have hashed an object to a number, you can easily use part of that number as an index to a list to store the object or something related to it. If the list is of length n, you might store information about the object A at index hash(A) % 0.

Dictionaries are implemented using hash tables! These tables are sort of difficult to understand (for me) but maybe staring at the example codes for a bit will help me, then I can implement some of the class examples again such as the birthday paradox one.

I am also planning my review for the final exam! I am going all out with studying this time… I have made enough mistakes with past midterms and quizzes that I should be able to overcome now! I’m definitely going to go to the last few office hours for help and do a study group! Of course, I will do a lot of practice with past labs and assignments as well.

This would be the final week of this term, and I am very excited to look forward to taking my final exam of this course! No I am just kidding actually.

Hash gives most outputs in python a specific code name, but it is not 100% unique, since you cannot hash everything. Once you started the process of a hash table, there is only a few of the numbers who are able to find the exactly correct position of themselves, on the other hand, there are some number who need to search downwards for an empty spot to fit in, and if they there is no empty spot till the very end of the table, they should go back to the beginning and repeat this process, until they finally get a spot.

The Big-Oh notation is more like a running-time calculation process, as it finds out the running-time for every loop in the function and sum them all up. However, since the general running-time of a single loop could be stated as “n”, and “n²” if there is another inside this loop, therefore when we count the final result of the Big-Oh notation, we usually count the subject with the highest number of power numbers, since the rest of the subject would be just too small compare to the number with powers.

Assignment II was indeed a tricky project to work on so far, it needed really strong logical thinking in order to sort every game out in your own mind by using binary trees, linked-lists, and recursions. Especially recursion which requires the programmer to have a farseeing view of where the program will be going and what is it going to be looked like after the first run through the program. It is one of the hardest topic to me throughout this entire term and really require the longest study time onto it in order to achieve the same goal as I did in other topics.

Also, we have started to pay more attentions on the running time to the algorithms in python, which is the same as what we are doing in the other computer science class 165. We talked about the time required for three different main sorting methods: Bubble, Selection, and Insertion, as well as some other sorting methods such as Quick Sort, which actually takes the shortest time to sort a list which contains only integers.

The topics of this week are “Recursion Efficiency”, “Searching”, “Height Analysis”, “Sorting”, and “Big-Oh”. So all of those just come down to an end of running time problems of the programs. The recursion functions sometimes might run out of stack space as in a program, just as the same as what we have seen in the “puzzle tool” file in assignment II, and they started to introduce this idea by calculating the program running time in the assignment files --- yes, sometimes it really takes a long time to generate the answer of a game.

So the memory that it takes for a program to run can easily be varied by changing just a line of code of two, for instance, the “list” algorithms cause way much more time than the “dictionary” and “set”, since the “list” objects are actually ordered, this way it records more information than the other random algorithms.