sorting, end of csc148

well, csc148 has come to an end. the only problem i have now is that most of the stuff in the practice exam we haven't seemed to have learned such as heaps and stuff. hopefully these practice exams aren't representative of the actual exam.

onto today's topic: sorting.

selection sort is when you find the biggest/smallest value of the list, and swap it with the first position. move the position up, and repeat. it has an big O of n^2 because it has to run through the list of n n times. since the entire list is processed to one value, repeated for n values.

quicksort is when you take a list, find a pivot, and split the list into 2 lists, one with values greater than the pivot, and one with smaller values than the pivot. the lists are then recursively processed, and then reassembled. since we're breaking a list of n values down to lists of length 1, the big O of quicksort is nlog(n)

finally, mergesort is similar to quicksort, because we're breaking down a list of n values to lists with length one. then we compare the lists, and then merge the lists based on value. if the top of one list has a greater value, then that is entered into the merged list first, and the comparisons continue until you have one list. likewise, similar to quicksort, the big O of mergesort is nlog(n)

i really enjoyed csc148. im glad that i took this over 108. the only thing now is to ace the exam and to get my assignment 2 remarked because the two mentioned errors earlier managed to chunk a huge mark off.

post term test 2

wooot 100 on term test two

hopefully my TA reads this before marking my assignment. it seems that looking over my code after looking at the report.txt generated on markus, i came to a conclusion

1. e should have been RegexTreeNode('e', []), rather than RegexTreeNode(' ', []). we're failing most of our tests because its complaining that its not exactly right.

2. our code processes the tree perfectly otherwise, except for one mishap: we didn't process the final outer brackets. so a regex statement like '(1|0).(1|0)' would be processed completely fine, but '((1|0).(1|0))' would not, because the outermost bracket would screw up the code. this is really disappointing because the code works fine otherwise, and its literally one line of code that fixes that problem, but we might lose a lot of marks because "the process doesn't work"

finally, some odds and ends in terms of processing the regex_match. for example, i thought e was a space, not an empty string, and some confusion on what starnode was and what it meant.

hopefully assignment 2 isn't that bad. our code works except for the two huge points mentioned above, which are killer.

test 2

the only thing that i find difficult about test 2 is big O notation, and how searching and sorting trees and lists have different times based on algorithm efficiency.other than that, binary trees and everything related to them are pretty self-explanatory. Danny did a really really good job of describing trees in detail and doing examples.

there wasn't an exercise, so nothing to comment on there.

assignment 2 was just handed in. hopefully all the test cases will be rational ones, not silly extreme examples, like 1********************* or 1|1******************************.

almost assignment 2 due date slog

i got a cherry blue mechanical keyboard over the weekend. its amazing. i will never go back to membrane keyboards ever :D.

finished up assignment 2 over the weekend. added in docstrings, changes variable names from temp1 temp2 and temp3 into something more descriptive. and overall just brushing up pep8 and style, because we initially went in hoping to just get it to work. now that it works, its all about style and making sure that our code is clear enough to whoever is reading it.

exercise 6 was similar to 5. new concepts, and some deciphering needed, along with a good knowledge base in how binary trees are built. the lab this week was challenging, especially the last bonus question. the first 2 were surprisingly a breeze, but the final question was really challenging. we were close, but we couldn't finish it in time.

also i gave my test to Danny to remark because I lost three marks for not having a test case that showed that the FunctionalList remained unchanged, when I clearly had one. how long does a remark take? I gave it back to him the tuesday after getting our tests back, and haven't heard about it since. I WANT MY MARKS YO.

exercise 5, assignment 2

Exercise 5 kept giving me errors and I could figure out why until I realized that
1. not returning anything gets you nowhere
2. resetting your data arrays is bad
3. not appending data is bad
4. reviewing rampup notes is good

after i facepalmed for at least a day i got e5a and e5b to work. success.

assignment 2 is up, and im currently in the process of deciphering what it wants. it would have been more helpful to include more test cases, as some of the test cases are sort of confusing at first glance. im currently trying to find the root node in regextree, which i cant seem to logic out.

in class its more recursion and nodes, which is relatively straightforward material. sometimes i wish that I could have more lab time to do assignments rather than the labs which are relatively simple and easy to implement. or maybe because my lab partner is a genius.

post term test 1

i did not do as well as i thought no term test 1, mainly due to careless errors like returning a list instead of a functionallist. otherwise the term test was straight forward. hopefully ill argue back some marks.

today we learned about linked lists, which are nodes with a value and a pointer to the next node. i dont have that much experience with linked lists, but coming from Java i know that linked lists in java are much more efficient than regular arrays, as adding a value into a linked list is simple changing the pointer of the previous node, and pointing the new added node to the next one. otherwise you would have to split the array and add them together with the new data sandwiched in between, which is terribly inefficient.

hopefully the lab will have something with linked list for us to practice on.

so apparently this was supposed to be a weekly thing, but i didn't actually read it until today.

 so our group finished part 1 through 3. part 3 was particularly infuriating as i forgot to update x and y coords for the moved cheese, so the cheese would move back to the original stack and i would get mad. but otherwise the assignment was quite straight forward. as long as the logic was reasoned out the code fell into place nicely.

RECURSION
the concept is simple, just actually coding it is a big pain and takes longer than one would expect. in recursion, not only do you run the risk of having not working code, if coded improperly a recursive method wont be able to find its terminating case, thus causing a dreaded infinite loop. the problem might lie in having a method inside rather than outside an if statement, or an x value not going to 0, but regardless i find troubleshooting recursion to be a little bit more tricky than regular non-recursive code as you need to theoretically run it in your head. overall this is useful for us computer scientists because in the long run recursion uses less memory and is more efficient.

OOP
Object Oriented Programming is a godsend. I dont know where i'd be without OOP. OOP is like methods. once you learn how to code methods, you never go back. its so great. OOP allows for custom data types (classes) and stores variables associated with them. so instead of having 300 x and 300 y values to track, you can track 300 Cheeses instead and pull each unique x and y coordinate. this is a must for computer scientists because of its efficiency and ability to optimally code things not hard coded into the programming language.