Week 4 – Analysis

Week 4 – Analysis
Mark W. Boady
April 26, 2020
1 How much work does my algorithm do?
It is important to figure out how much work out algorithms do. At the assembly
level, we can give exact answers to these questions. We can say “my code does
11 ADD commands”. In most cases, this is far to specific. It depends on both
the exact method the code was written and the processor it is being run on.
We will start by analyzing a function in assembly. Then we will introduce
theoretical methods of classifying code into general categories based on their
efficiency.
2 Search a List
In Week 2’s reading, we looked at linear search. The idea is we have a list of
numbers and wanted to search them to find a value.
This time, let us assume that the values we are searching are given in sorted
order.
We will start with an algorithm for the search.
We need three things as input. The first is a list of numbers stored in
memory. We call this an Array.
We use square brackets to say be are referencing a value in an array. For
example, let us imagine that haystack is the label of the first number in a long
list of numbers. In psuedocode, we could say haystack[0] to mean the value
that is zero position away from the start. This is the first element. We would
say haystack[2] to mean the value that is 2 positions away from the first. This
is the third value.
The second input we need is the size of the array. We need to know how
many elements to search.
The third input is the value we are searching for.
We will have this algorithm print the answer.
1
Algorithm 1 Linear Search of Sorted List
function LinearSearch(needle, haystack, size)
Let i=0
while i < size do
if haystack[i]==needle then
print(“Yes”)
return
end if
end while
print(“No”)
return
end function
To start, we need places in memory to store the values. We also put a
jump command to jump over the variables. We are not going to build a true
function here since we only need to do this one algorithm. The entire script is
our function.
1 ; Linear Search a L i st of Numbers
2 JMP s ear ch ; Jump to s t a r t of Program
3 ;—-Create V a ri a b l e s —–
4 n e edl e :
5 DB 8
6 size :
7 DB 10
8 haystack :
9 DB 1
10 DB 2
11 DB 3
12 DB 5
13 DB 7
14 DB 8
15 DB 12
16 DB 31
17 DB 92
18 DB 100
We need to load the start and ending locations. We need to implement
i < size. We can find out the memory locations of the last value. The
haystack+size is the point we should stop.
We use all four registers. Register D is the stopping point. Register C is the
current value. Register B is the needle we are looking for. We will use Register
A to store and compare values.
2
1 ;—–St a rt Program Code —
2 s e ar ch :
3 ; Step 1: Figu re out th e st o p pin g p oint
4 MOV D, [ size ]
5 MOV C, haystack ;C s t o r e s f i r s t element in Array
6 ADD D,C ;D st o r e d F i r st memory l o c a t i o n AFTER Array
7 MOV B, [ n e edl e ] ; Load Target
8 ; Step 2: Loop
The loop needs to store and compare values. First, we check for the needle.
If we have found it we can print that and exit. If not, we move to the next
element.
1 loop :
2 MOV A, [C] ; Get Value
3 CMP A,B ; See i f we found i t
4 JZ exit_found
5 ; Move to th e c o r r e ct a r ray p o s i t i o n
6 INC C ; In c r ea s e C p o s i t i o n
7 CMP C,D ; Are We s t i l l in Array?
8 JNZ loop
9 JZ exit_not_found
If we reach the end of the list and have not found the needle, then it must
not exist. We can print the answer is not found.
We can hardcode the two print statements.
1 exit_not_found :
2 MOV [ 2 3 2 ] , ’N ’
3 MOV [ 2 3 3 ] , ’O’
4 HLT
5 exit_found :
6 MOV [ 2 3 2 ] , ’Y ’
7 MOV [ 2 3 3 ] , ’E ’
8 MOV [ 2 3 4 ] , ’S ’
9 HLT
The full code is shown on the next page.
3
1 JMP s ear ch ; Jump to s t a r t of Program
2 ;—-Create V a ri a b l e s —–
3 n e edl e :
4 DB 8
5 size :
6 DB 10
7 haystack :
8 DB 1
9 DB 2
10 DB 3
11 DB 5
12 DB 7
13 DB 8
14 DB 12
15 DB 31
16 DB 92
17 DB 100
18 ;—–St a rt Program Code —
19 s e ar ch :
20 ; Step 1: Figu re out th e st o p pin g p oint
21 MOV D, [ size ]
22 MOV C, haystack ;C s t o r e s f i r s t element in Array
23 ADD D,C ;D st o r e d F i r st memory l o c a t i o n AFTER Array
24 MOV B, [ n e edl e ] ; Load Target
25 ; Step 2: Loop
26 loop :
27 MOV A, [C] ; Get Value
28 CMP A,B ; See i f we found i t
29 JZ exit_found
30 ; Move to th e c o r r e ct a r ray p o s i t i o n
31 INC C ; In c r ea s e C p o s i t i o n
32 CMP C,D ; Are We s t i l l in Array?
33 JNZ loop
34 JZ exit_not_found
35 exit_not_found :
36 MOV [ 2 3 2 ] , ’N ’
37 MOV [ 2 3 3 ] , ’O’
38 HLT
39 exit_found :
40 MOV [ 2 3 2 ] , ’Y ’
41 MOV [ 2 3 3 ] , ’E ’
42 MOV [ 2 3 4 ] , ’S ’
43 HLT
4
3 Count Operations
The most straightforward, but time consuming method to determine efficiency
is to count operations.
Our code always starts with a JMP command.
The following code always runs exactly once at the start of the file.
1 ;—–St a rt Program Code —
2 s e ar ch :
3 ; Step 1: Figu re out th e st o p pin g p oint
4 MOV D, [ size ]
5 MOV C, haystack ;C s t o r e s f i r s t element in Array
6 ADD D,C ;D st o r e d F i r st memory l o c a t i o n AFTER Array
7 MOV B, [ n e edl e ] ; Load Target
8 ; Step 2: Loop
That means every single time this code is executed we will always start with
a fixed number of Initialization Operations.

