ASSIGNMENT OF ANALYSIS AND DESIGN OF ALGORITHMS

ASSIGNMENT OF ANALYSIS AND DESIGN OF

                          ALGORITHMS

Question No.1 Describe the properties of Algorithms.

Properties of algorithms

An algorithm may have zero or more inputs externally and its should produce one or more output. Also an algorithm must terminate after a finite number or steps properties of algorithm include.

An algorithm is defined as a set of well defined instructions used to accomplish a particular task. It is considered as the cornerstone of good programming. The efficiency  of algorithms depends upon speed size and resource consumption.

1.      Correctness:- It should provide correct and accurate output for all legitimate input.

2.      Definiteness:- Each instruction should be clear precise and unambiguous. Input and output must  be well defined.

3.      Finiteness:- When we trace out the instruction of an algorithm, it has to terminate after a finite number of steps for all cases.

4.      Effectiveness:- Every instruction must be very basic so that it can be carried out in principle by a person using only pencil and paper.

5.      Generality:-  Algorithms need to have general instructions  which can be applied in any case.

Question No.2 Define selection sort and explain how to implement the selection sort?

Selection sort  

Selection sort is one of the simples and performance oriented sorting techniques that  work well for small files it has time complexity as O(n2) which is unproductive on large lists.

Sorting is  to place elements in increasing or decreasing order.  Selection sort  is a simple sorting algorithm .
The algorithm divides the input lists into two parts ; the sublist of the items are already sorted ,which is built up from left to right at the front(left) of the list , and the sublist of the  items remaining to be sorted that occupy the rest of the list. Initially the sorted sublist is empty and the unsorted sub list is the entire input list .The algorithm proceeds by finding the smallest (or largest depending on the sorting order ) element in the unsorted sublist  exchanging it with the leftmost unsorted element (putting in sorted order) and moving the sublist  boundaries one element to the right

Implementation of selection sort

The selection sort is a combination of searching and sorting. During each pass,

the unsorted element with the smallest (or largest) value is moved to its proper position in

 the array. The number of times the sort passes through the array is one less than the number of items in the array.

 In the selection sort, the inner loop finds the next smallest (or largest) value and the outer loop places that value

 into its proper location

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops

 depend on the data in the array.

 Selecting the lowest element requires scanning all n elements (this takesn − 1 comparisons) and then swapping

 it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and

 so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) comparisons. Each of these scans requires one

swap for n − 1 elements

Question No.3  Define and explain Topological sort with an example.

Topological Sort

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv,  vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Topological Sorting vs Depth First Traversal (DFS):

In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting,

we need to print a vertex before its adjacent vertices. For example, in the given graph, the vertex ‘5’

should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. So Topological sorting is different from DFS. For example, a DFS of the above graph is “5 2 3 1 0 4″, but it is not a topological sorting

 Algorithm to find Topological Sorting:

We recommend to first see implementation of DFS here. We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack.

 We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

 

For example

topological sorting of the following graph is “5 4 2 3 1 0″. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is “4 5 2 3 1 0″. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no in-coming edges)

Question No.4  Explain good-suffix and bad-character shift in Boyer-Moore algorithm.

 Good suffix shift

Sometimes the bad character heuristics fails. In the following situation the comparison a-b causes a mismatch. An alignment of the rightmost occurence of the pattern symbol a with the text symbol a would produce a negative shift. Instead, a shift by 1 would be possible. However, in this case it is better to derive the maximum possible shift distance from the structure of the pattern. This method is called good suffix heuristics.

Example: 

0              1              2              3              4              5              6              7              8              9              ...

a              b             a              a              b             a              b             a              c              b             a

c              a              b             a              b                                                                                            

                             c             a            b            a     b           

                                               

The suffix ab has matched. The pattern can be shifted until the next occurence of ab in the pattern is aligned to the text symbols ab, i.e. to position 2.

Bad character  shift

This method is called bad character heuristics. It can also be applied if the bad character, i.e. the text symbol that causes a mismatch, occurs somewhere else in the pattern. Then the pattern can be shifted so that it is aligned to this text symbol. The next example illustrates this situation.

