WSN 1

Introduction: -

• At algorithm- step by step procedure
• Precondition- input EC., List of n values ​​Produces Possible repetition
• Post condition- output
•  Abstract Data Type description of algorithm. Abstract objects: such as integers, real numbers, sets, stacks, graphs and trees.
• Abstract Surgical sort the list, pop the stack and trace the path.
• Abstract relationships- Greater Than, prefix, subset connected and child.
• Correctness- for every legal input instance the required output is produced.
• Running time- reasonable amount of time and memory space, the time of an algorithm is running a function from the size n of the input instance Given to a bound on the number of operations the computation must do. 

Algorithm- feasible (if the function is polynomial like Time (n) = ɵ (n ^{2); - infeasible - exponentially Time (n) = ɵ (2} n)

• Able to compute the running time.
• One needs to be able to add up the times taken in each iteration of a loop.

Meta Algorithm: -

• Most algorithms are Described iterative.

* One Step At A Time
* Each step makes progress while Maintaining the loop invariant 
* Recursive Algorithm 

• recursive algorithm

* Breaks ITS instance into smaller Instance

* For Which it gets a friend to solve

* Combines Their solution into one of its Solution

Optimization problems: -

• important class of computational problems
• key algorithm.

Greedy Algorithm: -

• keep grabbing the next object that looks best.

Recursive Backtracking: -

• try things and if They Do not work backtrack and try something else.

Dynamic programming: -

• solves a sequence of larger instances reusing the Previously saved solutions. Hanes smaller instances until a solution is Obtained Hanes Given Instance

Reductions: -

• one problem to solve another.

Randomized Algorithm: -

• flip coins to help them decide what action to take.

Lower bounds: -

• prove thatthere are no faster algorithms.

Iterative algorithms and loop invariants: -

• with each iteration you have a method That takes you a single step closer.
• to Ensure That You Move Forward You Need to have a closer measure of progress.- telling how far you are from your Either starting or destination.
• as you proceed you must know how to get on to the road from any StartLocation.
• from everyplace along the road You Must Know what actions you will take in order to step forward while not leaving the road
• When finally Sufficient progress has been made along the road, you must know how to exit and reach your destination in a reasonable amount of time.

Paradigm shift: -

* A sequence of actions versus sequence of assertions

Max (a, b, c)

Precondition: Input has 3 numbers

m = a

assert: m is in max {a}

if (b> m)

m = b

End If

assert: m is in max {a, b}

if (c> m)

m = c

End If

assert: m is in max {a, b, c}

return (m)

postcond: return max in {a, b, c}

end Algorithm

* The Challenge of the Sequence of Actions view: -

• needs to keep track of how the state of the computer changes with each new action

 * The advantages of the sequence of the snapshots view.

• this new paradigm is useful one from which one can think about or explain to develop algorithm

* Pre and post-condition: -

• before one can consider in algorithm one needs to define the computational problem being solved by IT Carefully
• by pre and post conditions by providing the initial picture or assertion about the Input Instance and a CORRESPONDING picture or assertion about required output.

* Start in the middle: -

• instead of starting with the first line of code Jump into the middle of the computation and to draw a static picture

* Sequence of snapshots: -

• once one builds up a sequence of assertions in this way one can see the Entire Path of the computation laid out before one

* Fill in the assertions: -

• Assertions are just static snapshots of the computation with time stopped. no action havebeen Considered yet.
• Final step is to fill in actions between consecutive assertions

* One step at a time: -

• Each search block of actions can be Executed Completely independent of the others

The steps to develop on iterative algorithm: -

• Iterative Algorithms
• Loop Invariant
• The code structure
• Proof of correctness
• Running time
• The most important steps are

* Define the problem

* Define step

* Make Progress

* Define loop invariant

* Define exit condition

* Initial conditions

* Define Measure of Progress

* Maintain loop invariant 

• Specifications: - what problem are you solving
• Basic steps: - basic steps will head you in correct direction
• Measure of progress: - define measure of progress; Where are the mile markers along the road.
• Loop Invariant: - define loop invariant; give the picture of the state of the computation; define the road did you want to stay on
• Main steps: - for every location on the road write the pseudo code "code loop"; do not need to start with the first location
• Make Progress: - Each iteration of the main step must make progress According to your measure of progress.
• Maintain Loop Invariant: - Each iteration must Ensure That the loop invariant is true
• Establishing the loop invariant: - Now you have the idea of ​​Where You Are going and you have a better idea of ​​how to begin; write pseudo code "code preloop" to establish loop invariant INITIALLY
• Exit condition: - write {exit cond} causes the computation to break
• Ending: - write "code postloop" to clean up loose ends and to return the required output.
• Termination and running time: - how much progress do you need to make before you know you want to reach this exit; estimate the running time.
• Special cases: - consider one general type of input instance.
• Coding and Implementation Details: - put all the pieces together and produce the pseudo code for the algorithm; Provide additional implementation details.
• Formal proof: - When above pieces fit together then your algorithm works well.