Wrap Up (Week 12)

Today we learned about hash tables and how they are an efficient way to look up a list of items (their worst case complexities, if done ideally, is O(1)). Apparently, an application of hash tables are used in Python, called dictionaries. Perhaps that's why it's so fast to access a value with its key... However, it is almost impossible to not have a collision when storing data in hash tables, so we learned that Python uses both probing and chaining to handle to minimize such collisions. Both these techniques have setbacks of their own (trying to store more items can lead to worst case complexities of O(n) or even O(n-squared), which defeats the purpose of having hash tables!). I can't see how I'll be tested on this topic since we only went over this topic conceptually, but I never had trouble understanding this topic and was even piqued by this aspect of the course.
There isn't much I can talk about in the labs since we only looked at running times and algorithms of different sorting techniques. For most of the sorting algorithms we looked at, their worst case complexities are either n log n or n-squared. However, each sorting algorithm's run times might be faster or slower than each other depending on whether the list is sorted, unsorted, and/or reversed. Analyzing these best, average, and worst time complexities through their code irked me a little bit because I really had to understand how each sorting algorithm actually worked before I did that. I'll look over the code before the final.

That's it for me. It's been one fun SLOG. Hope my finals go well.

Old SLOG Review (Week 11)

I decided to revisit my very first course SLOG, and my experiences with CSC148 were quite different than what I originally expected several weeks ago.
Surprisingly, I didn't have to learn that much syntax to understand the main concepts in CSC148. Instead, most of the programming design concepts were pretty straightforward to understand, and applying that knowledge in the labs was really useful as well. ADTs were the most interesting to learn since I was able to implement it any way I wanted. However, learning the syntax would have been more beneficial when I was doing my assignments. Since there were some aspects in the assignment that relied on efficiency, I felt like writing more efficient code would have benefited me more. I know that higher-level computer science courses will rely on efficiency to grade our assignments, so coming up with different ways to solve the same problem is a very good skill to have.
I also said that in my first SLOG that making a blog would help me plan better. Writing my reflections certainly helped me organize my time a lot better, but I could have used it as a debugging journal. While I worked on Assignment 2, I had a lot of trouble trying to implement its functions, especially the depth-and-breath first search functions in the puzzle_tools file. Keeping such a journal would make me less likely to overlook trivial cases and help me look for other solutions, and that would have really helped me plan my 2nd assignment better.
In short, this course was pretty fun and this SLOG really helped record my experiences and opinions of it. However, I'm still skeptical of whether I want to do this as a career. Perhaps I'll look into a career planning center sometime in the future.

Algorithms and Assignment 2 [Week 10]

I recently got my midterm back and did pretty well. The only reasons I lost a couple points was for overlooking some syntax errors in my code and misreading one of the questions where I was supposed to take care of one of the cases when writing the linked-list function. Those were only minor errors I had my midterm since I knew how to write the solutions for all aspects of the midterm. Luckily, these skills will come in handy for the final exam since I'll need that to fix my dud in Assignment 2.

Speaking of Assignment 2, I did have some major trouble trying to implement the puzzle_tools.py functions. I could figure out how to traverse the puzzle nodes iteratively through both searches, but I couldn't figure out how to make a unique path from a puzzle configuration to a solution (if it exists). 

To put it in picture terms (image above), I know how to print the path process from A to C in this picture (ABDFEC for example in depth first search), but after traversing the tree, I don't know how to get the actual path (AC in this picture). For the extension functions, I also forgot to put cases where the puzzles that are already solved should return no extensions for the grid peg solitaire and the word ladder puzzle. I assume that's why when I tried to run the puzzle_tool functions on those classes, the programs did not terminate. I'll have to clarify those problems in the interview part of Assignment 2. From now on, I'm going to organize my time more when a similar assignment like this comes up.

Other than that, algorithms and big-O's were not very hard to understand since in CSC165, we have already had a lot of practice tracing code to evaluate the worst-case complexities. I'll have to see more examples next lecture to get a feel for how CSC148 treats algorithm complexities.

Midterm 2 and Assignment 2 (Week 9)

