Artificial Intelligence Homework 3
Ed Smart
CSC 375
Homework 3
3.1 Explain why problem formulation must follow goal formulation.
Problem formulation must follow goal formulation because goal formulation narrows the focus of the problem to an extent that it may be solved within a reasonable amount of time. If a problem is formed without a goal, depending on the problem, an agent may have a near infinite number of decisions or options to choose from and must determine which is the most beneficial to it.
For example, if an agent is sitting at a desk with a computer and a textbook but has no specific goal formulated, what will it do? It may use the computer to surf the web or play video games, it may read random pages or sections of the textbook, it may go to sleep, or it may just get up and go outside, to name a few of the options. If it has a goal, however, to complete a specific homework assignment, such as chapter 6, problems 1 to 10, from the textbook using the computer, the agent’s scope of possible action choices narrows greatly. With this goal, any action that does not result in the completion of problems 1 to 10 from chapter 6 of the textbook using the computer is immediately dismissed. This way, the only courses of action left to choose from are the ones that result in the agent’s assignment being completed.
Without the formulation of a goal preceding the formulation of a problem, the problem typically becomes much more difficult to find a solution to, as there is nothing to point the agent in the proper direction, so to speak. As taken verbatim from page 65 of the textbook, “Goals help organize behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider.”
3.2 Your goal is to navigate a robot out of a maze. The robot starts in the center of the maze facing north. You can turn the robot to face north, south, east, or west. You can direct the robot to move a certain distance, although it will stop before hitting a wall.
a. Formulate this problem. How large is the state space?
The initial state of this problem is the center of the maze, where the robot starts and is facing north. The robot is capable of facing north, south east, or west and can move a certain distance as directed by the user controlling it. It will stop, however, if it comes too close to a wall, in order to avoid hitting it. Since the robot can move a certain distance and is capable of facing north, south, east, or west, it is able to move a certain distance north, south, east, or west. Given these options, with any direction the robot moves in, it will either stop upon reaching a wall to avoid hitting it, or progress further through the maze. The robot has a total of five possible actions; face north, face south, face east, face west, and move. It can move in the direction it is facing unless it reaches a wall. In which case, it will stop before hitting the wall. So, there are two possible outcomes for any action is takes; the robot can either move in the direction it is facing or it cannot because it has reached a wall. Since there are 4 possible directions that the robot can move in, for a location of size n, there are 4n possible world states.
Problem Formulation (using the problem formulation format found here http://w5.cs.uni-saarland.de/teaching/ss12/ki/slides/pre-handouts/ai03-search-pre-handout-4up.pdf)
Initial state: Middle of the maze, facing north. Following the textbook’s format, (In (start), face(n))
Successor function: (In (state), face(x)) //x = n, s, e, or w
State space: n possible locations, 4 possible directions to move in, so there are 4n possible world states
Actions: face north, face south, face east, face west, move
Goal: reach any location outside of the maze
b. In navigating a maze, the only place we need to turn is at the intersection of two or more corridors. Reformulate the problem using this observation. How large is the state space now?
If the intersections of the corridors make up some part of the n locations that the state consists of (n – i), and there still only 2 possible outcomes for an action performed at a state (2(n – i)), but the 4 different direction-facing actions that the robot can do are now determined only at intersections (meaning the 4n in the previously mentioned state space now becomes 4i), the new state space is 4i + 2(n – i).
To clarify:
Since the robot only turns at the locations of intersections of corridors (which I’ve represented with i) instead of at any location in the state (represented by n), the state space, which was 4n in part a, now becomes 4i.
Furthermore, since the intersections are obviously part of the locations of the state, i is contained within n. And since the robot performs its direction changes at only i, it must be moving at all other n except for i, which is where (n – i) comes from. Finally, the only 2 possible outcomes of the robot’s movement (move forward or stop upon reaching a wall) are included, making the total state space 4i + 2(n – i).
c. From each point in the maze, we can move in any of the four directions until we reach a turning point, and this is the only action we need to do. Reformulate the problem using these actions. Do we need to keep track of the robot’s orientation now?
If the robot now has the ability to move on its own in any direction and the only action that needs to be performed is now turning, then the 4 and the 2(n-i) previously included in the state space can be removed. This is due to the fact that the 4 represented the 4 directions in which the robot is capable of moving, while the 2(n-i) represented the locations within the state that the robot moved and the possible outcomes of those movements, all of which have been excluded in this part of the problem. Thus, all that is left to represent the state space is i. Another byproduct of all of these actions being excluded is that we do not need to keep track of the robot’s orientation now, since it performs all of its actions without the user’s control.
d. In our initial description of the problem we already abstracted from the real world, restricting actions and removing details. List three such simplifications we made.
The first missing detail I noticed was the lack of information about the robot’s design, considering that it can apparently turn, but cannot move diagonally at all, only in a straight line in 4 different directions. There was also a lack of detail about the maze itself. If the maze has any dead ends, the robot would be stuck due to the fact that it can only turn at intersections. This problem also assumes that the robot’s sensors work flawlessly 100% of the time and the robot never hits a wall.
Computer Architecture Homework 4
Ed Smart
CSC 320
Homework 4
4.1 Instruction Interpretation
a. AND Rd, Rs, Rt Reg[Rd]=Reg[Rs] AND Reg[Rt]
b. SW Rt, Offs(Rs) Mem[Reg[Rs]+Offs]=Reg[Rt]
4.1.1 What are the values of control signals generated by the control in Figure 4.2 for this instruction?
a. The control signals generated by the control in Figure 4.2 for this instruction are MemRead, MemWrite, RegWrite, ALU operation, Branch, ALU Mux and Reg Mux
4.1.2 Which resources (blocks) perform a useful function for this instruction?
Computer Architecture Homework 3
Ed Smart
CSC 320
Homework 3
3.1 The following table shows pairs of octal numbers.
. A B
a. 3174 0522
b. 4165 1654
3.1.1 What is the sum of A and B if they represent unsigned 12-bit octal numbers? The result should be written in octal.
a. 3174
+ 0522
—————-
. 3716
The sum of the octal numbers 3174 and 0522 is 3716. First, 4 and 2 are added, giving a result of 6 in the ones place. Next, 7 and 2 are added. Since the numbers are in octal (base 8), they cannot simply give a sum of 9 as they would in decimal (base 10) since single digits in octal cannot exceed 7, the same way they cannot exceed 9 in decimal. If the problem was in decimal numbers and the 7 in 3174 was changed to a 9, once it was added to the 2 in 0522’s tens place, it would result in a 1 with 1 being carried over to the hundreds place. The same concept applies in octal. Since these numbers are in octal, when 2 is added to 7 (summing to 9), 8 is reached, so a 1 is carried over to the hundreds column and the remaining 1 left over (9-8=1) is placed in the tens place. The 1 carried over from the tens column is then added to the 1 in 3174, which is then added to the 5 in 0522 (1+1+5=7). Finally, 3 is added to 0, giving a final sum of 3716.
b. 4165
+ 1654
—————–
. 6041
The same concepts explained in answer a are used here. 5 and 4 are added first, resulting in 9, so a 1 is carried to the tens column and the remaining 1 is put in the ones place. Then, 6 and 5 are added to the carried 1, giving 12 (1+6+5=12), so a 1 is carried to the hundreds column and the remaining 4 (12-8=4) is placed in the tens place. Next, the 1 and 6 are added along with the carried 1 from the tens column, giving 8 (1+1+6), so a 1 is again carried and 0 is put in the hundreds place. Finally, the carried 1 is added to 4 and 1, resulting in 6 (1+4+1=6), which is placed in the thousands.
There are a number of other approaches to this problem, such as converting the numbers to other formats, solving the equations, and the results back into base 8. For example, you could convert the numbers to base 10, add them, then convert the sum back to base 8.
First, in order to convert a number from base 8 to base 10, pick the highest power of 8 that is less than the number to be converted. Then, starting from the leftmost digit of the number, multiply each digit by descending powers of 8. Finally, add all of the quantities together. The resulting sum is the decimal form of the original octal number.
For example, to convert 8^^3174 to base 10:
8^3=512 #Highest power of 8 less than 3174
(3*8^3=1536) + (1*8^2=64) + (7*8^1=56) + (4*8^0=4) #Multiply each digit in 3 1 7 4 by a corresponding power of 8, in descending order
1536 + 64 + 56 + 4 = 1660 #8^^3174 = 10^^1660
And then the same is done to convert the second octal number, 0522:
8^3 = 512
(0*8^3) + (5*8^2) + (2*8^1) + (2*8^0)
0 + 320 + 16 + 2 = 338
8^^0522 = 10^^338
Then, the decimal values are added for part a:
a. 8^^3174 = 10^^1660
+ 8^^0522 = 10^^0338
—————- —————
. 1998
And now to convert 1998 from base 10 back to base 8. To do this, divide 1998 by 8. Record the remainder and divide the rest of the quotient again by 8. Repeat this process, while recording the remainders, until a quotient that is less than 8 is reached. Once this point is reached, list all of the remainders and add the final quotient (which is less than 8) to the end of the list. Then, simple read the list backward. This is the base 8 version of 1998.
1998 / 8 = 249, r6
249 / 8 = 31, r1
31 / 8 = 3, r7
3 < 8
10^^1998 = 8^^3716
As you can see, this approach gives the same result as the first one used.
If the same method is applied to part b, the first step is to again convert the octal numbers to decimal. Starting with 4165:
8^4 = 4096
(0*8^4) + (4*8^3) + (1*8^2) + (6*8^1) + (5*8^0)
. 0 + 2048 + 64 + 48 + 5 = 2165
8^^4165 = 10^^2165
Then the same is done for the second number, 1654:
8^3 = 512 #Again 8^3 is used, as it is the highest power of 8 that is less than the octal number to be converted
(1*8^3) + (6*8^2) + (5*8^1) + (4*8^0)
512 + 384 + 40 + 4 = 940
8^^1654 = 10^^940
b. 8^^4165 = 10^^2165
+ 8^^1654 = 10^^0940
—————- —————
. 3105
10^^3105 is then converted to base 8, since the question asks for the sum to be in octal.
3105 / 8 = 388, r1
388 / 8 = 48, r4
48 / 8 = 6, r0
6 < 8
10^^3105 = 8^^6041
Again, this approach gives the same result as the first approach.
Another approach would be to convert the octal numbers to binary and then convert the sum back to octal after the addition is performed. First, the numbers must be converted from octal to binary. This is done by simply converting each digit in the number into its binary counterpart. For example:
3 1 7 4 in octal = 011 001 111 100 in binary
a. 8^^3174 = 2^^011001111100
+ 8^^0522 = 2^^000101010010
—————— —————————
. 011111001110
Then, the binary sum must be converted back to octal. 011 111 001 110 in base 2 = 3 7 1 6 in base 8, or 3716.
b. 8^^4165 = 2^^100001110101
+ 8^^1654 = 2^^001110101100
—————— ————————–
. 110000100001
2^^110000100001 = 8^^6041
As you can see, the result of this method is the same as shown in the previous methods.
3.1.2 What is the sum of A and B if they represent signed 12-bit octal numbers stored in sign-magnitude format? The result should be written in octal.
. A B
a. 3174 0522
b. 4165 1654
If the octal numbers are converted into signed 12-bit binary numbers stored in sign-magnitude format:
a.
8^^3174 = 2^^011 001 111 100
8^^0522 = 2^^000 101 010 010
The most significant bit (leftmost bit) in a signed binary number is the sign bit, which determines whether the number is positive or negative. This means that the bit is no longer a part of the numbers that the operation is being performed on, but rather serves as a sign.If the bit is a 0, the number is positive. If the bit is a 1, the number is negative. As you can see, both of the above numbers are positive as they both have a 0 in the sign bit.
. 8^^3174 = 2^^011 001 111 100
+ 8^^0522 = 2^^000 101 010 010
——————- —————————–
. 011 111 001 110
The binary sum must then be converted to octal:
2^^011111001110 = 8^^3716
b.
8^^4165 = 2^^100 001 110 101
8^^1654 = 2^^001 110 101 100
Part b is approached in a similar fashion. Notice, however, that when 4165 is converted from base 8 to base 2, the most significant bit (or sign bit, in the case of sign-magnitude format) is a 1 this time because the leading 4 is represented as 100 in base 2. As mentioned earlier, this means that the number is negative, while 1654 remains positive when converted to base 2. This means that the operation is adding a negative number to a positive one. In other words, subtracting.
Due to the fact that the most significant bit in 100001110101 is serving as the sign bit, it is excluded from the actual value of the number. And since the other 2 bits that combine with it to form the leading digit 100, or 4, are both zeros, the first digit in 4165 in this case is now 0, making the new octal number -0165.
Thus, the equation for the sum is written in octal numbers as:
. 1654
. – 0165
————-
. 1467
3.1.3 Convert A into a decimal number, assuming it is unsigned. Repeat assuming it stored in sign-magnitude format.
. A B
a. 3174 0522
b. 4165 1654
a. So, the first octal number to be converted into decimal, assuming it to be unsigned, is 3174.
In order to convert 8^^3174 to base 10, the highest power of 8 that is less than 3174, 8^3, is multiplied by the first digit in 3174, the 3. Similarly, the rest of the digits in the number 3174 are each individually multiplied by powers of 8 in descending order until the last digit in the octal number is multiplied by 8^0. All of the resulting quantities are then added together. The sum of these quantities is the decimal version of the octal number originally presented. So, the process looks like this:
8^3 = 512 #Highest power of 8 less than 3174
. (3*8^3) + (1*8^2) + (7*8^1) + (4*8^0) #Octal digits multiplied by descending powers of 8
. 1536 + 64 + 56 + 4 = 1660 #Quantities are summed for final result
8^^3174 unsigned = 10^^1660
b. The same method is applied for part b. Here, the octal number to be converted to decimal is 4165. Again, the first step is to find the highest power of 8 that is less than the octal number to be converted, 4165, in this case. This time, that happens to be 8^4 (4096). However, using the method used in the previous problem, you will notice that, since 8^4 is being used here, the number 4165 basically runs out of digits with which to multiply powers of 8, as seen here:
(4*8^4) + (1*8^3) + (6*^8^2) + (5*8^1) + no digits left to multiply 8^0 by
So, in order to fix this issue, a 0 is added to the beginning of the octal number, making it 04165. Now the equation looks like this:
(0*8^4) + (4*8^3) + (1*8^2) + (6*8^1) + (5*8^0)
. 0 + 2048 + 64 + 48 + 5 = 2165
8^^4165 unsigned = 10^^2165
In order to convert the octal numbers into decimal, assuming they are stored in sign-magnitude format, the numbers should be converted first to binary, in order to check the most significant bit (MSB) to see whether the numbers are positive or negative. If the MSB in a binary number stored in sign-magnitude format is a 0, the number is positive. If the MSB is a 1, the number is negative. The MSB in sign-magnitude numbers is no longer a countable, operable part of the number, it is essentially a +/- sign. Since these numbers have all so far been in 12-bit format, if they are in sign-magnitude format, values can only be displayed using the rightmost (or least significant) 11 bits. The 12th, or most significant bit, is reserved for the 0 or 1 that represents the + or – sign.
a. 3174
When converted to binary, 3174 becomes 011 001 111 100. The most significant bit here is a 0, meaning the number is positive. When the MSB is excluded from the number itself, the first digit remains the same in this case, 011 becomes 11, which is still 3. So, the number remains the same, positive 3174. To convert it to decimal, the same method shown above for unsigned numbers is used.
(3*8^3) + (1*8^2) + (7*8^1) + (4*8^0)
1536 + 64 + 56 + 4 = 1660
8^^3174 sign-magnitude = 10^^1660
b. 4165
The same is done for part b for the octal number 4165. When converted to binary, it becomes 100 001 110 101. In this case, the MSB is a 1, meaning the number is negative. Excluding the sign bit from the number, 11 bits are left with which to represent the rest of the number. Notice that the rest of the bits used to represent the leftmost digit in 4165 are now 00. This means that the number is now -0165.
(1*8^2) + (6*8^1) + (5*8^0)
. 64 + 48 + 5 = 117
And when the sign bit is included, it is -117.
8^^4165 sign-magnitude = 10^^-117
3.1.4 What is A – B if they represent unsigned 12-bit octal numbers? The result should be written in octal.
. A B
a. 7040 0444
b. 4365 3412
a. 7040
– 0444
————-
. 6374
Subtraction between octal numbers can be done by hand from right to left, just like addition, using the same concepts as decimal subtraction. In this case, the octal number 0444 is being subtracted from the octal number 7040. Starting at the right (the ones column), the first operation to be performed is 0 – 4. Since 4 cannot be subtracted from 0 in this manner, a value must be borrowed from the tens column (or eights column, in the case of base 8) and added to the 0 in the ones column so that the operation can be performed. In base 8, the value that is borrowed is 8, just as it is 10 in base 10. So, 1 is subtracted from the 4 in the eights column, allowing 8 to be added to the 0 in the ones column. So, at this point, the operation is 7038 – 0444.
After subtracting 4 from 8 and placing 4 in the ones place, the eights column is addressed. Since the original 4 in 7040’s eights place was borrowed from, it is now 3, which cannot be subtracted from the 4 in 0444’s eights place, so another borrow must be done, this time from the hundreds place (or 64s place in base 8). However, since the 64s column in 7038 contains a 0, the 512s column mu be borrowed from. The borrowed 8 from the 512s column is then placed in the 64s column. The 3 in the eights column can then borrow from the 64s column, making it 11, which is then subtracted from 4, resulting in a 7 being placed in the eights place.
Now, the last 4 in 0444’s 64s place is subtracted from the remaining 7 in the 64s place, resulting in a 3 being placed in the 64s place. Finally, the operation between the last two digits, 6 and 0 in the 512s place, makes the first digit of the answer 6. So, now, we have the difference of 8^^7040 – 8^^0444 = 8^^6374.
b. 4365
– 3412
————-
. 0753
Part b requires quite a bit less work than part a. Using the same method as shown in part a, first the digits in the ones column are subtracted. in this case, 2 is subtracted from 5, resulting in 3 being stored in the ones place. Next, in the eights column, 1 is subtracted from 6, resulting in 5 being placed in the eights column. Then, in the 64s column, 4 is being subtracted from 3, so an 8 must be borrowed from the 4 in the 512s column of 4365. The resulting 11 (8+3=11) is then subtracted from 4 and a 7 is placed in the 64s place. Finally, the leading 3 in 3412 is subtracted from the remaining 3 in the leftmost bit of 4365 after the carry, resulting in 0. So, the difference of 8^^4365 – 8^^3412 = 8^^0753.
3.1.5 What is A – B if they represent signed 12-bit octal numbers stored in sign-magnitude format? The result should be written in octal.
a. If the numbers are signed 12-bit octal numbers stored in sign-magnitude format, they should be converted into binary in order to determine the whether they are positive or negative by checking the MSB (sign bit in sign-magnitude format).
Starting with 8^^7040 = 2^^111 000 100 000
In this case, since the leading digit is a 7, the MSB is a 1, which means that the number is negative. Excluding the sign bit, the number is now (0)11 000 100 000, or 8^^-3040.
Doing the same for 8^^0444 = 2^^000 100 100 100
Here, the MSB is a 0, meaning that the number is positive. Excluding the sign bit, the number remains the same; (0)00 100 100 100, or 8^^0444
-3040
-0444
—————-
-3504
Since subtracting a positive number from a negative number is basically the same as addition, the result of this equation is acquired through the same method as addition, not subtraction. Values are carried, not borrowed. First, 0 and 4 are added, summing to 4 in the ones place. Next, the two 4’s in the eights column are added, resulting in 8, so a 0 is placed in the eights place and a 1 is carried over to the 0 in -3040’s 64s column. That 1 is then added to 4, giving the 64s place a 5 digit. Finally, 3 and 0 are added, and the resulting 3 is placed in the 512s place. The result is 8^^-3040 – 8^^0444 = 8^^-3504.
On a side note, I’ve noticed that, in sign-magnitude format, if the leftmost octal digit is 0, 1, 2, or 3, the number is positive. However, if the leftmost octal digit is 4, the value in sign-magnitude becomes -0. If the digit is a 5, it becomes -1. If it is 6, it becomes -2, or if it is 7, it becomes -3.
b. First, the octal numbers are converted to binary. 8^^4365 = 2^^100 011 110 101, 8^^3412 = 2^^011 100 001 010
Due to the leftmost bit in 4365 being a 4, the leftmost bit in its binary conversion (100 011 110 101) is a 1. This means that the number is negative. After excluding the sign bit, the number becomes (0)00 011 110 101, or 8^^0365. Including the sign makes it 8^^-0365. Just as in part a, the second octal number here, 3412, is positive and remains the same. The MSB is a 0, making the number positive. The remaining digits are then (0)11 100 001 010, or 8^^3412.
-0365
-3412
———
-3777
The same operation as performed in part a is performed here. The numbers are added, since the signs are the same (negative sign in -0365 and subtraction sign next to 3412) starting with the 5 and 2 in the ones column, giving a 7 to the ones place. Then, the 6 and 1 in the eights column are added together and the resulting 7 is placed in the eights place. Next, the 3 and 4 in the 64s column are added, again summing to 7, which is stored in the 64s place. Finally, the leftmost digits, 0 and 3, are added and the resulting 3 is stored in the 512s place. Thus, the difference of 8^^-0365 – 8^^3412 = 8^^-3777.
3.1.6 Convert A into a binary number. What makes base 8 (octal) an attractive numbering system for representing values in computers?
Converting octal numbers into binary numbers is a fairly straightforward process. Simply replace each digit in the octal number with the binary counterpart of the digit. For example, using 7040:
a. 8^^ 7 0 4 0 = 2^^111 000 100 000
The binary representation of 7 is 111, 0 would be 000, 4 is 100, and again, 0 is 000. Putting this together, you get 8^^7040 = 2^^111000100000.
b. 8^^4 3 6 5 = 100 011 110 101
The binary representation of 4 is 100, 3 is 011, 6 is 110, and 5 is 101. Putting these numbers together gives 8^^4365 = 2^^100011110101.
The reason that base 8 (octal) is an attractive numbering system for representing values in computers is the fact that 8 = 2^3, meaning that each octal digit displays exactly 3 binary digits, thus making base 8 a very efficient shorthand for base 2.
I’ve checked all of my math and conversions for accuracy using http://www.wolframalpha.com.
3.2 The following table shows pairs of hexadecimal numbers.
. A B
a. 1446 672F
b. 2460 4935
3.2.1 What is the sum of A and B if they represent unsigned 16-bit hexadecimal numbers? The result should be in hexadecimal.
Hexadecimal is another well-known numbering system that stands alongside octal and decimal. Just as octal is a base 8 number system consisting of the digits 0, 1, 2, 3, 4, 5, 6, and 7 and decimal is a base 10 system consisting of the digits 0 – 9, hexadecimal is a base 16 number system using the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F, where A represents 10, B is 11, C = 12, D is 13, E is 14, and F is 15. Despite looking quite different from other number systems, such as base 8 and base 10, due to have letters instead of just numbers, the same concepts that apply in other number systems still apply in base 16.
For example, addition in hexadecimal works the same way as it would in other number systems. Here, F (or 15) is the highest digit, the same way 9 is the highest digit in decimal and 7 is the highest digit in octal.
a. 1446
+ 672F
———–
. 7B75
In this equation, the first operation performed is the addition of the two rightmost digits, 6 and F. Remember that F represents 15, so 6 + F = 21. Since F is the greatest digit that can be represented in base 16, and 21 > F, 21 must be carried to the next column, just as a number greater than 7 would be in base 8 or a number greater than 9 would be in base 10. So, the difference of 21 and 16, which is 5, is placed in the ones place and a 1 is carried over to the tens column (or 16s column in the case of base 16). Next, the carried 1 is added to the 4 and 2 in the 16s column and the resulting 7 (1+4+2=7) is placed in the 16s place. Then, the digits in the 256s column, 4 and 7, are added, which gives 11. Since the value of 11 is represented by the digit B, there is no need to carry here, as there would’ve been in base 8 or 10. Finally, the two rightmost digits, 1 and 6, are added and the resulting 7 is stored in the 4096s place. Thus, the final sum of 16^^1446 + 16^^672F = 16^^7B75.
b. 2460
+ 4935
————
. 6D95
Part b is solved the same way. There are not even any carries this time. First, 0 and 5 are added, and 5 is put in the ones place. Next, 6 and 3 are added, with the sum being stored in the 16s place. Then, moving to the 256s column, 4+9=13. Since 13 = D in base 16, there is no need to carry, so D is placed in the 256s place. Finally, 2+4 results in a 6 in the 4096s place.
3.2.2 What is the sum of A and B if they represent signed 16-bit hexadecimal numbers stored in sign-magnitude format? The result should be written in hexadecimal.
a. If A and B represent signed 16-bit hexadecimal numbers stored in sign-magnitude format, in order to operate with them, their signs must first be determined.
Some useful observations I’ve made:
16^^1446
(1*16^3) + (4*16^2) + (4*16^1) + (6*16^0)
4096 + 1024 + 64 + 6 = 10^^5190 = 2^^0001 0100 0100 0110
16^^672F
(6*16^3) + (7*16^2) + (2*16^1) + (15*16^0)
24576 + 1792 + 32 + 15 = 10^^26415 = 2^^0110 0111 0010 1111
Base 16 numbers can also be converted directly to base 2 without converting to base 10 in the process, the same way base 8 is converted to base 2. The only difference is that base 16 digits display 4 base 2 digits, where base 8 displayed 3. For example:
16^^1 4 4 6 = 2^^0001 0100 0100 0110
The last 4 bits in the binary number represent the last digit in the hexadecimal number, in this case, 6. The second to last group of 4 bits in the binary number represent the second to last digit in the hexadecimal number, which is 4 here. The second leftmost group of 4 bits in the binary number represent the second leftmost digit in the hexadecimal number, which is also 4. Finally, the leftmost group of 4 bits represents the leftmost digit in the hexadecimal number, which is 1 here.
Also, just as with signed base 8 numbers with leftmost digits 4, 5, 6, and 7 becoming -0, -1, -2, and -3, a similar rule seems to apply to base 16 numbers. Looking at the 4 most significant bits in the base 2 conversions shown above, you will notice that the MSB would be a 1 if the leftmost digit in the base 16 number was an 8, making the 4 most significant digits 1000, or -0 in sign magnitude format. Similarly, if the leftmost base 16 digit was a 9, the 4 leftmost digits digits in the binary number would be 1001, or -1 in sign-magnitude format. Continuing with this pattern, A would be -2, B would be -3, C would be -4, D would be -5, E would be -6, and F would be -7.
Moving on to the problem. Using the information stated above, it is apparent that the base 16 numbers 1446 and 672F are both positive if stored in sign-magnitude format because the most significant digit is less than 8 in both cases. This is further proven by the fact that neither number has a 1 as its most significant bit when converted to base 2. 16^^1446 = 2^^0001 0100 0100 0110, 16^^672F = 2^^0110 0111 0010 1111
. 1446
+ 672F
————
. 7B75
Thus, the operation and result remain the same as the unsigned version in this case. Again, 6 and F are added first, the sum is 21, so 1 is carried to the next column and 5 is stored in the ones place. Then, the carried 1 is added to 4 and 2, and 7 is stored in the 16s place. Next, 4 and 7 are added, and the resulting 11 is represented in the 256s place as B. Finally, the leftmost 1 and 6 are added, with the resulting 7 being placed in the 4096s place, giving the final sum of 16^^7B75.
b. The same methods used in part a are used to solve part b. 2460 and 4935 are the two base 16, 16-bit numbers stored in sign-magnitude format to be added. Notice that, once again, neither number has a most significant digit of 8 or greater. This means that both numbers are positive and can be added just as they were earlier.
. 2460
+ 4935
————-
. 6D95
Just as they were added in the unsigned problem, the 0 and 5 are first added and 5 is placed in the ones column. Next, the 6 and 3 are added, resulting in 9 in the 16s column. 4 and 9 are then added, summing to 13, which is represented by D in the 256s place. Finally, 2+4=6 in the 4096s place.
3.2.3 Convert A into a decimal number, assuming it is unsigned. Repeat assuming it stored in sign-magnitude format.
In order to convert a base 16 number into base 10, each digit in the base 16 number is multiplied by a corresponding power of 16, in descending order. So, for 16^^1446, 1 is multiplied by 16^3, the leftmost 4 is multiplied by 16^2, the second 4 is multiplied by 16^1, and 6 is multiplied by 16^0. All of the quantities are then added together. The sum is the base 10 representation of 16^1446.
a. 16^^1446
(1*16^3) + (4*16^2) + (4*16^1) + (6*16^0)
4096 + 1024 + 64 + 6 = 5190
16^^1446 = 10^^5190
b. 16^^2460
(2*16^3) + (4*16^2) + (6*16^1) + (0*16^0)
8192 + 1024 + 96 + 0 = 9312
16^^2460 = 10^^9312
Due to the fact that 16^^1446 and 16^^2460 both have most significant digits below 8, they would both be positive numbers if stored in sign-magnitude format. Thus, their values remain the same.
a. 16^^1446 sign-magnitude
(1*16^3) + (4*16^2) + (4*16^1) + (6*16^0)
4096 + 1024 + 64 + 6 = 5190
16^^1446 sign-magnitude = 10^^5190
b. 16^^2460 sign-magnitude
(2*16^3) + (4*16^2) + (6*16^1) + (0*16^0)
8192 + 1024 + 96 + 0 = 9312
16^^2460 sign-magnitude = 10^^9312
3.2.4 The following table also shows pairs of hexadecimal numbers.
. A B
a. C352 36AE
b. 5ED4 07A4
What is A – B if they represent unsigned 16-bit hexadecimal numbers? The result should be written in hexadecimal.
a. C352
– 36AE
—————-
. 8CA4
Since the numbers are unsigned here, they are simply subtracted. Starting from the right, since E cannot be subtracted from 2, a 16 is borrowed from the 5 in the next column. the resulting 18 is then subtracted from E, leaving 4 in the ones place. Next, since A cannot be subtracted from 4 (since it was borrowed from, 5-1=4), another 16 is borrowed from the next column. The result is 20, from which A is subtracted, leaving A in the 16s place. Then, since 6 cannot be subtracted from 2 (since 3 was borrowed from, 3-1=2), yet another borrow must be done from the next column, reducing C in the 4096s column to B and increasing 2 to 18. 6 is then subtracted from 18, resulting in C being stored in the 256s place. Finally, 3 is subtracted from the remaining B, leaving 8 in the 4096s place. So, 16^^C352 – 16^^36AE = 16^^8CA4.
b. 5ED4
– 07A4
—————
. 5730
Part b follows the same steps, but requires quite a bit less work. There are no carries involved. To begin with, 4 is subtracted from 4, leaving 0 in the ones place. Next, A is subtracted from D, resulting in a 3 in the 16s place. Then, 7 is subtracted from E, leaving 7 in the 256s place. Finally, 0 is subtracted from 5, so the leftmost digit is 5. 16^^5ED4 – 16^^07A4 = 16^^5730.
3.2.5 What is A – B if they represent signed 16-bit hexadecimal numbers stored in sign-magnitude format? The result should be written in hexadecimal.
a. Since the numbers are signed and stored in sign-magnitude format, the value of C352 changes, due to the fact that its leftmost digit is C >= 8. For hexadecimal numbers stored in sign-magnitude format with a leftmost digit of 8 or greater, the value becomes negative because leftmost digits 8 and greater have a MSB of 1 when converted to base 2. In this format, a hexadecimal number with a 0, 1, 2, 3, 4, 5, 6, or 7 as the most significant digit remains the same, while a hexadecimal number with a most significant digit of 8 becomes -0 (16^^8 = 2^^1000, 1 becomes the negative sign bit and the remaining 3 bits represent the number, which is now 0 in this case). Following this pattern, a 9 as the most significant digit in a base 16 number becomes -1 in sign-magnitude format (16^^9 = 2^^1001, the leftmost 1 is again used to represent the negative sign bit, while the remaining 3 bits represent the number, which becomes 1). So, A as the most significant hexadecimal digit in sign magnitude format becomes -2, B becomes -3, C becomes -4, D becomes -5, E becomes -6, and F becomes -7.
With this in mind, it is apparent that the first hexadecimal number in part a, C352, becomes -4352 in sign-magnitude format, since C >=8. 16^^C = 2^^1100.Since the MSB is reserved for the sign bit, which is negative, the remaining 3 bits, 100, are used to represent the leftmost digit, which then becomes 4. The second hexadecimal number in the problem, 36AE, however, remains the same due to its leftmost digit being below 8. The leftmost digit is 3, and 16^^3 = 2^^0011. So, theMSB indicates that the number is positive, and since the number 3 only requires the two rightmost bits to be represented, it remains unchanged if its leftmost bit is reserved for the sign bit.
. -4352
– 36AE
————–
. -7A00
Since a positive number is being subtracted from a negative number, addition is performed and the negative sign is kept. 2+E=16, so a 0 is put in the ones place and a 1 is carried. 1+5+A=16 again, so a 0 is put in the 16s place and a 1 is carried again. 1+3+6=A, so A ends up in the 256s place. Finally, 4+3=7 in the 4096s place.
b. By looking at the leftmost digits of both numbers in part b, it is apparent that the problem will be much less eventful than part a. The leading digits of both are a 5 and a 0, so when in sign-magnitude format, the values remain the same.
. 5ED4
– 07A4
————–
. 5730
No negative numbers, no value conversions, no borrows, nothing. Just basic subtraction of two positive numbers, the same operation presented in part b of the unsigned problem. First, 4 is subtracted from 4, leaving 0 in the ones place. Next, A is subtracted from D, and the resulting 3 is stored in the 16s place. Then, 7 is subtracted from E, leaving 7 in the 256s place. Finally, 0 is subtracted from 5, so 5 is placed in the 4096s place.
3.2.6 Convert A into a binary number.What makes base 16 (hexadecimal) an attractive numbering system for representing values in computers?
To convert base 16 numbers to base 2, simply use 4 bits to represent each digit in the base 16 number.
a. C352, C (or 12) represented in binary is 1100, 3 is 0011, 5 is 0101, and 2 is 0010.
16^^C 3 5 2 = 2^^1100 0011 0101 0010
b. 5ED4, 5 represented in binary is 0101, E (or 14) is 1110, D (or 13) is 1101, and 4 is 0100
16^^5 E D 4 = 2^^0101 1110 1101 0100
Base 16 is an attractive numbering system for representing values in computers because 16 = 2^4, so each digit in a hexadecimal number displays 4 bits. Due to this, a byte (8 bits) can be specified by exactly 2 hexadecimal digits.
I’ve checked all of my math and conversions for accuracy using http://www.wolframalpha.com.
Artificial Intelligence Homework 2
Ed Smart
CSC 375
Homework 2
2.1 Suppose that the performance measure is concerned with just the first T time steps of the environment and ignores everything thereafter. Show that a rational agent’s action may depend not just on the state of the environment but also on the time step it has reached.
My first thought regarding this question was that a rational agent could be involved in some sort of time-limited event or activity, such as a sports game. In such a scenario, the agent would be required to play against an opponent and accumulate more points than the opponent within a predetermined amount of time. So, the duration of the game would be the T time steps that the performance measure is concerned with. In a game of soccer, for example, goals may be scored outside the game’s duration, but obviously, they do not matter. The agent’s style of play or tactics may change during the game depending on the score relative to the remaining time. If the agent has a comfortable point lead over its opponent with little time remaining in the game, it may choose to simply play defensively for the remainder. On the other hand, if the agent has a lower score than its opponent and there is a considerable amount of time remaining, it may choose to play more offensively in order to gain points.
Another situation in which a rational agent’s actions may depend on the time step is has reached could be taking a long exam in some given amount of time. If the agent has 60 minutes to complete 30 exam problems and has 20 problems finished after 45 minutes, it may start skipping the problems that it finds to be more difficult or time consuming and focusing on the easier or shorter ones in order to maximize the amount of problems it can answer, instead of just completing them in the order they are given and possibly not having time to answer some of the easy questions.
2.2 Let us examine the rationality of various vacuum-cleaner agent functions.
a. Show that the simple vacuum-cleaner agent function described in Figure 2.3 is indeed rational under the assumptions listed on page 38.
The first assumption listed on page 38 states that the performance measure awards 1 point for each clean square at each time step over a lifetime of 1000 time steps. Based on this, the agent behaves rationally, as it moves back and forth from square to square looking for dirt to clean and moving to the other square if none is found. If the performance measure included any sort of penalty for movement between squares, however, the agent would not be considered rational, as it just moves back and forth needlessly once the dirt has been cleaned.
The second assumption is that the geography of the environment is known, but the dirt distribution and the agent’s initial location are not. It also states that cleaned squares remain clean and sucking cleans the current square. In this case, the agent also behaves rationally due to the fact that it oscillates from one square to the other checking for dirt and cleaning any that it finds. It is also assumed that the Left and Right actions move the agent left or right respectively, unless doing so would move the agent out of the environment, in which case it remains at its current location. Due to the fact that there are only 2 squares, this assumption solves the problem of the agent not initially knowing its location. If it starts at square A without knowing it is at square A and tries to move left, it remains where it is and has no other choice but to move right and go to square B.
The third assumption is that the only available actions are Left, Right, and Suck. According to this, the agent is rational, as these are the only actions performed by it. It checks the square it is currently at for dirt, sucks it up if any is found, and then moves either left or right to the other square and repeats the process.
The last assumption is that the agent correctly perceives its location and whether that location contains dirt. Looking back at the second assumption, it is clear that the agent is capable of perceiving its location and whether or not that location contains dirt.
b. Describe a rational agent function for the case in which each movement costs one point. Does the corresponding agent program require internal state?
For the case in which each movement costs one point, the agent should stop after checking both squares A and B and removing any dirt found in order to reduce needless movements and loss of points. The corresponding agent program would require internal state in this case, as it would need to remember checking both squares before it stops performing its task. If it finds dirt at square A, cleans it, then moves to square B and finds no dirt, and then does not remember whether or not it checked square A, it will check A again, and then repeat with square B and continue making unnecessary movements, thus losing points.
If the squares did not permanently remain clean, however, the agent could stop for some fixed amount of time after checking and cleaning both squares and repeat its task. It could work at some time interval, checking both squares, cleaning any dirt found, stopping for 1 hour or so, and then repeating the process. This would allow the agent to minimize movements and point loss while keeping the squares clean if they were to become dirty again.
c. Discuss possible agent designs for the cases in which clean squares can become dirty and the geography of the environment is unknown. Does it make sense for the agent to learn from its experience in these cases? If so, what should it learn? If not, why not?
For the case in which clean squares can become dirty, the agent could work at some fixed time interval. It could check and clean both squares A and B, then stop for a fixed amount of time, then start up and repeat the process in order to keep the squares clean while minimizing needless moves and performance measurement point loss. If the geography of the environment is unknown, the agent would need to explore the environment instead of simply oscillating back and forth between squares A and B. I would say it would make sense for the agent to learn from its experience in these cases. It could learn the geography of the environment by exploring it, as well as learning which squares it has checked and cleaned so that it may temporarily stop once it has finished checking and cleaning all of them.
Computer Architecture Homework 2
Ed Smart
CSC 320
Homework 2
2.1 Assume the variables f, g, h, and i are given and could be considered 32-bit integers as declared in a C program.
a. f = g – h;
b. f = g + (h – 5);
2.1.1 For the C statements above, what is the corresponding MIPS assembly code? Use a minimal number of MIPS assembly instructions.
a. sub f, g, h #h is subtracted from g and the difference is stored #in f
b. addi f, h, -5 #Since MIPS can only perform 1 operation at a #time and the value of (h – 5) must be computed #and then added to g, the (h – 5) operation is #performed first and the result is stored in f #The addi operator can be used with a negative #constant to give the same result as #”subtract immediate”
add f, f, g #g is then added to f, which currently contains the #difference of (h – 5), and the new result of g + (h – 5) #is then stored in f
Part b can also be written using a temporary register as such:
addi $t0, h, -5 #5 is subtracted from h and the difference is stored #in a temporary register $t0
add f, g, $t0 #g is added to the value of (h – 5) stored in $t0 and #the result of g + (h – 5) is stored in f
2.1.2 For the C statements above, how many MIPS assembly instructions are needed to perform the C statement?
For the C statements above, the total minimum number of MIPS assembly instructions needed is 3. MIPS can only perform one operation at a time and part b requires 2 operations (subtraction and addition), meaning two instructions are needed. Part a, however, only requires 1 simple sub instruction, making the total number of required instructions 3.
2.1.3 If the variables f, g, h, and i have values 1, 2, 3, and 4 respectively, what is the end value of f?
a. f = g – h;
1 = 2 – 3;
-1 = 2-3;
The end value of f here is -1. f’s initial value of 1 is replaced when the operation between g and h is performed, as the difference between g and h is stored in f.
I decided to throw this problem into MIPS for a better explanation. Register $t0 represents f, $t1 is g, and $t2 is h.
The output:
I ran the program step by step so that you can see the process instead of just the end result. As you can see here, the program has just finished loading the values of f, g, and h into registers $t0, $t1, and $t2 respectively (note the values on the right, where $t2 is highlighted green), but has not yet performed the operation.
And this is after the operation has been performed. Notice the difference of $t1 and $t2 is now stored in $t0, replacing f’s original value of 1 with -1.
b. f = g + (h – 5);
1 = 2 + (3 – 5);
1 = 2 + (-2);
0 = 2 – 2;
The end value of f here is 0. The initial value of f is again replaced when the addition and subtraction operations are completed and the new value is placed in f.
Here’s the MIPS code of the problem for further clarity.
And the outputs:
First, registers $t0, $t1, and $t2 are again given the values of f, g, and h respectively.
Then, as MIPS can only perform one instruction at a time, the problem must be broken into 2 steps. Here, 5 is subtracted from $t2’s value of 3 and the difference of -2 is stored in $t0.
Finally, $t1 is added to $t0 (which now contains the difference of $t2 and 5) and the result is stored in $t0, replacing its previous value of -2 with the final result, 0.
a. addi f, f, 4
b. add f, g, h
add f, i, f
2.1.4 For the MIPS assembly instructions above, what is the corresponding C statement?
a. f = f + 4; //4 is added f and the value of f is replaced with the new //sum
b. f = g + h; //g and h are added and the resulting sum is stored in f
f = i + f; //i is then added to f, which currently holds the value of (g + h), //and the new sum is then stored in f, meaning f = g + h + i
2.1.5 If the variables f, g, h, and i have values 1, 2, 3, and 4 respectively, what is the end value of f?
a. f = f + 4;
1 = 1 + 4; //initial value of f is added to 4
5 = 1 + 4; //sum of f and 4 is stored in f, replacing its initial value
The end value of f here is 5. f’s initial value of 1 is added to 4 and the resulting sum of 5 is then stored in f.
Here’s a brief MIPS code to better illustrate the process using register $t0 to represent f:
The output:
First f’s assigned value of 1 is stored in register $t0.
The constant 4 is then added to $t0, which contains f’s initial value of 1. The sum is then stored in $t0, updating its value to 5.
b. f = g + h;
f = i + f;
1 = 2 + 3; //initial values of f, g, and h respectively
5 = 2 + 3; //initial value of f is replaced by the sum of g and h
5 = 4 + 5; //i is added to the new value of f, which is the sum of g + h
9 = 4 + 5; //f is updated with the sum of i + f, which is equivalent to //(g + h + i)
The end value of f here is 9. The sum of g and h (2 + 3) is 5, which is stored in f. The value of i is then added to f and stored as f’s new value, so f = g + h + i = 2 + 3 + 4 = 9.
Here, I’ve again illustrated the process with some MIPS code:
The output:
First, the values of f, g, h, and i are stored in registers $t0, $t1, $t2, and $t3 respectively.
Then, the values of $t1 and $t2 are added and the sum is stored in $t0, replacing its initial value of 1 with 5.
Finally, the value stored in $t3 is added to the new value stored in $t0, and $t0 is then updated with the final sum of 9.
2.2 Assume the variables f, g, h, and i are given and could be considered 32-bit integers as declared in a C program.
a. f = g – f;
b. f = i + (h – 2);
2.2.1 For the C statements above, what is the corresponding MIPS assembly code? Use a minimal number of MIPS assembly instructions.
a. sub f, g, f #subtract f from g, store difference in f
b. addi f, h, -2 #subtract 2 from h, store difference in f
add f, i, f #add i to f (which contains h – 2), replace f’s #value with new sum
2.2.2 For the C statements above, how many MIPS instructions are needed to perform the C statement?
In total, 3 MIPS instructions are needed to perform the C statements above. Part a requires 1 instruction to subtract f from g and store the difference in f. Part b requires 2 instructions. The first instruction subtracts 2 from h using addi and -2 and stores the difference in f. The second instruction adds i to the value of f (which contains h – 2) and then stores the sum in f, meaning f = i + (h – 2).
2.2.3 If the variables f, g, h, and i have values 1, 2, 3, and 4 respectively, what is the end value of f?
a. f = g – f;
1 = 2 – 1; //initial values, f’s final value remains 1
In this case, the end value of f is the same as its initial value of 1. g = 2 and f = 1, 1 is subtracted from 2 and stored in f.
As shown in MIPS here, where $t0 represents f and $t1 represents g:
First, the values 1 and 2 are stored in registers $t0 and $t1 respectively.
$t0’s value is then subtracted from $t1’s and the difference is stored in $t0, in this case, resulting in $t0’s value remaining the same, as it is overwritten with the difference of 1.
b. f = i + (h – 2);
1 = 4 + (3 – 2);
5 = 4 + 1;
The end value of f here is 5. First, 2 is subtracted from h’s value of 3, resulting in the difference of 1 being stored in f. Then, i’s value of 4 is added to the 1 stored in f and f is updated with the new value of 5.
As shown here, where f, h, and i are stored in registers $t0, $t2, and $t3 respectively:
The output:
First, the values are stored in the registers:
Then, $t0 is updated with the difference of $t2 and 2, which is the same as its original value.
Finally, $t0 is added to $t3 and the sum is stored back into $t0.
a. addi f, f, 4
b. add f, g, h
sub f, i, f
2.2.4 For the MIPS assembly instructions above, what is a corresponding C statement?
a. f = f + 4; //4 is added to f and the sum is stored as f’s new value
b. f = g + h; //g and h are added and the sum is stored in f
f = i – f; //f is then subtracted from i and the difference is //stored in f
2.2.5 If the variables f, g, h, and i have values 1, 2, 3, and 4 respectively, what is the end value of f?
a. addi f, f, 4
addi 1, 1, 4 #initial values, 1 + 4 is added and stored in f
The end value of f in this case is 5. f’s initial value is 1, which is added to the constant 4, resulting in a sum of 5 being stored in f as its new value.
Which can be seen here:
After loading f’s initial value of 1 into register $t0, 4 is then added to that value and $t0’s final value is the sum, which is 5.
b. add f, g, h
sub f, i, f
add 1, 2, 3 #initial values
sub 5, 4, 5 #new value of f is subtracted from i
The end value of f here is -1. First, g and h are added (2 + 3) and the sum of 5 is stored in f. Then, f’s value of 5 is subtracted from i’s value of 4 and the difference of -1 is stored in f.
I’ve shown the process in MIPS here, where f, g, h, and i are represented by registers $t0, $t1, $t2, and $t3 respectively:
Output:
First, the initial values are loaded into their corresponding registers.
$t0’s value is then replaced with the sum of $t1 and $t2, which is 5.
Then, $t0’s new value of 5 is subtracted from $t3’s value of 4 and the resulting -1 is stored back into $t0.
2.3 Assume the variables f and g are given and can be considered 32-bit integers as declared in a C program.
a. f = -g – f;
b. f = g + (-f – 5);
2.3.1 For the C statements above, what is the corresponding MIPS assembly code? Use a minimal number of MIPS assembly instructions.
a. sub f, -g, f #f is subtracted from -g and the difference is stored in f
b. addi f, -f, -5 #addi is used to add -5 to -f, and the sum is stored in f
add f, g, f #g is then added to f and the new sum is stored in f
2.3.2 For the C statements above, how many MIPS assembly instructions are needed to perform the C statement?
For the C statements above, 3 MIPS assembly instructions are needed for part a. Part a requires 1 statement to make g negative by multiplying it by -1. The second statement is used to move -g from the Lo register, where the quantity is stored, to where g is stored. The third statement subtracts f from -g and stored the differences of -3 in f.
Part b requires 4 MIPS assembly instructions. The first one multiplies f by -1 in order to get -f, which is stored in the Lo register. The second one moves -f from Lo back to where f is stored, replacing f’s initial value with -f. The third instruction subtracts 5 from f’s new value and stores the difference in f. The last instruction adds f to g and stores the sum in f.
2.3.3 If the variables f, g, h, i, and j have variables 1, 2, 3, 4, and 5 respectively, what is the end value of f?
a. f = -g – f;
1 = -2 – 1; //initial values
-3 = -2 – 1; //f’s value is replaced with the result of the operation
The end value of f here is -3. 1 is subtracted from -2 and the result is stored in f.
This is shown more clearly here:
First the values are stored in their corresponding registers.
g’s value of 2 is then multiplied by -1 in order to get -g, and the result is stored in the Lo register.
-g is then moved from the Lo register into $t1, replacing g with -g.
f is then subtracted from -g and the result is stored in $t0, replacing f’s initial value of 1 with -3.
b. f = g + (-f – 5);
1 = 2 + (-1 – 5); //initial values
-4 = 2 + (-6); //final value is stored in f after the operation is finished
The end value of f in this case is -4. First, 5 is subtracted from -f’s initial value of -1. The resulting -6 is then added to 2, giving a sum of -4, which is then stored in f.
And here is the problem written in MIPS:
After the initial values are loaded into the registers, f’s initial value of 1 is multiplied by -1 in order to get -f, which is stored in the Lo register.
The -f value contained in Lo is then moved into $t0, replacing f’s initial value with -f.
5 is then subtracted from f and the difference is stored in f.
Finally, f is added to g and the sum is stored in f.
a. addi f, f, -4
b. add i, g, h
add f, i, f
2.3.4 For the MIPS statements above, what is a corresponding C statement?
a. f = f – 4; //The addi operator used with a negative constant is the //same as subtracting a positive constant
b. i = g + h; //h is added to g and the sum is stored in i
f = i + f; //f is then added to i and f is updated with the sum
2.3.5 If the variables f, g, h, and i have values 1, 2, 3, and 4 respectively, what is the end value of f?
a. f = f – 4;
1 = 1 – 4; //initial values
-3 = 1 – 4; //difference is stored in f
The end value of f is -3. 4 is subtracted from f’s initial value of 1 and the difference is then stored in f.
Here is the MIPS code for the problem:
Output:
First, f’s value of 1 is stored in register $t0.
Then, 4 is subtracted from the value of 1 stored in $t0 and $t0 is then updated with the difference, -3.
b. i = g + h;
f = i + f;
4 = 2 + 3; //initial values
5 = 2 + 3; //updated value of i
1 = 5 + 1; //initial value of f is added to updated value of i
6 = 5 + 1; //final result is stored in f
The end value of f is 6. First, g and h are added and the sum is stored in i. Then, f is added to the updated value of i and the result is stored in f.
The problem coded in MIPS:
Output:
First, the values of f, g, h, and i are stored in registers $t0, $t1, $t2, and $t3 respectively.
Then, the value of i stored in $t3 is replaced with the sum of g and h.
Finally, the new value of i is added to f and the sum is stored in $t0.
Artificial Intelligence Homework 1
Ed Smart
CSC 375
Homework 1
1.1 Define in your own words: (a) intelligence, (b) artificial intelligence, (c) agent, (d) rationality, (e) logical reasoning.
(a) intelligence: I would define intelligence as the ability of thought. The ability to perceive one’s surrounding environment and adapt or respond to stimuli in a way that is beneficial to himself in some form. For example, if a person is standing on one side of a busy street and wants to cross it, the intelligent method would be to wait until the cars have stopped and it is safe to cross, instead of putting himself in danger by running through the traffic.
(b) artificial intelligence: My definition of artificial is something that does not occur naturally, or something made by man with the intention of mimicking something in nature. Combining this with my previous definition of intelligence, I would say that artificial intelligence is man-made intelligence or giving the ability of thought to something that does not naturally have it. Building off of my example in my definition of intelligence about the person displaying intelligence by crossing a busy street properly, a similar example could be made for artificial intelligence if the person in that scenario was instead a robot crossing a street.
(c) agent: I would define an agent as a computer program that possesses some degree of artificial intelligence. Agents vary in level of intelligence, but all are capable of perceiving an environment, understanding it, and acting accordingly to accomplish a goal, whether that goal be building the sturdiest structure of a certain size given some amount of materials or simply figuring out the quickest way from point A to point B.
(d) rationality: Rationality can be thought of as an agent’s ability to choose what is generally accepted to be the best possible action based on what the agent knows and given several options. For example, let’s say an agent is on the second floor of a building and its goal is to get outside of the building. Let’s also say that the agent recognizes two possible ways of achieving this goal; going down the stairs and walking out the door or jumping out the window. Using the door would be the rational choice, as jumping out the window would potentially cause serious harm to the agent.
(e) logical reasoning: My definition of logical reasoning would be the ability to make inferences based on previously acquired knowledge in order to obtain new knowledge. If the information “a = b and b = c” is given, one can infer via logical reasoning that a = c. Or if one knows that a stove is hot while it is on and also knows that touching hot things will cause him to get burned, he can infer that touching a stove while it is on will cause him to get burned.
1.3 Are reflex actions (such as flinching from a hot stove) rational? Are they intelligent?
I would say reflex actions are somewhat rational. If one touches a hot stove, given such a small amount of time to consider the situation, he only has two options: to move away from the stove and avoid getting burned or to not move away from the stove and get burned. Obviously, option 1 is preferable to option 2, so a reflex to flinch from a hot stove is an action of limited rationality; acting appropriately when there is not enough time to do all the computations one might like.
As to whether or not reflex actions are intelligent, I think that is debatable. They may not be intelligent because one does not use much thinking power when performing a reflex action. All details of the situation may not be considered properly or at all before the action is made. On the other hand, they may be intelligent because they prove that one is capable of responding to stimuli in his environment and acting in a certain manner to protect himself. Overall, I would say that reflex actions are not intelligent due to the lack of thinking ability involved in them.
1.6 How could introspection—reporting on one’s inner thoughts—be inaccurate? Could I be wrong about what I’m thinking? Discuss.
I believe that introspection could be inaccurate due to the fact that one is consciously reporting his own inner thoughts, which could alter his thought process, possibly causing him to have thoughts that he would not otherwise have. If he is monitoring his thoughts, he may be more focused on thinking about what he is thinking about rather than just freely thinking about whatever comes to mind, such as pondering his plans for the following day. He may have thoughts that he would not typically have if he knows that his thoughts are being monitored. Instead of thinking “What should I make for dinner?”, he may be thinking “What should I think about?”
1.11 “Surely computers cannot be intelligent—they can do only what their programmers tell them.” Is the latter statement true, and does it imply the former?
I do not think there is a concrete answer to this question. The Turing Test lists attributes that a computer may require in order to be considered intelligent, but no computer has ever passed the Turing Test as of yet. Instead, AI researchers believe that it is more important to study the principles of intelligence than it is to design a computer that can pass the Turing Test, as they strive to create computers that have their own intelligence, not mimic the intelligence of humans, as the Turing Test aims to do. The textbook relates the situation to the Wright brothers achieving artificial flight after they stopped trying to imitate birds and brought wind tunnels and aerodynamics into play. Computers are capable of performing limited tasks such as understanding subsets of human language and navigating areas, so I believe a certain amount of intelligence is present.
1.12 “Surely animals cannot be intelligent—they can do only what their genes tell them.” Is the latter statement true, and does it imply the former?
I feel that both statements are false. Animals are capable of thought and learning through experience things they would not know by genetics. For example, a dog is not born knowing what the commands “sit” or “stay” mean, but he is capable of learning them, as well as consciously making the decisions to perform the actions upon hearing the commands. This ability to think and learn can be considered intelligence.
Computer Architecture Homework 1
Ed Smart
CSC 320
Homework 1
1.1 Find the word or phrase from the list that best fits the following description.
1.1.1 Computer used to run large problems and usually accessed via a network.
Server
In the very beginning of the first section of this chapter, the book describes a server as “A computer used for running larger programs for multiple users, often simultaneously, and typically accessed only via a network.”
1.1.2 10^15 or 2^50 bytes.
Petabyte
According to wolframalpha.com, 10^15 bytes = 1 petabyte (PB) and 2^50 bytes = 1.126 petabytes.
1.1.3 A class of computers composed of hundred to thousand processors and terabytes of memory and having the highest performance and cost.
Supercomputer
Chapter 1, page 5 of the textbook: “supercomputer A class of computers with the highest performance and cost; they are configured as servers and typically cost millions of dollars.”
1.1.4 Today’s science fiction application that will probably be available in the near future.
Virtual worlds
There are many online communities which can be thought of as virtual worlds to some extent, such as video games, but true virtual worlds similar to the ones in science fiction movies have yet to be developed.
1.1.5 A kind of memory called random access memory.
RAM
I don’t think an explanation is really needed.
1.1.6 Part of a computer called central processor unit.
CPU
Again, pretty self-explanatory.
1.1.7 Thousands of processors forming a large cluster.
Datacenter
Chapter 1, page 5 of the textbook: “Internet datacenters used by companies like eBay and Google also contain thousands of processors, terabytes of memory, and petabytes of storage. These are usually considered as large clusters of computers.”
1.1.8 Microprocessors containing several processors in the same chip.
Multicore microprocessor
Page 8 of the textbook: “Multicore microprocessor A microprocessor containing multiple processors (“cores”) in a single integrated circuit.”
1.1.9 Desktop computer without a screen or keyboard usually accessed via a network.
Low-end server
1.1.10 A computer used to running one predetermined application or collection of software.
Embedded computers
“An embedded system is a computer system designed to perform one or a few dedicated functions often with real-time computing constraints.” Source: wikipedia.org
1.1.11 Special language used to describe hardware components.
VHDL
“VHDL is the VHSIC Hardware Description Language. VHSIC is an abbreviation for Very High Speed Integrated Circuit.” Source: http://www.doulos.com
1.1.12 Personal computer delivering good performance to single users at low cost.
Desktop computers
A desktop computer is generally thought of as a personal computer that is used by one person at a time.
1.1.13 Program that translates statements in high-level language to assembly language.
Compiler
Chapter 1, page 11 of the textbook “compiler A program that translates high-level language statements into assembly language statements.”
1.1.14 Program that translates symbolic instructions into binary instructions.
Assembler
Page 11 of the textbook: “assembler A program that translates a symbolic version of instructions into the binary version.”
1.1.15 High-level language for business data processing.
Cobol
Cobol a programming language used primarily for business actions. it is an acronym for for Common Business-Oriented Language
1.1.16 Binary language that the processor can understand.
Machine language
Page 11 of the textbook: “machine language A binary representation of machine instructions.”
1.1.17 Commands that the processors can understand.
Instructions
Page 11 of the textbook: “instruction A command that computer hardware understands and obeys.”
1.1.18 High-level language for a scientific computation.
Fortran
Fortran is a programming language that is typically very well suited for numeric and scientific computations.
1.1.19 Symbolic representation of machine instructions.
Assembly language
Page 11 of the textbook: “assembly language A symbolic representation of machine instructions.”
1.1.20 Interface between user’s program and hardware providing a variety of services and supervision functions.
Operating system
Chapter 1, page 10 of the textbook: “An operating system interfaces between a user’s program and the hardware and provides a variety of services and supervisory functions.”
1.1.21 Software/programs developed by the users.
Application software
Application software is the topmost layer of a computer, above the systems software, which is the layer above the hardware.
1.1.22 Binary digit (value 0 or 1).
Bit
Page 11 of the textbook: “binary digit Also called a bit. One of the two numbers in base 2 (0 or 1) that are the components of information.
1.1.23 Software layer between the application software and the hardware that includes the operating system and the compilers.
Systems software
Chapter 1, page 10 of the textbook: “…with applications being the outermost ring and a variety of systems software sitting between hardware and the applications software.”
1.1.24 High-level language used to write application and system software.
C
Well, C is a high-level programming language that is certainly capable of being used to write application and system software.
1.1.25 Portable language composed of words and algebraic expressions that must be translated into assembly language before run in a computer.
High-level programming language
Page 12 of the textbook: “high-level programming language A portable language such as C, C++, Java, or Visual Basic that is composed of words and algebraic notation that can be translated by a compiler into assembly language.”
1.1.26 10^12 or 2^40 bytes.
Terabyte
10^12 bytes = 1 terabyte (TB), 2^40 bytes = 1.1 TB. Source: wolframalpha.com
Programming Languages Homework 8
Ed Smart
CSC 340
Homework 8
7.1 For the languages C and Java, give as precise binding times as you can for the following attributes. Explain your answers.
(a) The maximum number of significant digits in a real number
This is depends on the real number itself, so it occurs during execution., making it dynamically bound.
(b) The meaning of char
This occurs during language definition, making it statically bound.
(c) The size of an array variable
It is possible to declare an array variable at either compile time or runtime. Due to this, it can either be statically or dynamically bound.
(d) The size of an array parameter
The size of an array parameter is statically bound, since it is declared during compile time.
(e) The location of a local variable
Local variables are statically bound, as they cannot be changed during runtime.
(f) The value of a constant
The value of a constant is bound during loading time, making the binding static.
(g) The location of a function
The location of a function may either be bound at compile time or runtime, so it can be either statically or dynamically bound.
7.7 As noted in this chapter, C and C++ make a distinction between a declaration and a definition. Which of the following are declarations only and which are definitions?
To declare something means to give the compiler only the minimum of its information, mainly just a name and type. Defining, on the other hand, provides the compiler with all of the information for creating whatever it is that is being defined.
(a) char * name;
This is a definition.
(b) typedef int * IntPtr;
This is a definition.
(c) struct rec;
This is a declaration.
(d) int gcd(int,int);
This is a declaration.
(e) double y;
This is a definition.
(f) extern int z;
This is a declaration.
7.14 The following program prints two integer values; the first value typically is garbage (or possibly 0, if you are executing inside a debugger or other controlled environment), but the second value might be 2. Explain why.
#include <stdio.h>
void p(void){
int y;
printf(“%d\n”, y);
y = 2;
}
main(){
p(); p();
return 0;
}
The first value would be garbage because the variable y is being printed before it has been given a value. The second value might be 2 because y is given a value of 2 in the line following the printf, so it may print 2 during the second call, if y retains its value.
7.16 Explain the difference between aliasing and side effects.
Aliasing can be thought of as the binding of two different names to the same object. For example, the following code results in x and y becoming aliases.
int *x, *y;
x = (int *) malloc(sizeof(int));
*x = 1;
y = x; /* *x and *y now aliases */
A side effect, however, is any change in the value of a variable that persists beyond the execution of the statement. Side effects may become harmful if they cannot be determined from the written code.
Networking Wireshark 4
Ed Smart
CSC 251
Wireshark Lab 4: Exploring TCP
1. What is the IP address and TCP port number used by the client computer (source) that is transferring the file to gaia.cs.umass.edu? To answer this question, it’s probably easiest to select an HTTP message and explore the details of the TCP packet used to carry this HTTP message, using the “details of the selected packet header window.”
The IP address used by the client computer transferring the file is 192.168.1.102, and the TCP port number used is 1161.
2. What is the IP address of gaia.cs.umass.edu? On what port number is it sending and receiving TCP segments for this connection?
The IP address of gaia.cs.umass.edu is 128.119.245.12. It is sending and receiving TCP segments for this connection on port 80.
If you have been able to create your own trace, answer the following question:
3. What is the IP address and TCP port number used by your client computer (source) to transfer the file to gaia.cs.umass.edu?
The IP address used by my client computer to transfer the file is 10.33.152.47, and the TCP port number used is 54233.
4. What is the sequence number of the TCP SYN segment that is used to initiate the TCP connection between the client computer and gaia.cs.umass.edu? What is it in the segment that identifies the segment as a SYN segment?
The sequence number of the TCP SYN segment that is used to initiate the TCP connection is 0. The feature that identifies the segment as a SYN segment is the Flag.
5. What is the sequence number of the SYNACK segment sent by gaia.cs.umass.edu to the client computer in reply to the SYN? What is the value of the Acknowledgement field in the SYNACK segment? How did gaia.cs.umass.edu determine that value? What is it in the segment that identifies the segment as a SYNACK segment?
The sequence number of the SYNACK segment is 0. The value of the Acknowledgement field in the SYNACK segment is 1. Gaia.cs.umass.edu determined that value by considering the relative sequence and ACK numbers. The feature in the segment that identifies the segment as a SYNACK segment are the Flags.
6. What is the sequence number of the TCP segment containing the HTTP POST command? Note that in order to find the POST command, you’ll need to dig into the packet content field at the bottom of the Wireshark window, looking for a segment with a “POST” within its DATA field.
The sequence number of the TCP segment containing the HTTP POST command is 152494.
7. Consider the TCP segment containing the HTTP POST as the first segment in the TCP connection. What are the sequence numbers of the first six segments in the TCP connection (including the segment containing the HTTP POST)? At what time was each segment sent? When was the ACK for each segment received? Given the difference between when each TCP segment was sent, and when its acknowledgement was received, what is the RTT value for each of the six segments?
The sequence numbers of the first six segments in the TCP connection are:
1. 152494
2. 1
3. 152977
4. 0
5. 1
6. 0
The time (in seconds) at which each segment was sent was:
1. 5.184
2. 5.503
3. 5.708
4. 6.122
5. 6.128
6. 6.164
The ACK for each segment was received at time (in seconds):
1. 5.186
2. 5.703
3. 5.723
4. 6.125
5. 6.168
6. 6.1681
The RTT (in seconds) for each segment is:
1. 0.039
2. 0.2
3. 0.233
4. 0.00007
5. 0.0007
6. 0.0009
8. What is the length of each of the first six TCP segments?
The length of each of the first six TCP segments is:
1. 537
2. 739
3. 384
4. 532
5. 701
6. 602
Networking Project 4: Web Proxy Server Program
Socket Programming Assignment 4: HTTP Web Proxy Server
In this lab, you will learn how web proxy servers work and one of their basic functionalities – caching.
Your task is to develop a small web proxy server which is able to cache web pages. It is a very simple proxy server which only understands simple GET-requests, but is able to handle all kinds of objectsnot just HTML pages, but also images.
Generally, when the client makes a request, the request is sent to the web server. The web server then processes the request and sends back a response message to the requesting client. In order to improve the performance we create a proxy server between the client and the web server. Now, both the request message sent by the client and the response message delivered by the web server pass through the proxy server. In other words, the client requests the objects via the proxy server. The proxy server will forward the client’s request to the web server. The web server will then generate a response message and deliver it to the proxy server, which in turn sends it to the client.
Below is the code for the web proxy server.
smartedblog 