Flashcards
How do we know that an algorithm solves a particular problem?
Cards in this deck (13)
- 1Give two different ways in which a software bug can arise and give two different effects of a software bug.A programmer's error; a poorly written compiler/interpreter
Software bugs can cause programs to produce incorrect results or to crash entirely. - 2Give the different aspects of the software engineering software design process known as the Waterfall Model and very briefly explain what they are.The requirements phase: The specification of what the program is intended to do is produced
The design phase: A plan is composed for the intended solution (involves algorithms and their implementations, architectural aspects, data structures, etc)
Implementation: the design is implemented as code
Verification: Code is tested and debugged
Maintenance: Involves continual updating and modification of code (eg to improve performance, correct faults) - 3When it comes to establishing program correctness, briefly compare and contrast the different approaches taken in software testing and in formal methods.Formal methods involve using mathematically based techniques for the formal specification and verification of software and hardware systems (ie mathematically proving that a program meets its specification).
Software testing involves evaluating an attribute or capability of a program or system and determining that it meets required results by inputting a range of values into the program and verifying that the results are correct. While formal methods are more robust, software testing is preferred by the industry for cost-effectiveness. - 4What is a software metric and what is one used for?Software metrics are quantitative measurements of the complexity of a piece of software, being used in the process of software development, testing, debugging, and cost estimation
- 5What is the difference between an algorithm being totally correct and being partially correct?A totally correct algorithm is one that is correct with respect to some specification and terminates on every input. A partially correct algorithm is one that is only correct with respect to the specification (ie there are no guarantees on termination).
- 6What is the lexicographical order on pairs of natural numbers? How would you undertake an induction with a property indexed by pairs of natural numbers?Consider a set of pairs (a,b) st a>=b>=0.
The pair (a,b)=(b,d) iff a=c and b=d. (a,b) >(b,d) iff either a>c or a=c and b>d in lexicographic ordering. So some pairs could be ordered as (0,0)<(1,0)<(1,1)<(2,0)<(2,1)...
Base case: Show that P(0,0) holds (or in general, P(a0,b0)
Inductive step: assume that P(a,b) is true for some (a,b)>=(a0,b0). We prove that if this is the case then P(a+,b+) must be true, where (a+,b+) is the next pair in the ordering after (a,b)
Principle of induction allows us to state that P(a,b) holds for all (a,b)>=(a0,b0). - 7Outline how the mathematical principle of induction and the algorithmic construction of recursion are often related in the realm of program correctness.Induction has 3 steps:
Formulate a property P(n)
Decide upon a base case, prove it
The inductive step. (prove for n+1 if true for n)
With recursion we have a base case and a recursive call, so it is often easier to inductively prove a recursive algorithm as it already has a abse case, and the recursive call mirrors the inductive step. - 8—
- 9—Factorials n.
By observation we can see that the While loop will always run for exactly n iterations, so it will always terminate.
As it runs n times, and n is decremented by 1 each time, we can trivially see that x will be given the value (n)(n-1)(n-2)...(2)(1)
As it meets the specification and terminates for all inputs, it is totally correct.
- 10—(0,0)<(1,0)<(1,1)<(2,0)<(2,1)<(2,2)<(3,0)...
Base case: Prove P holds for (0,0)
Inductive step: assume P(ak,bk) is greater than its predecessors
Therefore P(ak+1,bk+1) will be larger than P(ak,bk)
Prove that P(ak+1,bk+1) holds if P(ak,bk) does. P(0,0) holds ,therefore P holds for all P(ak,bk).
- 11Outline how we might use a check-point and an invariant to prove that this algorithm correctly outputs the gcd of m and n.Set a check point prior to the execution of the WHILE test, we can show that the values are decreasing within the lexicographical order and thus it will eventually erminate.
An invariant is a checkpoint in a loop that will always simplify to true, if ti does then the program terminates and gives the correct output.
- 12What are the 3 fundamental aspects of a successful proof of total correctness when using invariants?Initialisation - showing that invariant holds for base case
Maintenance - showing that it will hold at the very least until just prior to the next loop test
Termination - there should be a point at which, by virtue of the invariant holding, the program will terminate. - 13—if (m,n) = (x,y) before *
And (m',n') = (x,y) afer *
Then (m',n') = (y,xmody)
HCF of (x,y) is the same as (y,xmody) as if a = bt + r, for integers t and r, then gcd(a,b) = gcd(b,r).
It helps prove that it terminates as x and y because the lines labelled * decrease (x,y) in the lexicographical order, but (x,y) remains part of the order and so will have the same GCD. Because it is decremented in the LO, it will eventually hit y=0 and so terminate. Because (x',y') is always the GCD (as shown by the invariant), when y hits 0, x will be the GCD.
Information
- Description
- Flashcards on How do we know that an algorithm solves a particular problem?, created by SEZ McKelvey on 05/04/2018.
- Created by
- SEZ McKelvey
- Views
- 1
- Rating