Example: 

0              1              2              3              4              5              6              7              8              9              ...

a              b             b             a              b             a              b             a              c              b             a

b             a              b             a              c                                                                                             

                             b                a            b             a                c             

                                               

Comparison b-c causes a mismatch. Text symbol b occurs in the pattern at positions 0 and 2. The pattern can be shifted so that the rightmost b in the pattern is aligned to text symbol b.

Question No.5  Solve the Knapsack problem using memory functions. Item 1 2 3 4 Weight 2 6 4 8 Value (in Rs.) 12 16 30 40 Knapsack capacity is given as W=12. Analyze the Knapsack problem using memory functions with the help of the values given above.

Knapsack Problem

Given some items, pack the knapsack to get the maximum total value. Each item (n) has some weight (wi) and some value (vi). Total weight that we can carry is no more than some fixed number W.
0-1 knapsack problem
Let there be n items,(1,...,n) where ni has a value vi and weight wi. xi is the number of copies of the item ni .The maximum weight that we can carry in the bag is W. It is common to assume that all values and weights are non-negative.
The bounded knapsack problem (BKP)
BKP removes the restriction that there is only one of each item, but restricts the number xi of copies of each kind of item to an integer value ci.

Example: Knapsack capacity W=12

item weight value

1     2     12

2     5     6

3     10    30

4     5     40

Subset Total weight Total value

{1} 2 12

{2} 6 16

{3} 4 30

{4} 8 40

{1,2} 7 30

{1,3} 12 50

{1,4} 7 20

{2,3} 15 12

{2,4} 10 16

{3,4} 15 40

{1,2,3} 17 not feasible

{1,2,4} 12 30

{1,3,4} 17 not feasible

{2,3,4} 20 not feasible

{1,2,3,4} 22 not feasible

Question No.6  Describe Variable Length Encoding and Huffman Encoding. Variable Length Encoding Variable length encoding removes this difficulty by assigning less number of bits to symbols which occur more often and more number of bits to symbols whose frequency of occurrence is less. The Huffman encoding scheme falls in the category of variable length encoding i.e. code for the symbol depends on the frequency of that symbol

We can do it better, provided: – Some characters are more frequent than others. – Characters may be represented different bit lengths, so that for example, in the English alphabet, letter a may use only one or two bits, while letter z may use several. – We have a unique way of decoding the bit stream.

Magic word: ABRACADABRA

  LET A = 0

B = 100

C = 1010

 D = 1011

 R = 11

Thus, ABRACADABRA = 01001101010010110100110

 So 11 letters demand 23 bits < 33 bits, an improvement of about 30%.

Huffman Encoding

This method is named after D.A. Huffman, who developed the procedure in the 1950s.  Figure 27-2 shows a histogram of the byte values from a large ASCII file. More than 96% of this file consists of only 31 characters: the lower case letters, the space, the comma, the period, and the carriage return. This observation can be used to make an appropriate compression scheme for this file. To start, we will assign each of these 31 common characters a five bit binary code: 00000 = "a", 00001 = "b", 00010 = "c", etc. This allows 96% of the file to be reduced in size by 5/8. The last of the five bit codes, 11111, will be a flag indicating that the character being transmitted is not one of the 31 common characters. The next eight bits in the file indicate what the character is, according to the standard ASCII assignment. This results in 4% of the characters in the input file requiring 5+8=13 bits. The idea is to assign frequently used characters fewer bits

and seldom used characters more bits. In this example, the average number of bits required per original character is: 0.96×5 + 0.04×13 = 5.32. In other words, an overall compression ratio of: 8 bits/5.32 bits, or about 1.5:1.

Huffman encoding takes this idea to the extreme. Characters that occur most often, such the space and period, may be assigned as few as one or two bits. Infrequently used characters, such as: !, @, #, $ and %, may require a dozen or more bits. In mathematical terms, the optimal situation is reached when the number of bits used for each character is proportional to the logarithm of the character's probability of occurrence.

--------------------------------------------------------------------