TOPIC 3 : INTRODUCTION TO DATA STRUCTURES

3.1 Data structures - Stack

Assignment 3.1.1: Application of Stack Data Structure

Objective: To understand how to apply Stack Data Structure.

Problem Description: Write a pseudo code to find the binary value of a given integer and 

display it.

Hint: Consider the integer 5. To convert 5 to binary, the following procedure needs to be 

adopted.

               2|_5____

               2|_2_-_1_

                   _1__- 0_

Each time, store the remainder in an appropriate data structure and use LIFO to get the 

binary value.

TOPIC 2: LOGIC BUILDING USING PSEUDO CODE part-3

2.3 Iteration Control Structures

Assignment 2.3.1 Pseudo code - Iterational pattern (1)

Objective: Write pseudo code for iterational pattern problems.

Problem 1 :

The problem given in Assignment 2.1.2 is extended to check whether 

the Number of Hours accepted from the user is less than or equal to 0. If so display an error 

message. Reenter the data the Number of Hours until valid data is entered.

Step 1: Write the following Pseudo code

CALC_GROSS_PAY
1. input No_of_Hours, Pay_Rate
2. while(------------) do
3. display "---------------------"
4. -------------------------------------
5. end while
6. Gross_Pay =  No_of_Hours * Pay_Rate
7. display " The gross pay is equal to : ", Gross_Pay
8. end

Step 2 : Fill in the missing (------) parts in the Pseudo code
We need to put a condition in the parenthesis of while ( ) loop, which could test the validity of the data input by the user for the number of hours. We need to keep the loop running displaying a message as long as the condition in the parenthesis remains true. Therefore the complete form the above pseudocode is given as :

CALC_GROSS_PAY

1. input No_of_Hours, Pay_Rate

2. while(No_of_Hours < = 0) do

3. display "Invalid Entry, Enter Valid Number of hours. "

4. input No_of_Hours

5. end while

6. Gross_Pay =  No_of_Hours * Pay_Rate

7. display " The gross pay is equal to : ", Gross_Pay

8. end

Problem 2 :

Write a pseudo code to calculate the Loan Balance, where a person borrows an amount A and in return he/she agrees to make N payments per year, each of amount P. While the person is repaying the loan, interest will accumulate at an annual percentage rate of R, and this interest will be compounded N times a year (along with each payment). Therefore, the person must continue paying these installments of amount P until the original amount and any accumulated interest is repaid.

NOTE: The formula to calculate the amount that the person needs to repay after T years is :

Balance amount after T years = 

TOPIC 2: LOGIC BUILDING USING PSEUDO CODE

2.2 Selection Control Structures

Assignment 2.2.1: Pseudo code - Selectional pattern (1)

Objective: Write pseudo code for selectional pattern problems

Problem Description: The problem given in Assignment 2.1.2 should be extended to check whether the Number of Hours accepted from the user is less than or equal to 0. If so an appropriate error message should be displayed.

The problem given in assignment 2.1.2 is here.

The pseudo-code with required changes can be written again as :

Calculate-Gross-Pay

1. input No_of_Hours, Pay_Rate

2. if  No_of_Hours < = 0 then

3. Display " The Number of hours are invalid."

4. else

5. Gross_Pay = No_of_Hours * Pay_Rate

6. Display "Gross Pay is : ", Gross_Pay

7. end

Assignment 2.2.2: Selectional pattern (2)

Objective: To develop pseudo code writing skills for a given problem using certain logic.

Case study: An institution offers several programs. Each program has several courses. There 

are students who have opted for these courses. There are Educators who offer these courses.

Problem 1:

At a given point of time we need to allocate a course to an educator for a given

period. Before allocating a course to an educator the following conditions are to be checked.

1. Enough number of students have registered for the course

AND

2. The course is added into the educator’s skill set

AND

3. Educator’s calendar is free for the given period

AND

4. Educator is not on leave for the given period

And

5. Educator has not yet completed his delivery targets Or There is no other alternative

SOLUTION :

COURSE_ALLOCATION

1. input course

2. input num_of_students

3. input educator's_skill_set, spare_time, is_on_leave, delivered_targets, allocation

