Week 1-2: Object Orientated Programming.
We were introduced two abstract data types (ADT) that commonly used in Computer Science which were Stack and Queue. Stack and Queue are both container class just like normal list. Stack adds (push) and removes (pop) data from the back of the existing data series, Queue also adds data (prepend) to the back of the data series but it removes (dequeue) data, starting from the front of the data series.
Since Stack behaves almost like list, and in fact we can easily implement Stack ADT, using normal Python list:
class Stack:I know you are thinking that i'm going to use the same strategy to implement Queue. And yes we can use list to implement queue and use the built-in function del to remove the first element in the list. Below is the code, is not it the best way to implement Queue ?
def __init__(self: 'Stack') -> None:
self.data = []
def pop(self: 'Stack') -> object:
return self.data.pop() # pop data from the top of the stack (back of the list
def is_empty(self: 'Stack') -> bool:
return self.data == [] # check if a stack is empty
def push(self: 'Stack', o: object) -> None:
self.data.append(o) # new data is pushed to the top of the stack
class Queue: # O(n) implementationThe problem for such an implementation is that when we delete an element in a list, all of the elements that come after the it will need to be shift by 1 to the front. So the running time complexity of my dequeue function is O(n-1) or simply O(n), which is not too bad but can be improved!
def __init__(self) -> None:
self.data = []
def dequeue(self) -> object:
first = self.data[0] # temporarily store first element in the list
del(self.data[0]) # delete the first element
return first # return the element that has been deleted.
def is_empty(self) -> bool:
return self.data == [] # check if the queue is empty
def enqueue(self, o) -> None:
self.data.append(o) # new data is added to back of the queue
Let take a look at my second implementation of Queue:
class Queue2: # O(1) implementation
def __init__(self) -> None:In this second implementation, i still use Python list to store data in the queue. However, I do not physically remove any element in the list self.data. I has the variable named 'self.first', which is an index in list 'self.data' that represents for the first element in the Queue. When method dequeue is called on an object, there are two possible cases:
self.data = []
self.first = None # tracking the index of first element
def dequeue(self) -> object:
if len(self.data) > 1:
self.first += 1
return self.data[self.first-1]
else:
self.first = None
return self.data[0]
def is_empty(self) -> bool:
return self.first == None
def enqueue(self, o) -:
self.data.append(o)
# If an element is added into the list, then the list list is not
# blank and the first index of first element in the list is 0.
self.first = 0
- If there are more than 1 element in the list self.data, the index reference self.first is incremented by 1. The element at index [self.first - 1] in list self.data, which is an element that has been "removed" from the Queue, is then returned.
- If there is only one element in the list self,data, the index reference self.first becomes None, indicating that the Queue is empty, although the list self.data is not empty! The only element in the list self.data is then returned.
Note that the function above can easily be done by a single while loop, but for the purpose of illustrating how exception works with recursion i made it little bit more complex.Week 3: Raising and Catching Exception.
I personally found it to be the easiest topic of the course. The purpose for raising and catching the Exceptions is to keep the program running when the user accidentally inputs invalid data or carries out illegal operation. An example of this can be found in the assignment 1, when an error message is rase but the program keeps running when the user unintentionally put a big cheese on top of a smaller cheese. I am not going revise that code, but instead do another example that works well when raising Exception works well with recursion! Consider the function slog_grade below which asks the TA for my Slog grade.
def slog_grade(): #abcSo the program asks the TAs to input a grade for my Slog. If the input grade is not equal to 100%, the InvalidSlogGrade error is raised and caught by the except statement. The function slog_grade is then recursively call in the except statement until the InvalidSlogGrade error is no longer raised. In order to stop the error from happening, the TA have to give me 100%.
grade = int(input("Please type in a grade for my Slog: "))
try:
if grade != 100:
raise InvalidSlogGrade
else:
return grade # thank you for giving me 100%, haha
except InvalidSlogGrade:
print("You are only allowed to type in 100%")
slog_grade()Week 3(2): Unit Testing.That is what the TAs always do, making test files and test all of the functions that we wrote for the assignments and exercises. I just tried to be a TA and wrote a class that test the function slog_grade() that i wrote above.
import unittest
class Test_grade(unittest.TestCase):
def test_slog_grade(self):
self.assertEqual(slog_grade(), 100)
def test_grade_to_percentage(self):
self.assertEqual(grade_to_percentage(slog_grade(), 100), 100)
if __name__ == '__main__':
unittest.main(exit = False)
The code looks fairly simple but it is a good example of how a testing file should be structured.
Week 4: Inheritance
Inheritance is often used in making a new class that is almost identical to some other but with some additional features. There are basically two pieces of code that we have to remember for the exam.
- derived_class_name(base_class_name) which is the syntax used for inheritance when declaring a new class.
- base_class_name.function_name() is the syntax used to call a function available in the parent classes. It is used in case when a programmer wants to reuse a method available in the parent classes, that has been override in the current class.
There are considerable advantages of using inheritance:
- Reusability: It reduces the duplicated code, the hard drive memory used to store these duplicated codes as well as time of a programmer.
- Upgrading: A programmer can add additional features into their program without alternating the current state of the program.
- Data Hiding: In Java, we can declare a variable or function to be “private”, so that the derived class cannot directly access or alter private data in parent classes. Although there is built in “property” in Python that make accessing variables in parent classes a little bit tricky, there exist no private variables or private methods that cannot be externally accessed. Java therefore is considerably more secure than Python.
- Overriding: A function that appear in the parent class can be overridden in derived class to perform a new operation.
Surprisingly, there are disadvantages as well:
- Multiple Inheritance: Python object is extremely powerful since it allows multiple inheritance, a class can inherit methods from more than one parent class. But very unfortunate that not all programming language support multiple inheritance. The more rigorous programming language than Python, Java does not support multiple inheritance.
- Running Time: If we have a very complex inheritance hierarchy, jumping from one to another level of inheritance may cost the machine some processing time.
- Upgrading: If a function in a parent class is changed, all of the daughter class also need to be upgraded.
