User:Ramakrishna.y

AlgorithmsContents

Importent sites

which are use full to me

http://en.wikipedia.org/wiki/User:Yasa.ramakrishna

the below site is MST(GRAPHS) http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

computer books http://www.w3schools.com/

http://en.wikipedia.org/wiki/Prim's_algorithm

http://www.karbosguide.com/

http://www.cs.cf.ac.uk/Dave/C/node10.html#SECTION001010000000000000000

http://www.englisch-hilfen.de/en/grammar/adverbs_position.htm

http://ranger.uta.edu/~cook/aa/lectures/applets/graph/primex1.html

http://www.topsites.at/www.english-coach.com/test.htm

Task 1

Learning Objectives

After successfully completing this module, you will be able to: Identify everyday life activities which can be described as algorithms Write an input specification for the algorithm Develop clear and precisely stated steps to expresses the algorithm Write an output specification for the algorithm Identify good and bad algorithms and justify

Introduction

What is an algorithm?

An algorithm is “a precise rule (or set of rules) specifying how to solve some problem.” The study of algorithms is one of the key foundations of computer science. Algorithms are essential to the way computers process information, because a computer program is essentially an algorithm that tells the computer what specific steps to perform (in what specific order) in order to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards. Thus, an algorithm can be considered to be any sequence of operations that can be performed by a computing device such as a computer.

Why algorithms are necessary?

"No human being can write fast enough, or long enough, or small enough to list all members of an enumerable infinite set by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain enumerable infinite sets: They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols"

Media:Media:Algorithms Walk Through Video Download Video

Instructions

All the assignments that are part of this module should be submitted in the form of a gurukulam online document. You can access this feature with your gurukulam.in account. The URL for the online document is http://docs.google.com/a/gurukulam.in

Problem Set Level A-

Identify SIX different everyday life activities and describe them as algorithms.

Do not pick the examples that are covered in the walk through video OR that are specified here. The following is an example algorithm:

Algorithm to "make a phone call" Input - Telephone number Pick up the telephone handset Listen for dial tone If there is a dial tone Key in the input telephone number by pushing the buttons on the number pad Listen for ring tone If there is ring tone Wait for the recipient to pick the call If there is no ring tone Put the receiver down and try again from step 1 If there is no dial tone Send a message to telephone operators Output - Successful telephone call

Problem Set Level A

Identify and write FOUR more algorithms that are found in everyday life. [edit]

Problem Set Level A+

Identify and write ONE unique everyday life algorithm. No one else in the class should have identified this algorithm.

Task 2

Tracing an AlgorithmContents

[edit]

Learning Objectives

Identify the variables in the algorithm that need to be traced Examine the value of the variables at each step in the execution of the algorithm Determine if the algorithm is giving the correct outputs for a set of legitimate/legal input values Analyze and determine what the purpose of the algorithm [edit]

Introduction

In this module we will see examples of computational algorithms and the techniques used for tracing algorithms. A computational algorithm is a set of precise instructions expected to be expressed as a computer program that can execute on a computer.

Fundamentals of Computational Algorithms

A variable is used to represent a data value needed for an algorithm A variable can store only one data value at a time

A variable can also be used to represent an ordered collection of data values. Such a variable is called vector. A data value in a vector is named using the variable name and a subscript.

[edit]

Walk Through Videos

Computational Algorithm Example Download Video Tracing the Result of an Algorithm Download Video edit]

Problem Set Level A-

Write an algorithm that takes a number as input and outputs the number's multiplication table (till times 20) on the console. Consider the algorithm 1 below displayed in the first box. Trace the algorithm using a = 7 and b = 10 and then using a = 105 and b = 239. Show the values of a and b after each step In one sentence, state what this algorithm is computing. Consider the algorithm 2 below displayed in the second box. Trace the algorithm using n = 5 then using n = 10. Show the values of i after each step In one sentence, state what this algorithm is computing.

Algorithm 1:

1. b = a + b
2. a = b - a
3. b = b - a
4. Output a
5. Output b