4. if ( (num_of_students > min_number_students) && (educator's_skill_set = course) && (spare_time = true ) && (is_on_leave = false) && (delivered_targets = true ) ) then

5. set allocation = true
6. end if

7. display "Course is allocated. "

8. end

Problem 2: For a student, following is the course qualifying criteria.

1. Student has registered for the course

2. Attended at-least 80% of the classes

or attended at-least 60% of the classes and submitted medically unfit certificate

3. Submitted all the assignments

4. Completed project

5. Scored 80% marks in the test or the retest

QUALIFYING_STUDENT

1. input classes_attended, min_score

2. input course_reg, medical_certificate, submitted_assignments, completed_project

3. if ( ( course_reg = true ) &&(classes_attended >= 80 || (classes_attended >= 60 && medical_certificate = true ) ) && (submitted_assignments = true ) && (completed_project = true) && ( min_score >= 80)) then

4. set course_qualification = true
5. end if

6. display "Congratulations, course has been qualified. "

7. end 

Assignment 2.2.3: Selectional pattern (3)

Objective: To use the problem solving techniques learnt so far in a real life application.

Problem 1: Take marks of a trainee in a module as input and calculate the grade and
grade points. The grade table is given below:

SOLUTION :

CALC_GRADE
1. input marks_obtained
2. if ( marks_obtained >= 80 ) then
3. grade_point = 5
4. grade = A
5. elseif ( marks_obtained >= 73 && marks_obtained <=79 ) then
6. grade_point = 4.5
7.  grade = B+
8. elseif ( marks_obtained >= 65 && marks_obtained <=72 ) then
9. grade_point = 4
10. grade = B
11. elseif ( marks_obtained >= 55 && marks_obtained <=64 ) then
12. grade_point = 3
13. grade = C
14. elseif ( marks_obtained >= 0 && marks_obtained <=54 ) then
15. grade_point = 2
16. grade = D
17. end if
18. display " The grade points obtained are equal to: ", grade_point
19. display " The grade awarded is : ", grade
20. end


Problem 2 :
Take marks of a trainee in all generic modules (listed below)as input and calculate the
Generic GPA. The method for calculating Generic GPA is as follows:

Grade points for marks are given in previous problem and credit points are as follows:

SOLUTION :

CALC_GPA
1. input marks_obtained
2. if ( marks_obtained >= 80 ) then
3. grade_point = 5
4. grade = A
5. elseif ( marks_obtained >= 73 && marks_obtained <=79 ) then
6. grade_point = 4.5
7.  grade = B+
8. elseif ( marks_obtained >= 65 && marks_obtained <=72 ) then
9. grade_point = 4
10. grade = B
11. elseif ( marks_obtained >= 55 && marks_obtained <=64 ) then
12. grade_point = 3
13. grade = C
14. elseif ( marks_obtained >= 0 && marks_obtained <=54 ) then
15. grade_point = 2
16. grade = D
17. end if
18 GPA = ( marks_obtained * grade_point ) / marks_obtained
19. display " The grade points are : ", grade_point
20. display " The GPA obtained : ", GPA
21. end

INFOSYS FOUNDATION TRAINING PROGRAM (FTP) SOLUTION FOR LAB-GUIDE ASSIGNMENT PROBLEM SOLVING AND LOGIC BUILDING- part-2

TOPIC 1 : COMPUTATIONAL PROBLEM SOLVING

1.1 COMPUTATIONAL PROBLEM SOLVING AND ALGORITHM

ASSIGNMENT 1.1.1 : PROBLEM SOLVING EXERCISES ( part-b )

1. In an objective type programming contest, following are the rules

a. It will have multiple rounds.

b. In each round, every participant will get a set of 10 question out of which

one question is marked as star question (The toughest one).

c. The participant will get the next set, only if 50% of the questions are

marked correctly in the previous round or he attempted the star question

correctly. Otherwise he will be out of the contest.

It is found that in each round 50% of the participants are not able to attempt 50%

of the questions correctly but one out of those 50% participants, attempts the

star question correctly.

If only 4 participants are left for the 5th round what was the number of

participants in the first round?

SOLUTION :

Let the students appeared for 1st round be = x

Students appearing for the 2nd round :

Since half of them made for the 2nd round, which constitute = x / 2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are = x/ 2 + 1 = (x + 2)/ 2

Students appearing for the 3rd round :

Since half of the previous round students made for the 3rd round, which constitute = ( (x + 2)/ 2 )/2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are =  ( (x + 2)/ 4 ) + 1 = (x + 6)/ 4

Students appearing for 4th round :

Since half of the previous round students made for the 3rd round, which constitute = ( (x + 6)/ 4 )/2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are =  ( (x + 6)/ 8 ) + 1 = (x + 14)/ 8

Students appearing for 5th round :

Since half of the previous round students made for the 3rd round, which constitute = ( (x + 14)/ 8 )/2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are =  ( (x + 14)/ 16 ) + 1 = (x + 30)/ 16

Since it is given that the number of students appeared for the 5th round are =  4

This implies the expression we got for the 5th round i.e. (x + 30)/ 16 becomes = 4

i.e.                                                   (x + 30)/ 16 = 4

                                                         (x + 30 ) = 64

                                                            x = 64 - 30

                                                               x = 34

Since we assumed ' x ' to be the number of students present during the 1st round, which came out to be = 34. It means there were total of 34 students present in the 1st round.

2. A farmer had a lazy son. The farmer wanted his son to work in the farm. So he offered that the son will work for 50 days, for each day the son works, he will get 10 rupees, for each day he will not work, he need to pay back 15 rupees to his father. At the end of 50 days, when the son counted his income, it turned out that he had not got anything. How many days did the son actually worked?

SOLUTION :

Let the son worked for =  x days
money earned for x days = 10x

No. of days on which he didn't work = (50 - x)
Money he lost for days he didn't work = 15 ( 50 - x )

It is given in that the money he earned balances the money he paid back, which means :

                                                      10x = 15 ( 50 - x )
                                                       10x = 750 - 15x
                                                            25x = 750
                                                           x = 750/25
                                                              x = 30
Since we assumed ' x ' to be the number of days for which son worked, which came out to be = 30 days. Therefore, Son worked for 30 days.

INFOSYS FOUNDATION TRAINING PROGRAM (FTP) SOLUTION FOR LAB-GUIDE ASSIGNMENT PROBLEM SOLVING AND LOGIC BUILDING

TOPIC 1 : COMPUTATIONAL PROBLEM SOLVING

1.1 COMPUTATIONAL PROBLEM SOLVING AND ALGORITHM

ASSIGNMENT 1.1.1 : PROBLEM SOLVING EXERCISES

1 . The King ordered his servants to fill up his treasury. Each of the 3 servants, had to go to the treasury, count how much gold coins there was at that moment, and then triple it and leave. But then the King felt sorry for them and thought that he should probably reward the servants in some way, so he let each of them take 1 gold coin out before leaving. Once again the King had a good luck. He collected exactly 500 gold coins in the treasury. How much gold coins did he have before the order.

SOLUTION

Let initially coins be = x
a servant has to make thrice of them, which means, coins should be = 3x
and a servant is allowed to take 1 coin, which leave the total coins to =  ( 3x - 1 )

Next servant comes and does the same thing of making the count of coins to 3-times, which makes the present count to =                      3 ( 3x - 1 )
and when he take 1-coin out , then the present count becomes =  ( 3 ( 3x - 1 ) - 1 )

Finally the 3rd servant comes and make the present count to thrice again making it = 
3 ( 3 ( 3x - 1 ) - 1 )
and when he also takes 1-coin out, the total count becomes = ( 3 ( 3 ( 3x - 1 ) - 1 ) -1 )

At last, it was found that the total count of the coins = 500

which means our expression ( 3 ( 3 ( 3x - 1 ) - 1 ) -1 ) = 500

solving this expression step by step :
                                                  ( 3 ( 9x - 3 - 1) - 1 ) = 500
                                                    27x  - 12 - 1  = 500
                                                           27x -13 = 500
                                                             27x = 513
                                                             x = 513 / 27
                                                                x = 19
since ' x ' is the number of coins initially present in the treasury. It means 19 coins were initially present in the treasury.
                                                    

2. John decided to start working. He was hired on the following terms: during 30 days, for each day John works, he gets 6 dollars, for each day he doesn't work,he pays back 9 dollars. At the end of the month, when they counted his wages, it turned out that he had not got anything. How many days did John actually work?


SOLUTION :

Let the number of days for which Jhon worked be = x
This implies, the number days for which Jhon didn't work = 30 - x

Jhon gets 6 $ for each day he works
therefore, his total wages for his working days become = 6x

Jhon has to pay back 9 $ for the day he don't work
therefore, he has to pay back total of = 9( 30 - x )

Since Jhon gets nothing at the end of the month as the money he has to pay back balances the money he earned, which means : 

                                                              6x = 9( 30 - x )
                                                              6x = 270 - 9x
                                                                15x = 270
                                                                x = 270 / 15
                                                                   x = 18
Since, we assumed ' x ' to be the number of days for which Jhon worked, and it comes out to be 18 days for which Jhon worked for the company.
                                 


3. Smith's boss proposed to pay him in the following way: "See, there is some money in the purse. Every day I'll add 5 dollars to it, and then you'll take out half of what's in it”. Three days later it turned out that there were6 dollars left in the purse. How much did Smith get for three days' work ?

SOLUTION :

Let the amount of money present in the purse initially be = x
1st day The boss added 5 $ to the purse and the total amount becomes = x + 5
The employee took half of the total amount , which means, he took = ( x+ 5 ) / 2.............(i)
Money left behind in the purse = (x + 5 ) - ( x + 5 ) /2

2nd day The boss added 5 $ again to the purse, which makes the total amount present in the purse to   = 5 + ( x + 5 )/ 2  =  (10 + x + 5) / 2 =   ( x + 15 )/ 2
The employee took half of the amount present in the purse , which means, for this time, he took-
( x + 15 )/ 2*2 = ( x + 15 )/ 4................................(ii)
Money left behind in the purse = ( x + 15 )/ 2 -  ( x + 15 )/ 4 = ( x + 15 )/ 4

3rd day The boss added 5 $ again to the purse, which makes the total amount present in the purse to  = 5 + ( x + 15 )/ 4 = ( x + 35 ) / 4
The employee took half of the amount present in the purse , which means, for this time, he took-
( x + 35 ) / 4 *2 = ( x + 35 ) / 8..............................(iii)
Money left behind in the purse =  ( x + 35 ) / 4 - ( x + 35 ) / 8 = ( x + 35 ) / 8

Since money left in the purse on 3rd day = ( x + 35 ) / 8
and it is given that on 3rd day money present in the purse = 6 $
which means :
                                                           ( x + 35 ) / 8 = 6
                                                               x + 35 = 48
                                                                    x = 13

Since, we assumed ' x ' as the money present in the purse initially, which means there were 13 $ present in the purse initially.

We've to find out the amount earned by the employee on 3rd day, which we can calculate by adding (i), (ii) and (iii) expressions above  as :

                           ( ( x+ 5 ) / 2 )   +   ( ( x + 15 )/ 4 )      +    ( ( x + 35 ) / 8 )
Putting 13 in place of x, we get the expression as :
                           ( ( 13 + 5 ) / 2 ) +  ( ( 13 + 15 ) / 4)   +   ( ( 13 + 35 ) / 8) 
                                       ( 18/ 2 )   +      (28 / 4 )    +     (48 / 8 )
                                                             9 +  7 +  6
                                                                   22


This implies the total of 22 $ earned by the employee. and If we see the amount only for 3rd day, it comes out to be : ( x + 35 ) / 8 =  ( 13 + 35 ) / 8  =    (48 / 8 )  =    6


4. Two friends who have an eight-quart jug of water wish to share it evenly. They also have two empty jars, one holding five quarts, the other three. How can they each measure exactly 4 quarts of water ?

SOLUTION : 

Step-1:
First of all water from 8-quart jug is poured into 3-quart jar, so now the values are :
8-quart jug = 5-quart water
3-quart jar = 3-quart water
5-quart jar = 0-quart water

Step-2 :
Now, water from 3-quart jar is poured into 5-quart jar, so now the values are :
8-quart jug = 5-quart water
3-quart jar = 0-quart water
5-quart jar = 3-quart water

Step-3:
Now again, water from 8 quart jug is poured into 3-quart jar, so now the values are :
8-quart jug = 2-quart water
3-quart jar = 3-quart water
5-quart jar = 3-quart water

Step-4:
Now, water from 3-quart jar is poured into 5-quart jar, Notice this time, since the 5-quart jar is left with only 2-quarts of capacity, therefore, 3-quart jar will be able to pour only 2-quarts of water, leaving 1-quart behind. So now the values are :
8-quart jug = 2-quart water
3-quart jar = 1-quart water
5-quart jar = 5-quart water

Step-5:
Now, the whole of water from 5-quart jar is poured back into 8-quart jug, which will set the values to :
8-quart jug = 7-quart water
3-quart jar = 1-quart water
5-quart jar = 0-quart water

Step-6:
Now, pour the water from 3-quart jar into 5-quart jar, making the values to :
8-quart jug = 7-quart water
3-quart jar = 0-quart water
5-quart jar = 1-quart water

Step-7:
Now again, fill the 3-quart jar by pouring water from 8-quart jug, making the values to :
8-quart jug = 4-quart water
3-quart jar = 3-quart water
5-quart jar = 1-quart water

Step-8:
Now, fill this 3-quart of water from 3-quart jar to 5-quart jar, and see it yourself that we have successfully divided  8-quarts of water into equal halves, so that both friends can get exactly 4-quarts of water. And the values can finally be seen as :
8-quart jug = 1-quart water
3-quart jar = 3-quart water
5-quart jar = 4-quart water 


5. The bin packing problem is an example of a wide set of problems. The task is to find how many set sized bins are required to hold a number of differently sized boxes. How many bins (10 units high) are required to contain the following boxes (1,3,4 and 5 units high) ?

SOLUTION :

Since, we've to put 1,3,4 and 5 units high boxes into 10 units high bins.
As can be seen, we can put 
1.)      1,4 and 5 units high boxes into 10 units high bin( all these boxes completely fit into bin w/o leaving any space behind )
2.)   Now we're left with only 3 unit high  box, which we've to put it into another 10 unit high bin, as we've no other option.