Algorithms (any help?)
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?
(edited 10 years ago)
No one is going to do your homework for you, so you need to say what you're stuck with. Here are some pointers for the first two.
1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).
2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.
1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).
2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.
Original post by Push_More_Button
No one is going to do your homework for you, so you need to say what you're stuck with. Here are some pointers for the first two.
1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).
2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.
1) Go through your username (absc941) and if it's a letter in an odd position of the alphabet add 11 onto the number you have (d).
2) Your number is 41. You already have your sorted list (0-99) so all you need to do is perform a simple binary search. This means you're looking for the number 41. A binary search means you select the value in the middle of your list (the 50th value) which is 49 and you compare it with what you're after (41). As your target is lower than your selected value you know you're not interested in the values above the selected number, so you can throw them away. We then select the 25th value in the list (24) and compare it with your target. This value is too low, so we throw away the numbers that are lower and split the list in half again and compare, throwing away the values we know it can't be. We keep doing this until you get lucky and hit the value you're searching for or until you throw away every value but the one you're searching for.
Hi..thanks for replying I just don't understand how to work any of it out I just need explanation especially on the first one I don't really understand the basics and textbooks are just too complicated imo
Posted from TSR Mobile
Ok, so a more in depth explanation of the first one...
Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.
The username is 7 characters long: absc941
We're given a number (called d) and we're told it's 1947
Our algorithm is:
For i=1 to 7
So this means we're going to do something 7 times (and our username is 7 characters long...)
If the ith element of the list is a letter then
This means as we're iterating through our loop we should check the corresponding letter. So for the first run through of the algorithm we look at the first character, the second run through the second character, until we've gone 7 iterations and we're looking at the last character in the username.
The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.
If the letter’s position in the alphabet is an odd number then
So we need to take the number that is assigned to the letter and check whether it is odd. As As number is 1 it is odd so we must continue with the next instruction.
d = d + 11
This means d has 11 added onto it.
We've now done our first iteration through the loop, so now i becomes 2 and we look at the second character. You need to check if it's a letter. If it is then you need to check if the number assigned to it is odd and if it is add 11 onto d. You then move onto the next character and do the same until you've done it to all the characters in your username. If the number assigned to the letter is even then you should just return the current value of d.
You do a similar thing if the character is a number in that you add n to d. n is the number you're currently checking.
Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.
The username is 7 characters long: absc941
We're given a number (called d) and we're told it's 1947
Our algorithm is:
For i=1 to 7
So this means we're going to do something 7 times (and our username is 7 characters long...)
If the ith element of the list is a letter then
This means as we're iterating through our loop we should check the corresponding letter. So for the first run through of the algorithm we look at the first character, the second run through the second character, until we've gone 7 iterations and we're looking at the last character in the username.
The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.
If the letter’s position in the alphabet is an odd number then
So we need to take the number that is assigned to the letter and check whether it is odd. As As number is 1 it is odd so we must continue with the next instruction.
d = d + 11
This means d has 11 added onto it.
We've now done our first iteration through the loop, so now i becomes 2 and we look at the second character. You need to check if it's a letter. If it is then you need to check if the number assigned to it is odd and if it is add 11 onto d. You then move onto the next character and do the same until you've done it to all the characters in your username. If the number assigned to the letter is even then you should just return the current value of d.
You do a similar thing if the character is a number in that you add n to d. n is the number you're currently checking.
(edited 10 years ago)
Original post by Push_More_Button
Ok, so a more in depth explanation of the first one...
Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.
The username is 7 characters long: absc941
We're given a number (called d) and we're told it's 1947
Our algorithm is:
For i=1 to 7
So this means we're going to do something 7 times (and our username is 7 characters long...)
If the ith element of the list is a letter then
This means as we're iterating through our loop we should check the corresponding letter. So for the first run through of the algorithm we look at the first character, the second run through the second character, until we've gone 7 iterations and we're looking at the last character in the username.
The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.
If the letter’s position in the alphabet is an odd number then
So we need to take the number that is assigned to the letter and check whether it is odd. As As number is 1 it is odd so we must continue with the next instruction.
d = d + 11
This means d has 11 added onto it.
We've now done our first iteration through the loop, so now i becomes 2 and we look at the second character. You need to check if it's a letter. If it is then you need to check if the number assigned to it is odd and if it is add 11 onto d. You then move onto the next character and do the same until you've done it to all the characters in your username. If the number assigned to the letter is even then you should just return the current value of d.
You do a similar thing if the character is a number in that you add n to d. Though your question doesn't say what n is so it's possibly an error and it means i or it's in another part of your question...
Each letter of the alphabet is assigned a number based on it's position. As A is the first number it is 1, B is the second so it's 2, C is 3, D is 4 and so on all the way to Z which is 26.
The username is 7 characters long: absc941
We're given a number (called d) and we're told it's 1947
Our algorithm is:
For i=1 to 7
So this means we're going to do something 7 times (and our username is 7 characters long...)
If the ith element of the list is a letter then
This means as we're iterating through our loop we should check the corresponding letter. So for the first run through of the algorithm we look at the first character, the second run through the second character, until we've gone 7 iterations and we're looking at the last character in the username.
The algorithm is an if statement checking whether the character we're looking at is a letter. It is so we continue with the next instruction.
If the letter’s position in the alphabet is an odd number then
So we need to take the number that is assigned to the letter and check whether it is odd. As As number is 1 it is odd so we must continue with the next instruction.
d = d + 11
This means d has 11 added onto it.
We've now done our first iteration through the loop, so now i becomes 2 and we look at the second character. You need to check if it's a letter. If it is then you need to check if the number assigned to it is odd and if it is add 11 onto d. You then move onto the next character and do the same until you've done it to all the characters in your username. If the number assigned to the letter is even then you should just return the current value of d.
You do a similar thing if the character is a number in that you add n to d. Though your question doesn't say what n is so it's possibly an error and it means i or it's in another part of your question...
To add to your last point, it could be n refers to the value of the character if it's a number
EDIT: OP actually says "numeral n"
Ahh well spotted, missed that.
Have edited it in, thanks.
Have edited it in, thanks.
Original post by Push_More_Button
n is the number you're currently checking.
Do you mean I would add 9 on once I get to the 5th character or add 5 itself?
But thank you so much for your help, I will go over this asap and hopefully understand it better than before, also are there any pointers on question three because that seems even worse than the first two? If not thank you once again for the detailed explanations you've written, really helped me out there
(edited 10 years ago)
You would add 9.
Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.
Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.
Original post by Push_More_Button
You would add 9.
Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.
Have a try at question 3 and if you need help explain which part you're stuck on. It's a similar problem, you need to go through each character and do something with it.
Thanks
I'll have a shot, also in question two, what does it mean keep track of value U, L and I? I understand the rest of the question but I'm slightly confused as to what those three letters meanI'm guessing your lecture notes or beginning of the worksheet will say what L U and I is but I don't know. I'd guess that L is the list index you're currently using.
You'll need to write down what you're doing step-by-step, most likely.
You'll need to write down what you're doing step-by-step, most likely.
Original post by Push_More_Button
I'm guessing your lecture notes or beginning of the worksheet will say what L U and I is but I don't know. I'd guess that L is the list index you're currently using.
You'll need to write down what you're doing step-by-step, most likely.
You'll need to write down what you're doing step-by-step, most likely.
I managed to finally get some more time to look at the questions I still don't understand question three to be honest, also I did get some more information about the binary search:
– a list of n elements being searched [L1,….,Ln]
– the quarry, K
– a variable i. This variable holds the current position (index) in the list being searched
– variable found a boolean variable for whether or not the quarry has been found.
– the algorithm terminates immediately when it finds K (or when there are no items left)
Not too sure what the "quarry" part means?
The quarry is the thing you are looking for.
Quick Reply
Related discussions
- Epq computer science HELP
- CS AQA NEA - my own hashing algorithm?
- Seeking Advice on Pursuing MSc in Artificial Intelligence at BCU or MMU
- Computer Science Question
- Computer Science Paper 2 (OCR A Level)
- A-level computer science NEA - need help with design section
- cs alevel question quick sort
- OCR A-level Computer Science Paper 2 (H446/02) - 19th June 2023 [Exam Chat]
- Speedcubing advice
- OCR Computer Science NEA
- Request for 'latest' feed option
- MSc Computer Science (Online) University of York
- Ocr alevel spec comp sci
- What topic are you on at school in Further maths yr 12?
- GCSE Computer Science QUESTION
- Computer science nea A level project
- Where to look for in-person tutors?
- Above and beyond for AI
- Do you use logarithms, matrices and exponentials in algorithms?
- Gce ocr computer science 2024
Latest
Last reply 1 hour ago
Official University College London Applicant Thread for 2024Last reply 1 hour ago
Can I do economics degree without a level maths?Last reply 1 hour ago
How to choose unis in UCAS application for CS undergraduate course?Last reply 1 hour ago
Rishi Sunak pledges to remove benefits for people not taking jobs after 12 monthsLast reply 2 hours ago
Got my crush's number 2 days ago and no reply yet. What could be the reasons?Posted 2 hours ago
GB News set to axe 40 jobs after channel posts heavy lossesPosted 2 hours ago
Sunak rejects offer of youth mobility scheme between EU and UKTrending
Last reply 1 week ago
OCR A-level Computer Science Paper 2 (H446/02) - 19th June 2023 [Exam Chat]Last reply 2 weeks ago
AQA A-level Computer Science Paper 1 (7517 1A - 1E) - 12th June 2023 [Exam Chat]Last reply 4 weeks ago
OCR A-level Computer Science Paper 1 (H446/01) - 12th June 2023 [Exam Chat]Last reply 2 months ago
OCR GCSE Computer Science Paper 1 (J277/01) - 19th May 2023 [Exam Chat]Last reply 3 months ago
AQA GCSE Computer Science Paper 2 (8525/2) - 25th May 2023 [Exam Chat]Last reply 5 months ago
AQA GCSE Computer Science Paper 1 (8525/1A, 1B, 1C) - 19th May 2023 [Exam Chat]Last reply 5 months ago
AQA Computer Science NEA and Computer science paper 1 questionTrending
Last reply 1 week ago
OCR A-level Computer Science Paper 2 (H446/02) - 19th June 2023 [Exam Chat]Last reply 2 weeks ago
AQA A-level Computer Science Paper 1 (7517 1A - 1E) - 12th June 2023 [Exam Chat]Last reply 4 weeks ago
OCR A-level Computer Science Paper 1 (H446/01) - 12th June 2023 [Exam Chat]Last reply 2 months ago
OCR GCSE Computer Science Paper 1 (J277/01) - 19th May 2023 [Exam Chat]Last reply 3 months ago
AQA GCSE Computer Science Paper 2 (8525/2) - 25th May 2023 [Exam Chat]Last reply 5 months ago
AQA GCSE Computer Science Paper 1 (8525/1A, 1B, 1C) - 19th May 2023 [Exam Chat]Last reply 5 months ago
AQA Computer Science NEA and Computer science paper 1 question