Algorithm 2:

 1. Set i = 1
 2. Do the following n times:
   a. If i % 2 == 0
      i. Output i
   b. Add 1 to i

Problem Set Level A

Write an algorithm that takes a series of numbers as input and stores the data set in a vector variable. Calculate the arithmetic mean of this data set and output to the console. Consider the algorithm below displayed in the first box. Trace the algorithm 1 using n = 736 and then using n = 105. Show the values of p, q and r after each step In one sentence, state what this algorithm is computing. Consider the algorithm 2 below displayed in the second box. Trace the algorithm using n = 736 and then using n = 105. Show the values of x, n and i after each step In one sentence, state what this algorithm is computing.

Algorithm 1:

1.  Set p = n modulo 10
2.  Set q = n modulo 100
3.  Set r = (p*100)
4.  Add q-p to r
5.  Add (n-q)/100 to r
6.  Output r

Algorithm 2:

 1. Set x to 0
 2. Do the following until n => 10
    a. Set i to n % 10
    b. Add i to x
    c. Set n to floor(n/10)
 3. Add n to x
 4. Output x

Problem Set Level A+

Write an algorithm that takes a series of numbers as input and stores the data set in a vector variable. Calculate the mode of this data set and output to the console. Consider the algorithm below displayed in the first box. Trace the algorithm 1 using x = 7 and y = 10 and then using x = 15 and y = 17. Show the values of x, y and z after each step In one sentence, state what this algorithm is computing. Consider the algorithm 2 below displayed in the second box. Trace the algorithm using n = 5 and then using n = 10. Show the values of x and i after each step In one sentence, state what this algorithm is computing.

[Algorithm 1:]

 1.  If x > y, exchange values of x and y
 2.  Set z to 0
 3.  Do the following till x == y:
      a. Add 1 to x
      b. Add x to z
 4.  Output z

Algorithm 2:

 1. Set i to 1
 2. Set x to 0
 3. Do the following n times:
    a. If i % 2 != 0
       i. Add i to x
    b. Add 1 to i
 4. Output x

Task 3

Visualize Algorithms with FlowchartsContents

Learning Objectives

Identify the components of a given flow chart Trace the flow and execution of flow charts Design computational algorithms using flow charts

Introduction

Raptor Overview Raptor Simple Interest Example Raptor Conditionals Overview Raptor Control Structures

Problem Set Level A-

Use Raptor to implement the following algorithm as a flow chart: Run the following test cases after completing the flowchart to check the correctness of the algorithm

Test Cases Find all positive values for n less than 1000 such that: n modulo 5 = 4 and n modulo 11 = 5

Find all positive values for n less than 1000 such that: n modulo 7 = 5 and n modulo 11 = 8 Find all positive values for n less than 1000 such that: n modulo 27 = 13 and n modulo 16 = 7

Find all positive values for n less than 1000 such that: n modulo 25 = 0 and n modulo 4 = 0

Algorithm:

1.  Input a.
2.  Input b.
3.  Input x.
4.  Input y.
5.  Set n equal to 1.
6.  While n ≤ x*y do the following:
    a. If n modulo x = a do the following (otherwise skip step i):
       i. If n modulo y = b do the following (otherwise skip steps a1,b1):
          a1. Set answer equal to n.
          b1. Set n equal to x*y.
    b. Add 1 to n.
7.  While answer < 1000 do the following:
    a. Output answer.
    b. Add x*y to answer.

Problem Set Level A

1.Develop a flow chart, using Raptor, that takes a number as input and gives the number's multiplication table (till times 20) as output onto the console.

2.Run the 3 test cases after completing the multiplication table flowchart to check the correctness of the algorithm.

3.Develop a flow chart, using Raptor, that takes a series of numbers as input and stores the data set in a vector variable. Calculate the arithmetic mean of this data set and output to the console.

4.Run the 3 test cases after completing the arithmetic mean flowchart to check the correctness of the algorithm.

Problem Set Level A+

Develop a flowchart to shuffle the elements of a given array.

