We have been learning about algorithm complexity and big O notation in class recently. CSC148 has been covering the topic in a very practical way, for example how it applies to sorting algorithms. We are also covering it in CSC165, which has been going more rigorous into the theory behind it. Despite being kind of abstract, I think the idea of big O is really intuitive; the difficult part is actually applying it the code you write.
Tuesday 12 November 2013
Thursday 10 October 2013
I got 99 problems but a bit ain't one
While working on the assignment #1 I ran into an annoying problem. I was working on the function to find the best index to split the stack of cheeses at in order to move them on four stools. Part of the function involves raising 2 to the exponent i. It seemed obvious that I could just write 2^i. After getting seemingly random values out of my function I eventually decided to check the Python manual. There I found out that ^ is actually bitwise operator, so the expression should have used 2**i.
The Object Orient Express
Object oriented is a programming paradigm in which everything in the domain of our code is an "object". An object is something that has attributes (data stored in the object) and methods (functions that the object can be called to do). Each object is created from a template called a class, and each new one we create from that class is called an instance.
One reason the object oriented paradigm is useful is because of encapsulation. Using encapsulation an object can be become a black box; we interact with it through a basic interface, with no knowledge of its inner workings. This is helpful if for example you are working with other programmers who need to use your code, but don't need to know how it works, or even for yourself so you don't always need to remember how your old code works. Encapsulated objects have "public" methods and attributes which are intended to be accessed by other objects, and "private" methods and attributes which are only intended for use by the object itself.
Another helpful feature of objects is inheritance. Instead of defining a class from scratch, inheritance lets us use another class, called the "parent", as a template. This means that instances of the new class will have whatever attributes and methods you define, but also all the attributes and methods defined in the parent class. For example, Python's unittest module provides a parent testing class with general useful methods for testing, and you can create your own class which inherits it to do test specific to your program, as opposed to making your own testing class entirely by yourself.
Recursion: It's as Easy as Recursion!
Recursion is a problem solving technique in which a function calls itself. A basic recursive function has two parts. First: the base case. The base case is the smallest, most basic version of a problem and it is typically trivial to solve. After solving this small problem the function returns some value. The second part of a recursive function is where the problem is broken down into one or more smaller parts. At this point the function is called from within itself on these smaller parts. This will end up repeating until the base case is reached, and the solution gets composed out of the solutions of the smaller parts.
Recursion is a useful technique. It lets you think about a very complex problem in simple terms, and build your way up from there. Most of the time it is also relatively terse, so your code will be easier to read and understand.
However, recursion should be used with caution. If a base case is used which doesn't catch every possible input you want it to, the function may continue to call itself forever, eventually causing a run-time error. Another potential problem with recursion is memory usage. Each time the function calls itself we have to keep the previous variables it was using in memory. By the time the function reaches the base case your stack can be huge and be taking up large amounts of memory, slowing down your program.
While working on the assignment #1 I ran into an annoying problem. I was working on the function to find the best index to split the stack of cheeses at in order to move them on four stools. Part of the function involves raising 2 to the exponent i. It seemed obvious that I could just write 2^i. After getting seemingly random values out of my function I eventually decided to check the Python manual. There I found out that ^ is actually bitwise operator, so the expression should have used 2**i.
The Object Orient Express
Object oriented is a programming paradigm in which everything in the domain of our code is an "object". An object is something that has attributes (data stored in the object) and methods (functions that the object can be called to do). Each object is created from a template called a class, and each new one we create from that class is called an instance.
One reason the object oriented paradigm is useful is because of encapsulation. Using encapsulation an object can be become a black box; we interact with it through a basic interface, with no knowledge of its inner workings. This is helpful if for example you are working with other programmers who need to use your code, but don't need to know how it works, or even for yourself so you don't always need to remember how your old code works. Encapsulated objects have "public" methods and attributes which are intended to be accessed by other objects, and "private" methods and attributes which are only intended for use by the object itself.
Another helpful feature of objects is inheritance. Instead of defining a class from scratch, inheritance lets us use another class, called the "parent", as a template. This means that instances of the new class will have whatever attributes and methods you define, but also all the attributes and methods defined in the parent class. For example, Python's unittest module provides a parent testing class with general useful methods for testing, and you can create your own class which inherits it to do test specific to your program, as opposed to making your own testing class entirely by yourself.
Recursion: It's as Easy as Recursion!
Recursion is a problem solving technique in which a function calls itself. A basic recursive function has two parts. First: the base case. The base case is the smallest, most basic version of a problem and it is typically trivial to solve. After solving this small problem the function returns some value. The second part of a recursive function is where the problem is broken down into one or more smaller parts. At this point the function is called from within itself on these smaller parts. This will end up repeating until the base case is reached, and the solution gets composed out of the solutions of the smaller parts.
Recursion is a useful technique. It lets you think about a very complex problem in simple terms, and build your way up from there. Most of the time it is also relatively terse, so your code will be easier to read and understand.
However, recursion should be used with caution. If a base case is used which doesn't catch every possible input you want it to, the function may continue to call itself forever, eventually causing a run-time error. Another potential problem with recursion is memory usage. Each time the function calls itself we have to keep the previous variables it was using in memory. By the time the function reaches the base case your stack can be huge and be taking up large amounts of memory, slowing down your program.
Subscribe to:
Posts (Atom)