Flashcards
How might we develop algorithms to solve fundamental problems?
Flashcards do conjunto (21)
- 1Detail, using pseudocode, a recursive version of Euclid's algorithm.Input: two non negative integers m and n with m>=n>=0
Function: Euclid(m,n)
If n==0:
output m
Else:
set m = n and n = m mod n simultaneously
Euclid(m,n) - 2Detail, using pseudocode, an iterative version of Euclid's algorithm
- 3What is the fundamental difference between the research areas of formal methods and software testing when it it comes to verifying that programs are correct?Formal methods involve mathematically proving that a program meets the specification, software testing involves systematically testing various inputs and establishing a program's correctness by studying its executions. Formal methods are preferred (much more robust), but proofs are difficult to achieve.
- 4Describe the key difference between recursion and iteration.Recursion involves the repeated application of a process within the process itself (the process calls itself), whereas iteration is the repeated application of a process, normally in a loop.
- 5Give a natural language description of the algorithm bubble-sort (ascending)Take the first value in the list ([x]) and compare it to the second ([x+1]). If x is greater than the second value, then, switch [x] and [x+1]. Then move on to the next value ([x+1]), comparing this to the third value in the list ([x+2]). Switch these around if the second is greater than the third. Continue through the list in this way. Make multiple passes through the list until a pass is made where no values are switched. The sort is complete.
- 6Give pseudocode for bubble sort.
- 7Can you amend bubble sort so as to improve it? You should explain clearly how you amend the pseudocode and what improvements you have made.In bubble sort, after each pass, the largest number gets pushed to the end, then the next largest, etc. So no need to compare the last digit after the first pass, last two after second, etc. This makes the algorithm much faster as fewer comparisons have to be made.
- 8Give a natural language description of Selection sort (ascending).Start with unordered list. i=0. List[i] = x
Pass 0: compare x with the numbers in the list starting from list[1], keep the smaller number in x and the larger number in the list cell.
Put the resulting x in List[0].
Pass 1-> n-1: Increment i, compare list[i] with all numbers list[i+1:] in the list. - 9Give pseudocode for selection sort (ascending)
- 10—
- 11Explain how you might amend the selection sort algorithm so that the number of data swaps made is lessened.Store the index of the smallest value found so far in x, then after the full pass swap A[pass] with A[x].
- 12Compare and contrast the efficiency of bubble-sort and selection-sort when the input list of numbers is already sorted into descending order. Explaiin how you interperet efficiency.Selection sort: always takes n(n+1)/2 = comparisons.
Bubble sort: will take n(n+1)/2 comparisons also.
So if both are not optimised, wil ltake the same time. - 13Compare and contrast the efficiency of bubble-sort and selection-sort when the list of numbers is already sorted into ascending order.Selection sort: always takes n(n+1)/2 comparisons
Bubble sort: will just take n-1 comparisons, so will take a lot fewer data swaps. - 14Give a natural language description of the merge sort.Chop the input list into two halves. Recursively sort each half, then merge the two sorted lists together.
- 15Give pseudocode for merge sort
- 16Describe an application of coding theory and explain the relecance of this application to coding theory.Coding theory is the study of the properties of codes, with codes used in examples like data compression, error correction, cryptography. Codes are studied for the purpose of designing efficient and reliable data transmission methods, typically involving the removal of redundancy and the addition of error correction/detection data. Data compression is the compression of data for more efficient transmission. There are many data compression algorithms such as zip, jpeg, mpeg etc, used all the time by everyday people.
- 17Describe the binary search algorithmFinds items in sorted lists. Compare the item we are looking for with the median element of the list. If this is the correct item, we return it. Otherwise we perform binary search on the elements up to the median (if the median is too large) or from the median to the end (if it is too small). If all elements are checked and x is not found, x is not in the list.
- 18What is the string matching problem?We are given a text string and a pattern string, and we want to find an occurence of the pattern string in the text if there is one.
- 19—It walks through a string, aligns the pattern string against the first m symbols of text T then we check the selection from right to left. If there is a match, we halt, and output the index within the text where the pattern matches. If not, we move the pattern one cell to the right and check again, etc.
The two heuristics are the Good Suffix heuristic - where the end of the pattern string matches
The bad character - the character before the good suffix that does not match
Based on this, we can increment the pos by more than 1 when we obtain a mismatch, the amount we increment based on good suffix/bad character and the pattern string. This is what the Boyer-More algorithm does.
Unsure what simple change can be made tbh.
- 20Suppose we have a patten string abab in Boyer-Moore algorithm where the laphabet is {a,b,c}. What are the values of the good suffix and bad character heuristics at the different mis-match positions?GS(3) = 1 no good suffix so can only move pattern one cell to right
GS(2) = 2 we can't move pattern 1 cell to the right and get a match.
GS(1) = 2. we can move pattern 2 cells to the right and potentially get a match.
GS(0) = 2.
BC(a,3) = 1, BC (c,3) = 4
BC(b,2) = 4 BC(c,2) = 4
BC(a,1) = 3 BC(c,1) = 3
BC(b,0) = 3 BC(c,0) = 4? 3? - 21Give one area of science where string matching algorithms are of direct relevance.Bioinformatics - genetic sequence analysis, where different genes or relationships between species are compared, which heavily involves strings and algorithms.
Informações
- Descrição
- FlashCards sobre How might we develop algorithms to solve fundamental problems?, criado por SEZ McKelvey em 05-04-2018.
- Criado por
- SEZ McKelvey
- Visualizações
- 1
- Avaliação