Example: 
Input to the algorithm = [1, 5, 2, 6, 9, 8]
Output of the algorithm = [5, 9, 6, 8, 1, 2] (This example need not match the output of yourflowchart)

Hint: You may use the random function available in the Raptor math functions.

Task 4

Numerical AlgorithmsContents

Instructions to Students

Learning Objectives

Write algorithms for solving numerical problems Identify test cases to verify the correctness of the numerical algorithm Trace the execution of numerical problems for different test cases

Introduction

Check Even or Odd Algorithm Download Video Check Prime Number Algorithm Download Video

Problem Set Level A-

Develop the flowchart, using Raptor, to compute the factors of a given number. Trace the algorithm for the following test cases. Test Case 1: 243 Test Case 2: 24 Test Case 3: 98

Problem Set Level A

Develop the flowchart, using Raptor. You will be given a number as input. The algorithm check if the number is a palindrome number or not. Trace the algorithm for the following test cases and submit a report. Test Case 1: 12321 Test Case 2: 200002 Test Case 3: 7848283

Problem Set Level A+

Develop a flowchart, using Raptor, to find the first n Hardy-Ramanujan numbers.

1729 is known as the Hardy-Ramanujan number. It is the smallest number expressible as the sum of two positive cubes in two different ways.

Example: 
1729 can be expressed as 1^3 + 12^3 or 9^3 + 10^3

Task 15

HeapsContents

Instructions to Students

Learning Objectives

Understand the traversal of the elements in heaps Illustrate the addition and deletion of an element in the heap

Introduction

Heaps Video Download Video

Problem Set Level A-

For the list of Integers, 3,4,8,21,28,13,19,25,20,7,13,22

Insert 6

Draw the tree pictures and show the movement of the elements through arrows while inserting the data values.

Note: The above heap is a minheap.

Problem Set Level A

For the tree constructed in problem set A

Delete 3.

Draw the tree pictures and show the movement of the elements through arrows while deleting the data values.

Problem Set Level A+

A d-heap is a simple generalization of a binary heap. A d-heap is exactly like a binary heap except that all nodes have d children (thus, a binary heap is a 2-heap). The goal of this assignment is to compare different implementations of heap sort using d-heaps with different values of d.

Implement the heap sort algorithm using d-heap.
Using a random number generator, generate 2 lists of integers L1 and L2 of sizes 50,000, and 100,000, respectively.
Sort each of the two lists using d = 2, 4, 7, and 9.
For each of the 8 runs, count the number of comparisons and measure the execution time.

Submit the following by the deadline:- A report including: 1) description of your heap sort algorithm.

heaps information

Data Structures/Min and Max Heaps From Wikibooks, the open-content textbooks collection < Data StructuresTop Introduction - Asymptotic Notation - Arrays - List Structures & Iterators - Stacks & Queues - Trees - Min & Max Heaps - Graphs - Hash Tables - Sets - Tradeoffs

Min and Max Heaps

A heap is an efficient semi-ordered data structure for storing a collection of orderable data. A min-heap supports two operations:

 INSERT(heap, element)
 element REMOVE_MIN(heap)