Table 1: Initialization Operations
When the code ends, we will do one of the two print paths.
1 exit_not_found :
2 MOV [ 2 3 2 ] , ’N ’
3 MOV [ 2 3 3 ] , ’O’
4 HLT
5 exit_found :
6 MOV [ 2 3 2 ] , ’Y ’
7 MOV [ 2 3 3 ] , ’E ’
8 MOV [ 2 3 4 ] , ’S ’
9 HLT
Both paths have a HTL operation. They each do different amounts of MOV
operations.

Table 2: Display Operations
5
The loop is the most difficult part. It depends.
1 loop :
2 MOV A, [C] ; Get Value
3 CMP A,B ; See i f we found i t
4 JZ exit_found
5 ; Move to th e c o r r e ct a r ray p o s i t i o n
6 INC C ; In c r ea s e C p o s i t i o n
7 CMP C,D ; Are We s t i l l in Array?
8 JNZ loop
9 JZ exit_not_found
There are three possible paths through this code.
We might find the value we want. In this case, the JZ exit_found will run.
The rest of the code will be skipped. We might not find it, but need to keep
looking. Then we run to the JNZ loop code. Lastly, we might be on the last
number and make it all the way to JZ exit_not_found.

Table 3: Loop Operations
We can make a table and see what happens for specific search values. This
is shown in Table 6.
We can also look at the best case and worst case. In the Best Case, we
find the value on our first try. In the worst case, we need to look at every
value.
The base case, is the Initialization Operations, the Display Found
Operations, and one count of Found Value operations. This is shown in
Table 4.
The worst case depends on the number of elements in the list. We will execute the Initialization Operations and the Display Not Found operations
once. For every element in the list except the last one, we will run the Keep
Looking operations. One time, for the last element, we will run the extra
operation for End of Array. The worst case values are shown in Table 5.
We can total these up into a grand total. The best case will always take
exactly 12 operations. The worst case, will take 6 ∗ size + 9 operations. Since
our list has 10 elements, the worst case is 69 operations.
More generally, we can say for any list with size elements the number of
operations falls in the range 12 ≤ ops ≤ 6 ∗ size + 9.
6

Table 4: Best Case Operations

Table 5: Worst Case Operations

Table 6: Counts for Specific Cases
7

The post Week 4 – Analysis appeared first on My Assignment Online.

Expert Help With This Assignment — On Your Terms