Algorithm

Getting Started with AlgorithmWhat is an Algorithm?

Characteristics of Algorithm1 Topic

Analysis Framework

Performance Analysis3 Topics

Mathematical Analysis2 Topics

Sorting AlgorithmSorting Algorithm10 Topics

Searching Algorithm6 Topics

Fundamental of Data StructuresStacks

Queues

Graphs

Trees

Sets

Dictionaries

Divide and ConquerGeneral Method

Binary Search

Recurrence Equation for Divide and Conquer

Finding the Maximum and Minimum

Merge Sort

Quick Sort

Stassen’s Matrix Multiplication

Advantages and Disadvantages of Divide and Conquer

Decrease and ConquerInsertion Sort

Topological Sort

Greedy MethodGeneral Method

Coin Change Problem

Knapsack Problem

Job Sequencing with Deadlines

Minimum Cost Spanning Trees2 Topics

Single Source Shortest Paths1 Topic

Optimal Tree Problem1 Topic

Transform and Conquer Approach1 Topic

Dynamic ProgrammingGeneral Method with Examples

Multistage Graphs

Transitive Closure1 Topic

All Pairs Shortest Paths6 Topics

BacktrackingGeneral Method

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
Specifications of Algorithm
A. Pseudo code Convention
We can describe an algorithm in many ways. We can use a natural language like English, although if we select this option,we must make sure that the resulting instructions are definite. Graphic representations called flowcharts are another possibility, but they work well only if the algorithm is small and simple.In this text we present most of our algorithms using a pseudo code that resembles C and Pascal.
1.Comments begin with // and continue until the end of line.
2.Blocks are indicated with matching braces: { and }. A compound statement (i.e.,a collection of simple statements)can be represented as a block.The body of a procedure also forms a block.Statements are delimited by ;.
3.An identifier begins with a letter.The data types of variables are not explicitly declared.The types will be clear from the context. Whether a variable is global or local to a procedure will also be evident from the context.We assume simple datatypes such as integer,float,char,boolean,and soon. Compound data types can be formed with records. Here is an example:
In this example,link is a pointer to the record type node.Individual data items of a record can be accessed with —–> and period. For instance if p points to a record of type node,p —–> data_1 stands for the value of the first field in the record.On the other hand,if q is a record of type node, q.data_1 will denote its first field.
4. Assignment of values to variables is done using the assignment statement
<variable>:=<expression>;
5.There are two boolean values true and false. In order to produce these values,the logical operators and,or,and not and the relational operators <,<=,=,/,>=,and > are provided.
6.Elements of multidimensional arrays are accessed using [ and ]. For example,if A is a two dimensional array, the (i,j)th element of the array is denoted as A[i,j]. Array indices start at zero.
7.The following looping statements are employed: for,while,and repeat until.The while loop takes the following form
As long as (condition) is true,the statements get executed.When (condition) becomes false,the loop is exited. The value of (condition) is evaluated at the top of the loop. The general form of a for loop is:
Here valuel, value2, and step are arithmetic expressions.A variable of type integer or real or a numerical constant is a simple form of an arithmetic expression. The clause “step step” is optional and taken as +1 if it does not occur,step could either be positive or negative. variable is tested for termination at the start of each iteration. The for loop can be implemented as a while loop as follows:
A repeatuntil statement is constructed as follows:
The statements are executed as long as <condition> is false. The value of <condition> is computed after executing the statements.
The instruction break; can be used within any of the above looping instructions to force exit. In case of nested loops, break; results in the exit of the inner most loop that it is a part of. A return statement within any of the above also will result in exiting the loops.A return statement results in the exit of the function itself.
8.A conditional statement has the following forms:
if <condition> then <statement>
if <condition> then <statement 1> else <statement 2>
Here(condition)is a boolean expression and (statement), (statement 1) and (statement 2) are arbitrary statements(simple or compound).
We also employ the following case statement:
Here(statement 1),(statement 2), etc. could be either simple statements or compound statements. A case statement is interpreted as follows. If (condition 1) is true, (statement 1) gets executed and the case statement is exited. If (statement 1) is false, (condition 2) is evaluated. If (condition 2) is true,(statement 2) gets executed and the case statement exited,and soon.If none of the conditions (condition 1),…, (condition n) are true,(statement n+1)is executed and the case statement is exited. The else clause is optional.
9.Input and output are done using the instructions read and write. No format is used to specify the sizeof input or output quantities.
10.There is only one type of procedure: Algorithm. An algorithm consists of a heading and a body. The heading takes the form
Algorithm Name(<parameter list>)
where Name is the name of the procedure and (<parameter list>) is a listing of the procedure parameters. The body has one or more (simple or compound) statements enclosed within braces { and }. An algorithm may or may not return any values. Simple variables to procedures are passed by value. Arrays and records are passed by reference. An array name or a record name is treated as a pointer to the respective datatype.
As an example,the following algorithm finds and returns the maximum
of n given numbers.
In this algorithm (named Max), A and n are procedure parameters. Result and i are local variables.
B. Recursive Algorithms
A recursive function is a function that is defined in terms of itself. Similarly, an algorithm is said to be recursive if the same algorithm is invoked in the body.
When is recursion an appropriate mechanism for algorithm exposition?One instance is when the problem it self is recursively defined. Factorial fits this category, as well as binomial coefficients, where