(we discuss min-heaps, but there's no real difference between min and max heaps, except how the comparison is interpreted.)

This chapter will refer exclusively to binary heaps, although different types of heaps exist. The term binary heap and heap are interchangeable in most cases. A heap can be thought of as a tree with parent and child. The main difference between a heap and a binary tree is the heap property. In order for a data structure to be considered a heap, it must satisfy the following condition (heap property): If A and B are elements in the heap and B is a child of A, then key(A) ≤ key(B).

(This property applies for a min-heap. A max heap would have the comparison reversed). What this tells us is that the minimum key will always remain at the top and greater values will be below it. Due to this fact, heaps are used to implement priority queues which allows quick access to the item with the most priority. Here's an example of a min-heap:

A heap is implemented using an array that is indexed from 1 to N, where N is the number of elements in the heap.

At any time, the heap must satisfy the heap property

 array[n] <= array[2*n]

and

 array[n] <= array[2*n+1]

whenever the indices are in the arrays bounds.

Compute the extreme value

We will prove that array[1] is the minimum element in the heap. We prove it by seeing a contradiction if some other element is less than the first element. Suppose array[i] is the first instance of the minimum, with array[j] > array[i] for all j < i, and . But by the heap invariant array, array[floor(i / 2)] < = array[i]: this is a contradiction.

Therefore, it is easy to compute MIN(heap):

 MIN(heap)
    return heap.array[1];

Removing the Extreme Value

To remove the minimum element, we must adjust the heap to fill heap.array[1]. This process is called percolation. Basically, we move the hole from node i to either node 2i or 2i + 1. If we pick the minimum of these two, the heap invariant will be maintained; suppose array[2i] < array[2i + 1]. Then array[2i] will be moved to array[i], leaving a hole at 2i, but after the move array[i] < array[2i + 1], so the heap invariant is maintained. In some cases, 2i + 1 will exceed the array bounds, and we are forced to percolate 2i. In other cases, 2i is also outside the bounds: in that case, we are done.

Ignore remove algorithm, I'm 100% sure it won't work. Therefore, here is the remove algorithm:

REMOVE_MIN(heap)
  return_value = heap.array[1];
  hole_index = 1;
  while (hole_index < heap.array.len) {
    if (2 * hole_index > heap.array.len)
      break;
    if (2 * hole_index + 1 > heap.array.len)
      {
        heap.array[hole_index] = heap.array[2*hole_index];
        hole_index = 2 * hole_index;
      }
    else
      {
        if (heap.array[2*hole_index] < heap.array[2*hole_index+1])
          new_hole_index = 2 * hole_index;
        else
          new_hole_index = 2 * hole_index + 1;
        heap.array[hole_index] = heap.array[new_hole_index];
        hole_index = new_hole_index;
      }
   }
  heap.array.len -= 1;

Inserting a value into the heap

A similar strategy exists for INSERT: just append the element to the array, then fixup the heap-invariants by swapping. For example if we just appended element N, then the only invariant violation possible involves that element, in particular if array[floor(N / 2)] > array[N], then those two elements must be swapped and now the only invariant violation possible is between

array[floor(N/4)]  and  array[floor(N/2)]

we continue iterating until N=1 or until the invariant is satisfied. INSERT(heap, element)

  append(heap.array, element)
  i = heap.array.length
  while (i > 1)
    {
      if (heap.array[i/2] <= heap.array[i])
        break;
      swap(heap.array[i/2], heap.array[i]);
      i /= 2;
    }

TODO

Make-heap: it would also be nice to describe the O(n) make-heap operation
Heap sort: the structure can actually be used to efficiently sort arrays
Treaps: heaps where elements can be deleted by name

Tasks

Recursion

Program Set Level A-:

Part -1

Here is a recursive function: 
f(n) = n + f(n-1), n ≥ 1 
f(0) = 0 
Compute f(4). Show your work. 
What does this recursive function compute in general in terms of n? 
F(n) = n + f(n-1), n > 1
f(1) = 1 + f(1-1)
f(1) = 1 + f(0)
f(1) = 1 + 0 
f(1) = 1
f(2) = 2 + f(2-1)
f(2) = 2 + f(1)
f(2) = 2 + 1
f(2) = 3
f(3) = 3 + f(3-1)
f(3) = 3 + f(2)
f(3) = 3 + 3
f(3) = 6
f(4) = 4 + f(4-1), 4>1
f(4) = 4 + f(3), 
f(4) = 4 + 6
f(4) = 10

Draw a flowchart for a computation that computes the same result for some positive value of n using a loop without using recursion.

Part 2:

Consider the following recursive definition: 
f(n) = f(n-1) * f(n-2), n > 2 f(2) = 3 f(1) = 2 
Draw a recursion tree for f(5). 
Using the recursion tree, calculate f(5).
f(3) = f(3-1) * f(3-2)
f(3) = f(2) * f(1)
f(3) = 3 * 2
f(3) = 6
f(4) = f(4-1) * f(4-2)
f(4) = f(3) * f(2)
f(4) = 6 * 3
f(4) = 18
f(5) = f(5-1) * f(5-2)
f(5) = f(4) * f(3)
f(5) = 18 * 6
f(5) = 108

f(5) = f(2) * f(1) * f(2) * f(2) * f(1) = 3 * 2 * 3 * 3 * 2
f(5) = 108

Part 3:

The following Scheme function mystery is written recursively. (define (mystery numlist))

 (if (null? numlist)                 ; is list empty?
     0                               ; if so, answer for this list is 0
     (+ 1 (mystery (rest numlist)))  ; if not, answer for this list is 
                                     ;     1 + answer for rest of list 
  )

) What value does this function compute for the numlist (34 25 74 53 92)? Show your work, step by step. Explain in one sentence what this Scheme function computes in general.

