During this term, I have learned a lot about computer programming and computer science, such as being able to reduce the amount of lines necessary for a function through shortcuts and recursion, ADTs and being able to obtain the big-Oh of certain functions. I have also learned about __repr__, __contains__, __getitem__, __setitem__, as well as general vs specific. These have helped me to better understand how to go about object-oriented programming and being aware of the steps that are necessary to using these objects in a program.
While at times I believe that there were easier ways to implement certain functions without the use of classes and that the construct didn't seem all that relevant, I understand now the advantages of OOP. Errors can be more easily fixed and it can provide already established code and an idea of how to go about implementing a class with similar attributes. ADTs were interesting to look at, if only because of the visual images that are conjured, but I have yet to understand their role for programming projects, though the assignments and exercises have helped me understand how to go about creating functions relevant to them. Recursion and implementing ADTs has been more challenging without the tutorials and my test 2 mark certainly reflected that perhaps I did not understand linked lists as well as I did (nor did I understand the types of orders one travels in a tree), and I will certainly have to be aware of those when I study for the exam. Seeing big-Oh at the end of the course did help me understand better what I was looking at in CSC165.
Overall, I think this class has created a decent enough foundation for my path in computer science and programming. While it is a shame that the strike affected my learning process, I believe that there is a sufficient amount of material and skills that I have learned that will allow me to do well on the final exam.
Wednesday 1 April 2015
Tuesday 31 March 2015
Entry #5 - Predicting Machines
This was a self-challenge I created in CSC165 to understand better how to calculate the value of the input in a machine. The way these notes were formatted helped me to understand better the way in which to find the big-Oh of a function.
######################################################
Machine 1:
How can we find z assuming x > 1?
For this, we will use x-y-z charts.
2:
2:
|
x
|
y
|
z
|
|
2
|
1+1
|
+1
|
|
2-1
|
2
|
+1
|
|
1
|
2
|
2
|
3:
|
x
|
y
|
z
|
|
3
|
1+1
|
+1
|
|
3-1
|
2
|
+1
|
|
2
|
2
|
2
|
4:
|
x
|
y
|
z
|
|
4
|
1+1
|
+1
|
|
4-1
|
2
|
+1
|
|
3
|
2
|
+0
|
|
3
|
2+1
|
+1
|
|
3
|
3
|
3
|
5:
|
x
|
y
|
z
|
|
5
|
1+1
|
+1
|
|
5-1
|
2
|
+1
|
|
4
|
2
|
+0
|
|
4
|
2+1
|
+1
|
|
4-1
|
3
|
+1
|
|
3
|
3
|
4
|
We can simplify this for the next few numbers by pointing out when z increases for each condition (x > y, x > z) and compare it to the previous results:
2: 1, 1 = 2
3: 1, 1 = 2
4: 1, 1, 0, 1 = 3
5: 1, 1, 0, 1, 1 = 4
6: 1, 1, 0, 1, 1, 0, 1 = 5
7: 1, 1, 0, 1, 1, 0, 1, 0, 1 = 6
8: 1, 1, 0, 1, 1, 0, 1, 1, 1 = 7
It can be gathered that z = x – 1 except at x = 2 when z = x. This means that at some point a condition that isn’t met before does get met or a new condition is met, adding to the chain.
Machine 2:
How can we find a assuming x > -1?
We know that machine_2(-1) returns 0. What does
machine_2(0) return?
x = x + 2 so x = 2
Since y = 1 and x > y, a goes up by 1 and so does y.
Since z = 2 and y == z, a goes up by 1 and z goes up by 2.
x > y is not in effect anymore, therefore machine_2(0) returns 2 (which is what a is).
Now what happens when machine_2(1) is executed? The same as machine_2(0) but we can add 1 to a since x = 3 and x still is greater than y when y = 2 making the function return 3. How about machine_2(2)? Again the same as before apply but x now equals 4 meaning that y has to increase by 1 in order to break the loop (which makes a increase by 1). By doing so, y = 4 and z = 4 making the y == z statement true and allowing a to go up by 1 again, meaning the function returns 5.
x = x + 2 so x = 2
Since y = 1 and x > y, a goes up by 1 and so does y.
Since z = 2 and y == z, a goes up by 1 and z goes up by 2.
x > y is not in effect anymore, therefore machine_2(0) returns 2 (which is what a is).
Now what happens when machine_2(1) is executed? The same as machine_2(0) but we can add 1 to a since x = 3 and x still is greater than y when y = 2 making the function return 3. How about machine_2(2)? Again the same as before apply but x now equals 4 meaning that y has to increase by 1 in order to break the loop (which makes a increase by 1). By doing so, y = 4 and z = 4 making the y == z statement true and allowing a to go up by 1 again, meaning the function returns 5.
The table illustrates this pattern:
|
x
|
m_2(x)
|
|
0
|
2
|
|
1
|
3
|
|
2
|
5
|
|
3
|
6
|
|
4
|
8
|
|
5
|
9
|
|
6
|
11
|
When x goes from odd to even, 2 is added. When x goes from even to odd, 1 is added. So machine_2(x) creates this pattern:
2 + 1 + 2 + 1 + 2 + 1 + 2 . . .
(based on 2, 3, 5, 6, 8, 9, 11 . . . )
To put it another way:
0 / 1 turns to 2 / 3 # by adding 2
2 / 3 turns to 5 / 6 # by adding 3
4 / 5 turns to 8 / 9 # by adding 4
6 / 7 turns to 11 / 12 # by adding 5
etc.
Another interesting element is that the even and odd
sets all differ by 3.
We can re-write the results of machine_2 like so:
-1: 0 + 0 // 0 + 2(0)
0 : 0 + 2 // 0 + 2(1)
1 : 1 + 2 // 1 + 2(1)
2 : 1 + 4 // 1 + 2(2)
3 : 2 + 4 // 2 + 2(2)
4 : 2 + 6 // 2 + 2(3)
5 : 3 + 6 // 3 + 2(3)
6 : 3 + 8 // 3 + 2(4)
7 : 4 + 8 // 4 + 2(4)
We can split this through conditions:
if x % 2 == 0 then a = x/2 + 2 * ceiling((x + 1)/2)
if x % 2 == 1 then a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
So we can combine the two to get:
a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
-1: 0 + 0 // 0 + 2(0)
0 : 0 + 2 // 0 + 2(1)
1 : 1 + 2 // 1 + 2(1)
2 : 1 + 4 // 1 + 2(2)
3 : 2 + 4 // 2 + 2(2)
4 : 2 + 6 // 2 + 2(3)
5 : 3 + 6 // 3 + 2(3)
6 : 3 + 8 // 3 + 2(4)
7 : 4 + 8 // 4 + 2(4)
We can split this through conditions:
if x % 2 == 0 then a = x/2 + 2 * ceiling((x + 1)/2)
if x % 2 == 1 then a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
So we can combine the two to get:
a = ceiling(x/2) + 2 * ceiling((x + 1)/2)
Machine 3:
How can we find b assuming x > 3?
The while x > a loop indicates how many steps it
takes for a to equal x using the a + 1 approach, making b = (x - a).
Since a = 3, b = (x - 3).
Now xα = x + 2.
The while xα > z loop indicates how long it takes for xα == z (provided xα % 2 == 0) or xα < z (xα % 2 == 1) following the xα – 1 // z + 1 approach:
Since a = 3, b = (x - 3).
Now xα = x + 2.
The while xα > z loop indicates how long it takes for xα == z (provided xα % 2 == 0) or xα < z (xα % 2 == 1) following the xα – 1 // z + 1 approach:
|
X
|
z
|
B
|
|
xα
(x + 2)
|
2 (z)
|
+ 0
|
|
xα
- 1 (x + 2 - 1)
|
2 + 1 (z +
1)
|
+ 1
|
|
xα
- 2 (x + 2 - 1)
|
2 + 2 (z +
2)
|
+ 2
|
|
-
|
-
|
-
|
|
xα-final
(x + 2 – n)
|
zfinal
(z + n or 2 + n) |
+ n
|
By manipulating inequalities:
x + 2 - n ≤ 2 + n
x + 2 ≤ 2 + 2n
x + 2 ≤ 2(1 + n)
((x + 2) / 2) ≤ 1 + n
(((x + 2) / 2) – 1) ≤ n
So we have:
b = (x - 3) + (((x + 2) / 2) - 1) # if x % 2 == 0
b = (x - 3) + ceiling(((x + 2) / 2) - 1) # if x % 2 == 1
b = (x - 3) + ceiling(((x + 2) / 2) - 1) # if x % 2 == 1
Which means b
= (x - 3) + ceiling(((x + 2) / 2) – 1).
We will call
n = ceiling(((x + 2) / 2) – 1) # b = (x + 3) + n
At this point, xβ = xα – n. Consider xβ = xβ + 3 = xα – n + 3
At this point, xβ = xα – n. Consider xβ = xβ + 3 = xα – n + 3
The while xβ > y indicates how long it
takes for xβ == y (xβ % 2 == 0) or xβ < y
(x % 2 == 1) following the xβ - 1 // y + 2 approach:
|
xβ
|
y
|
b
|
|
xβ
(xα – n + 3)
|
1 (y)
|
+ 0
|
|
xβ
– 1 (xβ – 1)
(xα – n + 3 - 1) |
1 + 2
(y + 1(2)) |
+ 1
|
|
xβ
– 2 (xβ – 2)
(xα – n + 3 - 2) |
1 + 4
(y + 2(2)) |
+ 2
|
|
-
|
-
|
-
|
|
xβ-final
(xβ – q)
(xα – n + 3 - q) |
yfinal
(y + 2q or 1 + 2q) |
+ q
|
xβ – q ≤ 1 + 2q
xβ ≤ 1 + 3q
xβ – 1 ≤ 3q
(xβ – 1 / 3) ≤ q
So we have:
b = (x - 3) + n + (xβ – 1 / 3) # if x % 2 == 0
b = (x - 3) + n + ceiling(xβ – 1 / 3) # if x % 2 == 1
In conclusion, when x > 3:
b = (x – 3) + n + ceiling(xβ – 1 / 3)
b = (x – 3) + n + q # ultra-simplified
b = (x – 3) + n + ceiling(xα – n + 2 / 3) #in “x”-n terms
b = (x – 3) + n + ceiling(x – n + 4 / 3) #in x-n terms
b = (x - 3) + n + ceiling(xβ – 1 / 3) # if x % 2 == 1
In conclusion, when x > 3:
b = (x – 3) + n + ceiling(xβ – 1 / 3)
b = (x – 3) + n + q # ultra-simplified
b = (x – 3) + n + ceiling(xα – n + 2 / 3) #in “x”-n terms
b = (x – 3) + n + ceiling(x – n + 4 / 3) #in x-n terms
Machine 4:
How can we find b if x > 1?
This one will require checking inputs and outputs:
|
x
|
m_4(x)
|
|
2
|
3
|
|
3
|
3
|
|
4
|
4
|
|
5
|
4
|
|
6
|
6
|
|
7
|
6
|
|
8
|
7
|
In this case we have pairs that produce the same value thus creating a sequence like so:
3, 4, 6, 7, 10, 11, 13, 14, 17, 18 . . .
This has a repeated pattern of + 3 + 1 + 2 + 1 + . . .
When a number is able to accomplish both boolean statements, b increases by 3 (machine_4(2)). When the z % 2 == 0 statement is accomplished by itself, b increases by 2 (machine_4(6)).
Now we can color code the sequence to indicate when b increase by 2 and when it increases by 3:
3, 4, 6, 7, 10, 11, 13, 14, 17, 18, 20, 21, 24 . . .
Both of these sets are separated by 7 (1 + 3 + 1 + 2 // 1 + 2 + 1 + 3). Let’s look at the pairs of some of these closely.
Both of these sets are separated by 7 (1 + 3 + 1 + 2 // 1 + 2 + 1 + 3). Let’s look at the pairs of some of these closely.
|
n ∊ Blue
|
Pair
|
n ∊ Red
|
Pair
|
|
3
|
2, 3
|
6
|
6, 7
|
|
10
|
10, 11
|
13
|
14, 15
|
|
17
|
18, 19
|
20
|
22, 23
|
These pairs have a difference of 8. If we were to assign a color to the other numbers with a 7 difference in a pattern, we might obtain something more concise:
3, 4, 6, 7, 10, 11, 13, 14, 17, 18, 20, 21, 24 . . .
We go B, Y, R, G with each pair differentiating by 8.
Pooling all this information to calculate b, we first establish the original
B-Y-R-G pairs.
B: 2, 3. Y: 4, 5. R: 6, 7. G: 8, 9
Then we say that if your x is an item in the original B-Y-R-G pairs + 8n, then you must get the original B-Y-R-G pair values (3, 4, 6, 7) and add it by 7n
Ex.1: machine_4(29) = b. Calculate b.
Can 29 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
29 % 8 = 5. Does this mean that 29 = 5 + 8n?
Prove: 29 – 5 = 8n. 24 = 8n. 3 = n.
Y: 4, 5 = 4
So therefore 29 could be 4 + 7(3).
check - machine_4(29) == 25. True!
(Note: this also means that machine_4(28) == 25 is True)
Ex.2: machine_3(33) = b. Calculate b.
Can 33 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
33 % 8 = 1. What does this mean? Consider an int such that it can be represented by 8 + 8n. This int % 8 = 0. Does this mean that if an int % 8 = 1, it would have to be represented as 9 + 8n?
Prove: 33 – 9 = 8n. 24 = 8n. 3 = n.
(Note: You can also consider 9 + 8n as 1 + 8 + 8n)
G: 8, 9 = 7
So therefore 33 could be 7 + 7(3).
check – machine_4(33) == 28. True!
(Note: this also means that machine_4(32) == 28 is True)
B: 2, 3. Y: 4, 5. R: 6, 7. G: 8, 9
Then we say that if your x is an item in the original B-Y-R-G pairs + 8n, then you must get the original B-Y-R-G pair values (3, 4, 6, 7) and add it by 7n
Ex.1: machine_4(29) = b. Calculate b.
Can 29 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
29 % 8 = 5. Does this mean that 29 = 5 + 8n?
Prove: 29 – 5 = 8n. 24 = 8n. 3 = n.
Y: 4, 5 = 4
So therefore 29 could be 4 + 7(3).
check - machine_4(29) == 25. True!
(Note: this also means that machine_4(28) == 25 is True)
Ex.2: machine_3(33) = b. Calculate b.
Can 33 be written as (2, 3, 4, 5, 6, 7, 8, 9) + 8n? Probably.
33 % 8 = 1. What does this mean? Consider an int such that it can be represented by 8 + 8n. This int % 8 = 0. Does this mean that if an int % 8 = 1, it would have to be represented as 9 + 8n?
Prove: 33 – 9 = 8n. 24 = 8n. 3 = n.
(Note: You can also consider 9 + 8n as 1 + 8 + 8n)
G: 8, 9 = 7
So therefore 33 could be 7 + 7(3).
check – machine_4(33) == 28. True!
(Note: this also means that machine_4(32) == 28 is True)
Basically:
Let x % 8 = m
If m = 2 or 3: x can be written as 2 + 8n or 3 + 8n
Solve for n, then plug in for 3 + 7n = b
If m = 4 or 5: x can be written as 4 + 8n or 5 + 8n
Solve for n, then plug in for 4 + 7n = b
If m = 6 or 7: x can be written as 6 + 8n or 7 + 8n
Solve for n, then plug in for 6 + 7n = b
If m = 0 or 1: x can be written as 8 + 8n or 9 + 8n
Solve for n, then plug in for 7 + 7n = b
Machine 5:
How can we find a if x > 2?
The while x > z loop will stop when x ≤ 2 and a
increases every time x decreases by 1, meaning a so far equals:
a = (x – 2) + inner while loop
The inner while loop creates the x + x – 1 + x – 2 … + 1 sequence with x – 2. Since that sequence is normally (x)(x – 1)/2 and (x – 1) represents the lowest point, we must change this to (x – 2)(x – 1) / 2. Thus:
a = (x – 2) + ((x – 2)(x – 1) / 2)
a = (x – 2) + ((x2 – 3x – 2) / 2)
a = (x – 2) + inner while loop
The inner while loop creates the x + x – 1 + x – 2 … + 1 sequence with x – 2. Since that sequence is normally (x)(x – 1)/2 and (x – 1) represents the lowest point, we must change this to (x – 2)(x – 1) / 2. Thus:
a = (x – 2) + ((x – 2)(x – 1) / 2)
a = (x – 2) + ((x2 – 3x – 2) / 2)
###################################################################
def machine_1(x):
y = 1
z = 0
while x > y:
y = y + 1
z = z + 1
if x > z:
x = x - 1
z = z + 1
return z
def machine_2(x):
x = x + 2
y = 1
z = 2
a = 0
while x > y:
y = y + 1
if y == z:
a = a + 1
z = z + 2
a = a + 1
return a
def machine_3(x):
y = 1
z = 2
a = 3
b = 0
while x > a:
a = a + 1
b = b + 1
x = x + 2
while x > z:
x = x - 1
z = z + 1
b = b + 1
x = x + 3
while x > y:
y = y + 2
x = x - 1
b = b + 1
return b
def machine_4(x):
y = 0
z = 0
a = 1
b = 0
while x > a:
a = a + 1
x = x - 1
b = b + 1
z = a
if z % 2 == 0:
y = y + 1
b = b + 1
if y % 2 == 1:
b = b + 1
return b
def machine_5(x):
z = 2
a = 0
while x > z:
y = x
while y > z:
y = y - 1
a = a + 1
x = x - 1
a = a + 1
return a
Entry #4 - Using A Linked List In Relation To A Function
Back in CSC108, I created a function that would lead any integer of your choosing to reach 16. It was a relatively simple concept. Seeing linked lists, I figured that it would be interesting if I could adapt it to that ADT. So I imported the code I wrote for linked list (the linked list node .py file from this class works with this too) and modified it to suit my purposes.
Before I do that, allow me to bring up a random number like 43 and ask you to do the following. I want you to add 1, then divide by two and round down, then subtract 4 twice, double the result of that, and subtract 4 three more times. Did you reach 16? I bet you did. How did those steps come about? Well let's look below.
Before I do that, allow me to bring up a random number like 43 and ask you to do the following. I want you to add 1, then divide by two and round down, then subtract 4 twice, double the result of that, and subtract 4 three more times. Did you reach 16? I bet you did. How did those steps come about? Well let's look below.
import math
def linked_list_specific_sts(number):
''' (int) -> LinkedList
Return the steps necessary to reach 16
>>> lnk = linked_list_specific_sts(43)
>>> print(lnk)
43 -> Add 1 -> Divide by 2 and round down -> Subtract 4 -> Subtract 4 -> Double it -> Subtract 4 -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|
'''
lnk = LinkedList()
lnk.append(str(number))
while number != 16:
if number % 2 == 0 and number < 16:
number = number * 2
lnk.append('Double it')
elif number % 2 == 1 and number < 16:
number = number + 1
lnk.append('Add 1')
elif number % 2 == 0 and 16 < number < 30:
number = number - 4
lnk.append('Subtract 4')
elif number % 2 == 1 and 16 < number < 30:
number = number - 1
lnk.append('Subtract 1')
elif number % 2 == 0 and 30 <= number < 100:
number = number//2
lnk.append('Divide by 2 and round down')
elif number % 2 == 1 and 30 < number < 100:
number = number + 1
lnk.append('Add 1')
elif number >= 100:
number = round(math.log(number, 10))
lnk.append('Round the base 10 log')
lnk.append('You have reached 16')
return lnk
As you can see, there are certain restrictions that lead to certain steps.
- If number is even and less than 16, double it
- If number is odd and less than 16, add 1
- If number is even and greater than 16 but less than 30, subtract 4
- If number is odd and greater than 16 but less than 30, subtract 1
- If number is even and greater than 30 but less than 100, divide by 2 and round down
- If number is odd and greater than 30 but less than 100, add 1
- If number is greater than 100, round the base 10 log
I did get lazy when the number gets higher than 100, but that's just me exercising one of the golden rules of being a computer scientist. Now you can do this on your own without the function above but what if you wanted to be sure that you were following the algorithm correctly after a certain amount of steps? Well, worry not, for obtain_sts_step has you covered.
def obtain_sts_step(lnk, step):
''' (LinkedList, int) -> int
Precondition: step != lnk.size - 1 and step > 1
Return what the step would be based on the instructions given
>>> lnk = linked_list_specific_sts(43)
>>> obtain_sts_step(lnk, 3)
18
>>> lnk = linked_list_specific_sts(35375)
>>> obtain_sts_step(lnk, 5)
20
'''
start = int(lnk[0])
for i in range(1, step+1):
if lnk[i] == 'Add 1':
start = start + 1
elif lnk[i] == 'Divide by 2 and round down':
start = start // 2
elif lnk[i] == 'Subtract 4':
start = start - 4
elif lnk[i] == 'Double it':
start = start * 2
elif lnk[i] == 'Round the base 10 log':
start = round(math.log(start, 10))
elif lnk[i] == 'Subtract 1':
start = start - 1
return start
As you can see, it returns to you the number after finally going through all the steps. We know how 43 goes, but what about 35375? Well first we should look at what happens when you enter that number into linked_list_specific_sts:
35375 -> Round the base 10 log -> Add 1 -> Double it -> Double it -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|
We would stop at the first instance of Subtract 4, meaning that the next 5 numbers would be 5, 6, 12, 24, 20. Now that's if you want a quick check to see that your approach with the algorithm was correct. If you simply just want to see the numbers rather than the actions that you need to do, you can use linked_list_sts:
As you can see, it returns to you the number after finally going through all the steps. We know how 43 goes, but what about 35375? Well first we should look at what happens when you enter that number into linked_list_specific_sts:
35375 -> Round the base 10 log -> Add 1 -> Double it -> Double it -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|
We would stop at the first instance of Subtract 4, meaning that the next 5 numbers would be 5, 6, 12, 24, 20. Now that's if you want a quick check to see that your approach with the algorithm was correct. If you simply just want to see the numbers rather than the actions that you need to do, you can use linked_list_sts:
def steps_to_sixteen(number):
""" (int) -> list of ints
Precondition: number != 0
Return a list of steps it takes to get to 16
>>> steps_to_sixteen(2)
[2, 4, 8, 16]
>>> steps_to_sixteen(3)
[3, 4, 8, 16]
>>> steps_to_sixteen(10)
[10, 20, 16]
>>> steps_to_sixteen(30)
[30, 15, 16]
>>> steps_to_sixteen(100)
[100, 2, 4, 8, 16]
"""
steps = []
steps.append(number)
while number != 16:
if number % 2 == 0 and number < 16:
number = number * 2
steps.append(number)
elif number % 2 == 1 and number < 16:
number = number + 1
steps.append(number)
elif number % 2 == 0 and 16 < number < 30:
number = number - 4
steps.append(number)
elif number % 2 == 1 and 16 < number < 30:
number = number - 1
steps.append(number)
elif number % 2 == 0 and 30 <= number < 100:
number = number//2
steps.append(number)
elif number % 2 == 1 and 30 < number < 100:
number = number + 1
steps.append(number)
elif number >= 100:
number = round(math.log(number, 10))
steps.append(number)
return steps
def linked_list_sts(number):
""" (int) -> NoneType
Return steps to take to sixteen as a linked list
>>> lnk = linked_list_sts(43)
>>> print(lnk)
43 -> 44 -> 22 -> 18 -> 14 -> 28 -> 24 -> 20 -> 16 ->|
"""
steps = steps_to_sixteen(number)
lnk = LinkedList()
for step in steps:
lnk.append(step)
return lnk
As you can see, I used a helper function which simply shows them as a list, and then have each step in the list be appended to the linked list.
Subscribe to:
Posts (Atom)