Iamstuckatm
New member
- Joined
- Jan 31, 2014
- Messages
- 1
I'm really bad at maths, I'm in my first year of uni and they've given everyone the same modules for the first year...does anyone understand algorithms or ANY of these questions because I'm truly baffled.
Given username was absc941
Question 1.
Consider the following algorithm (note that a letter’s position in the alphabet starts from ‘a’ at position 1 and goes to ‘z’ at position 26).
Input is a list, with elements numbered from 1. Put d = 1947
1. For i=1 to 7
If the ith element of the list is a letter then
If the letter’s position in the alphabet is an odd number then
d = d + 11
else
2. Return d.
If the ith element is numeral n then
d = d + n.
Now consider the list of characters in your login. Apply the algorithm above to this list, writing down the value of all variables involved in the algorithm each time one of these values changes.
Question 2
Consider the list of all number from 0 to 99:
[0, 1, 2, 3, …, 97, 98, 99]
Consider the number given by the last two digits of your login. [Suppose your login was abcd123, then your number would be 23. If your login was abcd409, then your number would be 9.] Apply binary search (as defined in the lectures) to search for this number within the above list. Show all your working from the search, in particular, keep track of the value of u, l and i. Note that your list indices are number from 1, even though the values start from 0, that is, L1 = 0 and L23 = 22.
Question 3.
Consider the following algorithm that applies to non-empty lists of letters: For list [L1,….,Ln].
1. Put m=27, i=1.
2. While i < n
o For j = i+1 to n
If distance(Li,Lj) < m then m = distance(Li,Lj)
o i = i+1
3. Return m.
In the algorithm, the function distance(α,β) is given by the absolute difference between the position in the alphabet of α and β. For example, distance(e, v) = 17 and distance(f, c) = 3.
a) Apply this algorithm with input list consisting of the four letters in your login reversed. That is, for login abcd123, the input is [d,c,b,a]. Your answer should consist of a table of values for i, j and m after each call to the “If…” line.
b) For input of size 5, how many steps will this algorithm take? How many for the general case where the input is of size n? What complexity class is it in?
Given username was absc941
Question 1.
Consider the following algorithm (note that a letter’s position in the alphabet starts from ‘a’ at position 1 and goes to ‘z’ at position 26).
Input is a list, with elements numbered from 1. Put d = 1947
1. For i=1 to 7
If the ith element of the list is a letter then
If the letter’s position in the alphabet is an odd number then
d = d + 11
else
2. Return d.
If the ith element is numeral n then
d = d + n.
Now consider the list of characters in your login. Apply the algorithm above to this list, writing down the value of all variables involved in the algorithm each time one of these values changes.
Question 2
Consider the list of all number from 0 to 99:
[0, 1, 2, 3, …, 97, 98, 99]
Consider the number given by the last two digits of your login. [Suppose your login was abcd123, then your number would be 23. If your login was abcd409, then your number would be 9.] Apply binary search (as defined in the lectures) to search for this number within the above list. Show all your working from the search, in particular, keep track of the value of u, l and i. Note that your list indices are number from 1, even though the values start from 0, that is, L1 = 0 and L23 = 22.
Question 3.
Consider the following algorithm that applies to non-empty lists of letters: For list [L1,….,Ln].
1. Put m=27, i=1.
2. While i < n
o For j = i+1 to n
If distance(Li,Lj) < m then m = distance(Li,Lj)
o i = i+1
3. Return m.
In the algorithm, the function distance(α,β) is given by the absolute difference between the position in the alphabet of α and β. For example, distance(e, v) = 17 and distance(f, c) = 3.
a) Apply this algorithm with input list consisting of the four letters in your login reversed. That is, for login abcd123, the input is [d,c,b,a]. Your answer should consist of a table of values for i, j and m after each call to the “If…” line.
b) For input of size 5, how many steps will this algorithm take? How many for the general case where the input is of size n? What complexity class is it in?