ITSCALLEDCSC148

A carbohydrate lover running a SLog. Welcome to CSC 148. 

[itscalledcsc148-blog]

SLOG # 11: Big O, back to the basics

Here comes efficiency—It’s time to be professional. Gone are the days of mindlessly slapping code together and only focusing on the fact that it worked—We were CSC148 students, and it was time to take that step into more effective and streamlined maturity.

After getting an introduction to efficiency last week, we got down to the nitty gritty this lecture. There’s two ways of measuring efficiency; first is by time, and second is by memory. However, we’re going to shove memory to the side a bit this week—Time was of the essence. How fast did it take a code to execute? And how could we time it?

This is where Big O comes in.

If you want to be a pro, you got to know the lingo. What in the world is Big O, a young, naïve, two weeks ago me may have asked. Present me can now answer with confidence—It’s a way of measuring how long an algorithm takes to run. O(1) has a constant run time, and O(n2) has a run time relative to n. What’s faster? Constant ( O(1) ) always is, and is considered to have the lowest runtime, while Factorials ( O(n!) ) are atrocious with getting anything done in an acceptable amount of time, the old men they are.

But Bread, you may be asking. “What about in the case the algorithm for function A is f(x) = 6000, and the algorithm for function B is g(x) = 2x? When x is 1, Function B, which is O(n), would be faster than Function A, which is O(1), right? Your logic doesn’t make sense!

Dear grasshoppers, please think again to the last lecture—When we’re calculating Big O, we’re always considering worst case and thinking about x in arbitrarily big numbers. Just let your n get up to, say, 300000. Then you can see that O(1) is much more efficient than O(n). This was repeated many times in these lectures, too. Key point, take note!

When we’re trying to find the Big O of a function, we want to focus on loops. They’re the one that determines n, and you want to pay special focus to them—the rest are minor. Ignore them, unless you’re trying to find out the specific algorithm for that function. But for Big O, we only look at the Dominant Term—which is the term that leads the algorithm; i.e, the term that grows the fastest. Loops tend to define these terms.

If a loop that iterates n times is nested inside a loop that also iterates n times, you multiply n x n, which gives us O( n2 ). If they’re not nested and follow each other, then you add—n + n, which gives us O(n).

Which makes me wonder—how are Big (O) s of recursive functions calculated? Does each recursion have an O () value or is the function evaluated as a whole? Also, what about if and elif functions, where there’s a for loop nested in one of the elifs but not in the rest? Where when that for loop is evaluated, Big O is n, but when it’s not, it’s O 1)? Worst case scenario rule says that we should consider the for loop and say O(n) in that case, but it’s a thought to think about.

Big O—it seems like such a simple concept, but in application, it was challenging and mind engaging. There were so many variables to think about, and I found myself getting answers wrong left and right. Practice makes perfect, however. Big O questions are fun, and I look forward to doing them – I just hope I don’t mess up on the Final Exam.

Looking back, I realized a bunch of things—like the theme of friendship and how that tied everything together into a – no, I’m just kidding. Maybe it’s not friendship, but this week’s lecture certainly tied everything into focus—everything we learned, until now, tied elegantly with Big O bow. I’m glad. I only knew iteration when I came in, and I dipped into recursion on the week 6 and 7 Slog— I thought that was the bomb when I first learned about it, but now I see it isn’t quite so—they both have their strengths and weaknesses.

It feels like I’m taking baby steps again. Big baby steps, but still.

The nervousness about the test and exams stay the same, though. Good luck, everyone!

[itscalledcsc148-blog]

SLOG #10: Iteration vs Recursion; BST edition

Remember how we left off last Slog talking about how to do bst_insert and bst_insert  in a recursive way? We’re finally here. 

I’d been looking at the definition of recursion and BST before this class, trying to puzzle it out-- To no avail. But now looking at it, it was because I kept trying to use an iterative definition to apply it-- when what we needed was a whole new approach. 