The midterm was a lot easier than I expected. I really thought the professors were going to trick us by either telling us how to implement a certain type of tree traversal or extremely hard recursive functions, but the midterm was only testing us if we knew the general concepts and applications of linked lists and recursion. That made the test really fair. I had almost no trouble implementing linked lists and trees in the labs, so I was almost surprised when the functions we had to implement had extremely similar features to those in the labs. Unlike the first midterm, I had enough time to check my answers in the second midterm, but I can't be too sure of my grade in the second.
The question that interested me the most was when we had to modify a tree such that we had to swap its children. I've heard of using a dummy variable when you swap two variables with each other (since trying to assign one variable as the other one will overwrite the other one), so I decided to use that. Once I've taken care of that base case, the general case was pretty straightforward, which was doing the same thing for the left and right children (if the tree has any).
As for Assignment 2, implementing the two searches from the puzzle tools file seems extremely daunting; Luckily, it takes a lot of thinking and planning to actually carry these functions out. I'm going to break this down into smaller, more solvable tasks since that strategy actually worked the best for me when I try to implement the extensions for the grid peg and 15 puzzle. During the last lab, I've thought about how I would carry out both functions, but I haven't actually written them down yet, but it did involve using a variable that keeps track of what extensions have already been checked. Let's hope that when I run my functions, it doesn't run for too long. I've heard in a couple of Piazza posts that the grid peg solitaire or word ladder tends to run for at least a couple of hours...
Other than that, I have had no trouble implementing the binary tree functions, expect when deleting a node from a binary tree. I'll have to review that.

Recursion, Part 3 (ft. Binary Trees) [Week 8]

This week, we were able to get some experience with implementing certain functions of binary trees. I learned that there were four ways of searching trees instead of the two general depth and breadth search. However, there were three different ways of doing depth-first search, but I find pre-order search the easiest to understand. Perhaps I'll do the pre-order search when I'm implementing the depth-function search function for my 2nd assignment. As for the other functions, I found the general cases really hard to solve. I still wasn't able to get a lot of practice with binary trees, but I did find that drawing pictures of binary trees and working out each case helped a lot when getting some binary tree practice in the labs.
Luckily, implementing recursive functions for binary trees in the labs were nothing new to me since their implementations are pretty similar to making recursive functions for nested lists. I naturally found it intuitive since the difference between the base case and the general case for binary trees seems to be whether the tree has children or not, just like checking whether an element in a list is a list or not for making functions on nested lists. I'm going to assume that the midterm questions relating to recursion are much harder than those in the labs, so it might be similar to the ones presented in lecture.
At this point in the course, there really isn't any new concept we can learn, except for seeing more applications, which I'm pretty excited about. So see you soon.

Recursion, Part 2 (Week 7)

This week, we revisited the topic of recursion. There was nothing new about understanding or even designing recursive functions, but one thing that stood out this week was how recursion could be used to implement certain ADTs such as binary trees, the topic for this week's lecture. Sadly, we only had time to go over the terminology of binary trees, so we never had the time to actually see its implementation. The implementation part piqued my interest so much that I decided to do a bit of research on this particular ADT.
It turns out that like a typical ADT, we can implement binary trees any way we want in our code. However, what surprised me the most was how we could use recursion to search our tree: depth-first search, breadth-first search, you name it. Even though I still haven't gotten my feet wet on recursion yet, I find the applications of it really interesting, like how binary trees are used by computers to evaluate math expressions. I do feel like I'm going to use this application of recursion in one of my assignments, which might be pretty difficult.
Luckily, I'm going to get a bit more practice with recursion from the labs, but it all depends on how much effort I put into the actual concept itself. I've heard that learning recursion only comes with practice, and I'm still struggling to implement recursive functions. Perhaps I'll try to come up with a couple of examples and pseudo-code and see if tracing the code actually helps me come up with some common strategies to carry out such functions. I would like to see more applications to recursion, such as some new ADTs or other real-world scenarios.

Recursion (Week 6)

Recursion. It's a concept I've heard before in computer programming, where your implementation of a function calls the function itself one or more times in its body.

Recursion makes certain functions easier to implement, such as calculating the sum of nested lists or a factorial. It comes with two parts: the base case and the general case.

Tracing a recursive function seems pretty trivial to me, but designing a recursive function doesn't feel very easy. I always had trouble figuring out the general case, especially during the lecture exercises. Luckily, understanding recursion only comes with lots and lots of practice, and I plan to get a lot of that from looking at the example code or practice making recursion functions.

As for infinite recursion, I won't have trouble with that since figuring out the base case for recursive functions seems pretty easy to me, and base cases are termination conditions for recursive functions.

There was also a lab somewhere in the 6th week, but I don't think there was anything special there (other than learning about two built-in functions, zip and filter).