Solution:

( (mystery (34  25   74  53  92)))
(+1 (mystery (25  74  53 92))))
( + 1 (+ 1 (mystery (74  53 92)))))
( + 1 (+ 1 (+ 1 (mystery (53 92))))))
( + 1 (+ 1 (+ 1 ( + 1(mystery (92)))))))
( + 1 (+ 1 (+1 (+ 1 (+ 1 (mystery ()))))))) (since: rest numlist=null )
( + 1 (+ 1 (+1 (+ 1 (+ 1 0 ))))))
( + 1 (+ 1 (+1 (+ 1  1)))))
( + 1 (+ 1 (+1  2))))
( + 1 (+ 1 3))
(+ 1 4)
=5

Problem Set Level A:

1. How many times is the smallest disc moved if there are N=5 discs? Based on this, come up with a formula for the number of times the smallest disc is moved for a puzzle with N discs, where N > 0.

Solution:

1.	If I consider n=1 disc in this case the smaller disc moves only one step to complete the puzzle.
2.	if I consider n=2 discs in this case the smaller disc moves two steps to complete the puzzle, the moments are 1,3.
3.	if I consider n=3 discs in this case the smaller disc moves four steps to complete the puzzle, the moments are 1,3,5,7.
4.	if I consider n=4 discs in this case the smaller disc moves eight steps to complete the puzzle the moments are 1,3,5,7,9,11,13,15. 
     -------------
     -------------
     -------------
     -------------
n. If I consider n=n discs in this case the smaller disc moves 2n-1 steps to complete the puzzle, the moments are all odd number moments like 1,3,5,7,…………

2. If the puzzle has 15 discs, exactly how many moves are required to move the discs using the algorithm? If it takes a robot arm 10 seconds to make one disc move, approximately how many days would it take the robot to solve this puzzle assuming it works constantly without breaks?

Solution:

As for n discs the no.of steps to complete the given puzzle is given by 2n -1
For the 15 discs to complete the puzzle is given by 215 -1 = 32767
AS by given data the robot take 10 sec for each so in order to complete the puzzle the robot takes  327670 secs 
Nearly 3.79 days

Program Set Level A+:

Recall the following Scheme definitions: 
        (define john (list 'Doe 85000 'Senior-Accountant 'Accounting))
        (define jane (list 'Smith 97000 'Manager 'Web-Services))
        (define mike (list 'Brown 70000 'Programmer 'Systems-Support))
        (define (salary employee) 
            (first (rest employee)))

Complete the definition of the function sum shown below so that it recursively computes the sum of  all of the salaries of the employees.

The variable employees is a list of employees, such as (list john jane mike).

 (define (sum-salaries employees)
      (if (null? employees) _________
          (+ _____________________________
             _____________________________
          )
      )
 )

Solution:

(sum-salaries  (employees  (john  jane  mike)))
 (+85000(sum-salaries(employees(jane  mike))))
 (+85000(+97000(sum-salaries(employees(mike)))))
(+85000(+97000(+70000(sum-salaries (emplyees ( ))))))))
(+85000(+97000(+70000(+0))))
(+85000(+97000(+70000)))
(+85000(+167000))
=252000