For the deletion method, Iteration does it by taking the node to be deleted then pointing it’s parent function to it’s right tree-- easy, done. Recursion does it by applying bst_delete to every single node. It’s repetitive and memory consuming, but can be done in short lines of code. 

Both have their good and bad points-- but memory wise, it feels like iteration would be so much more efficient. Remember the old saying that  “No recursive function is more efficient than its iterative equivalent” ? That certainly comes into play here.

[itscalledcsc148-blog]

SLOG #9: Where’s Waldo? Binary Search Trees

We did a brief intro on Binary search trees last time—and here we are now, going deeper and implementing more of our code. ( This seems to be a common theme in our classes. )

The methods we’re exploring today is insert and delete; how do you insert a value in the tree and keep it balanced? Insert and Delete may have been easier for other trees, but for binary, we have to keep to the definition—values lower than the value in the parent node are in the left child, and higher than the value in the parent node are in the right.

Insert was easier than delete. You simply trace the tree, going left if the value is lower, and right if the value is higher, and append the value if the child is empty.

Delete, on the other hand… We had to consider two cases, one where the current node has no child, and two, where the current node does have a child if the current node has no child, we would simply connect the right subtree to the parent node.  ( I say simply, but in practice, it’s really not. ) In the second case, we had to go to the right most node of the left child and put that in the parent node, connect the left child of that node to where the right most node was before.

We wrote it iteratively this week—the teacher asked us this: how could we write is recursively? I was thinking about this, but I can’t see a way how. Iteration uses a method where you “point” to the node, then delete it—how would you write that recursively at all? Maybe I’ll make a post if I figure it out before the next lecture.

[itscalledcsc148-blog]

SLOG #8 Trees, man, trees.

There’s a thing that I forgot to mention that we covered last week—and those were trees—and bad thing I did, because here’s a new foe to tackle—binary trees.

Binary Trees are trees with an arity of two—What the heck is an arity, you might ask. It’s simply the number of children a tree node can have. Binary trees redefine these children to a right child and a left child. We learned about a new method today, too-- __repr__ , which was slightly different than __str__...? I’d googled what it meant before, but formally learning it in class opened a new world. __repr__ is basically a representation of that object for developers.

What I was mostly intrigued by was, though, was arithmetic binary trees.

The fact that you could use binary trees to express arithmetic, frankly, was so cool for me.

As always, it’s a day before the exam and I wish I can kick my nervousness to Andromeda, but unfortunately my kicking poweress is not that much— But that’s fine, we’ll all just kick the test’s ass instead. Good luck everyone!

[itscalledcsc148-blog]

SLOG #7

Hello, lucky week 7, and hello, Recursion. The ol' glory days of writing long winded iterative formulas are over, and it's time to usher in a new star to the stage of short but powerful functions. 

Maybe it's because we're learning a new skill, but I was extremely excited to add recursion to my skill set this week after its introduction last week. ( It was no good just knowing it exists, after all. It was time to use it. ) Examples are always helpful, so we went over Factorials and Fibonacci Functions; both which we learned had Recursive definitions. A recursive formula needed at least one base case and at least one recursive case, which means, that yes! We can have two base cases or two recursive cases. I was wondering how that could be ( it seems like I have a one track mind ) when Fibonacci came and cleared up my doubts. 

The Fibonacci function has two bases cases -- Fibonacci(1) = 1 and Fibonacci(0) = 1. The function's definition is as follows: 

Fibonacci(n) = Fibonacci( n = 1 ) + ( n - 2 ). 

Is it possible, however, to write the Fibonacci function using only one base case? That's something we'll have to try out later. I imagine, however having two base cases would reduce the time for us to get an answer, because python won't have to go that extra level when it hits Fibonacci ( 1 ) to Fibonacci ( 0 ). 

( Or maybe we do need two-- because if we only have one base case, how would we account for Fibonacci ( -1 )? ) 

Stacks also made a guest appearance on our lectures tonight, and they were more important than ever. ( It's interesting how something so simple and are building blocks for so many things. ) A Recursive Function is just a Stack that keeps calling itself repeatedly instead of calling other functions-- For instance, if Function B was called in Function A, the stack would pause what it's doing in Function A and go do Function B. Just imagine Function B as Function A, and voila! One Recursive Function, coming right up. 

Recursion is a powerful tool, though as the lecture ended, there were some questions putting doubt onto the efficiency of the method. Even if it is a powerful tool, the point was--  it was just a bit too powerful. "No recursive function is more efficient than its iterative equivalent" is a sentence that will be burned into my mind. However, why do we use it? It probably has to do with the readability, and the cleanness of it. Four lines of code, at its minimum. Yet capable of doing so many things.

Recursion, I'm looking forward to getting to know you more. Iteration -- I haven't forgotten you, and you'll always be there for me, but say hello to your new friend.

Looks like someone's coding arsenal got a little bit bigger tonight. 

[itscalledcsc148-blog]

SLOG #6

Hello, fellow CSC students and welcome to week 6: where the star of our show is a new topic: recursion.

We were working with a lot of lists this week—lists nested inside lists nested inside lists! Our primary task today was to find out how you could find the sum of all values inside that list, including the ones nested within the lists ( So [ 1 , 4, [ 5 , 7 , [ 5 , 4 ]]] would return 26 ). A simple sum() method wouldn’t work, considering sum() only takes floats and ints, not lists as an acceptable value. We can write this with iteration, and there was conversation in the classroom on how to write it with iteration, but they all required long code. The answer to this? Recursion, iteration’s more powerful and simpler sister.

Recursion is a function where you call the original function again in its code, and use it to “dig deeper”. It works like a stack in the sense that it pauses whatever else it was doing to do that function, then comes back up to resume its code.

We did a lot of tracing exercises demonstrating this exact function— it just demonstrates how important recursive functions are considering we spent a whole 3 hour lecture doing examples. I can’t wait to dig deeper—but that’s going to have to be next week.

[itscalledcsc148-blog]

SLOG #5

Week 5, AKA the Week of Test 1 ™ and linked lists.  

And the test? Well…. Let’s just say it went well.

By well, I mean well as it could have in the small window of time I got to look at it. Hey! This was easy, I thought. I got this. I can do this! Haha. I’d scant taken a 10 minutes look at it when the fire alarm rang; “Is this for real?” My thoughts implored. Other students informed me that #1, my thoughts weren’t as private if said aloud, and #2, yes, it was.

I admit I was half hoping there would be no class after this, but alas, we are students, and we must study. I hope the situation will be resolved well.

So! It was a two hour lecture this week, and we briefly went over Linked Lists last lecture, and now we were diving into it.

Linked Lists, like said in last week’s slog post, consist of Nodes that have a Value and an indicator to the next node in the list. This is why they’re so efficient; Linked lists can grow and shrink easily, because all you have to do is “slide” the node into the place you want, change the _next indicators, and voila. When the _next parameter is None, it means you’re reached the end of the List. Hurrah!

Our teacher demonstrated this in an interesting way. He had volunteers come up from the crowd, and told them to write down where they were sitting (Row and seat number) and their hobbies or their favourite sport onto a sheet of paper. After mixing them up and having them stand in a line, he told them to jot down onto the sheet of paper the seat number of the person to their right, and dispersed them back to their seats. Then, starting from the first person, he told them to state their value ( Their hobby or favourite sport ) and asked what their _next value was-- the location of the next person. It was time consuming, but we got to the end of the Linked list this way.

Introducing a new person into this linked list was easy. All he had to do was ask what the new person’s value was, then link the previous node to the new person, and give the new person the _next indicator of the next node. Easy. This was harder in a simple list, where everyone after him had to shift out of the way to give him space.

One thing that was really interesting to me was the fact the last node’s next could point to the first node—which meant that the list was in a loop! I wondered what its applications could be.

That ended the class on linked lists, with a suggestion to explore the other methods it could take on. That’s what I’m assuming our lab is about this week.

It seems like Linked Lists will be the death of me this semester. I have no idea what I’m doing, but hopefully I’ll get the hang of it soon.

[itscalledcsc148-blog]

SLOG # 4

Week 4, and we’re rolling straight into Containers ( i.e., Sack and Stack ), Unit tests, and Linked Lists.

The purpose of this week feels like it’s to nail in the concepts of super and sub classes; a concept that I’m still struggling with, but getting the hang of. I’ve gotten the grind of putting Implementation errors in the superclass and toiling away in the subclass, and it’s efficient—just feels new.

Sack and Stack are both container classes. Stack has a Last In First Out (LIFO) structure, and Sack is randomized. They have similarities in the code—they both need an add method, a remove method, and an is_empty method. Of course, they need the three basics: __init__, __str__, and __eq__, too.

Our class came up with so many creative ways to implement these—Some said we should put add in the super class container, and some said no, we should put it in the subclass. I felt like add could be implemented in the super class; you could add the item to the container, then remove them differently. For stack , you can just pop the last thing that was appended to the stack list, and for sack, you could randomize the list, then pop the last thing out.

( I wonder how “random” Python’s random method is; because in the end, it all boils down to an equation, right? )

Unit tests were a familiar thing from back in CSC108, but I admit I didn’t really study it like I should have. Unit tests provide a reliable and consistent method of testing; you can test for the same cases repeatedly without having to copy paste the code into the console every single time. It’s a bit different than a doc test ( actually, a lot different ) that you need to write a separate python class for it. It’s really efficient.

Unit tests feel odd; probably because they’re semi new material. Tear Down? Set Up? What are these? It’s methods for setting up the test case and cleaning up after it’s done, but the concepts still felt so foreign to me.

Then it was Linked Lists ( We sure were covering a lot of topics this week! ) and the basic intro was that: in python, lists can take up a lot of memory, an large lists may not be able to be stored in computer memory. Linked lists, on the other hand, are “broken up” into nodes and stored separately instead of consecutively, so the computer has more space to operate. Each node has a value and the reference to the next node. The Linked List Node eludes me— And I can’t wait to see how it’s covered next week.

Speaking of next week…

Man, I’m really nervous about the midterm test; writing computer code down into pencil always makes me wince. Mostly because Pycharm’s not there to help me out with its error searching-- but ah, well, a good programmer knows not to depend on its compiler. Tally ho!

[itscalledcsc148-blog]

Week 3 Review

It’s the start of this blog and CSC148, and it feels odd to be posting a blog about it-- but I’m excited. It’s a good opportunity to review, and I hope I’ll get to utilize it to the fullest-- and maybe fall into the habit of reviewing classroom material every week. Hopefully.

The classes we’ve had so far were about designing classes.  the professor I’m with teaches passionately, with a focus on design and building up good programming/designing habits. From CSC 108, I had a habit of not completing the docstring before coding, which I realize now was one of the many reasons I felt rushed to hand in assignments and got code wrong-- because while I had an idea of what I was writing, it hadn’t been solidified and the result was code that was subpar.

Classes were one of the last things we covered in CSC108, and the memory is still fresh in my mind. The docstring is slightly different in 148 and Pycharm is new, but the fundamentals are still there and while I feel uneasy swimming in new waters, it’s a reassuring thing to fall back on. The first two weeks felt like a review, and the labs are... odd? It’s that state where I know what’s going on, and know the concepts, but applying it feels weird after not doing it for so long. 

I really hope I can stop procrastinating, and I hope I can develop the habit of working on labs ahead of time and not being too shy about asking questions in class. 

An interesting thing that happened in class was about when we were going over equality, one of the code snippets: 

>>> x = [5] >>> z = [5]  >>> y = x >>> x == y ? >>> x == z ? >>> x is z

wouldn’t work; x is z was supposed to display false after changing z’s value, but it kept coming out as true. I want to write a blog post about it later, so I’ll leave it here for now. 

I’ve always had mutable and immutable confused, and it was really cool how that one blunder cleared everything up for me. That moment of understanding is exhilarating and it’s nice that I can finally understand it.

All in all, it was a great 3 weeks, and I’m looking forward to the next.