Reappear Throughout The Text – Be Sure You This Is A Key .

AbstractionAbstraction A mental model that removescomplex detailsThis is a key concept. Abstraction willreappear throughout the text – be sure youunderstand it!15

Internal and Abstract View2

DefinitionAbstraction is the act of representingessential features without including thebackground details or explanations. Inthe computer science and softwareengineering domain, the abstractionprinciple is used to reduce complexityand allow efficient design andimplementation of complex softwaresystems.3

Problem SolvingProblem solvingThe act of finding a solution to a perplexing,distressing, vexing, or unsettled questionHow do you define problem solving?4

Problem SolvingHow do you solve problems?Understand the problemDevise a planCarry out the planLook back5

StrategiesAsk questions!– What do I know about the problem?– What is the information that I have to processin order the find the solution?– What does the solution look like?– What sort of special cases exist?– How will I recognize that I have foundthe solution?6

StrategiesAsk questions! Never reinvent the wheel!Similar problems come up again and againin different guisesA good programmer recognizes a task orsubtask that has been solved before andplugs in the solutionCan you think of two similar problems?7

StrategiesDivide and Conquer!Break up a large problem into smaller unitsand solve each smaller problem– Applies the concept of abstraction– The divide-and-conquer approach can beapplied over and over again until eachsubtask is manageable8

Computer Problem-SolvingAnalysis and Specification PhaseAnalyzeSpecificationAlgorithm Development PhaseDevelop algorithmTest algorithmImplementation PhaseCode algorithmTest algorithmMaintenance PhaseUseMaintain9Can younamea recurringtheme?

Phase InteractionsShould weadd anotherarrow?(What happensif the problemis revised?)10

AlgorithmsAlgorithmA set of unambiguous instructions for solving aproblem or subproblem in a finite amount of timeusing a finite amount of dataAbstract StepAn algorithmic step containing unspecified detailsConcrete StepAn algorithm step in which all details are specified11

Developing an AlgorithmTwo methodologies used to develop computersolutions to a problem– Top-down design focuses on the tasks to bedone– Object-oriented design focuses on the datainvolved in the solution12

Summary of MethodologyAnalyze the ProblemUnderstand the problem!!Develop a plan of attackList the Main TasksRestate problem as a list of tasksGive each task a nameWrite the Remaining ModulesRestate each abstract module as a list of tasksGive each task a nameRe-sequence and Revise as NecessaryProcess ends when all steps (modules) are concrete13

Top-Down DesignProcess continues for as many levels as it takes to make every stepconcreteName of (sub)problem at one level becomes a module at next lowerlevel14

PseudocodePseudocodeA way of expressing algorithms that uses amixture of English phrases and indentationto make the steps in the solution explicitThere are no grammar rules in pseudocode,but it’s important to be consistent andunambigous19

Pseudocode FunctionalityVariablesNames of places to store valuesquotient, decimalNumber, newBaseAssignmentStoring the value of an expression into avariableSet quotient to 64quotient -- 64quotient -- 6 * 10 420

Pseudocode FunctionalityOutputPrinting a value on an output deviceWrite, PrintInputGetting values from the outside word andstoring them into variablesGet, Read21

Pseudocode FunctionalitySelectionMaking a choice to execute or skip a statement (or group ofstatements)Read numberIF (number 0)Write number " is less than zero."orWrite "Enter a positive number."Read numberIF(number 0)Write number " is less than zero."Write "You didn't follow instructions."29

Pseudocode FunctionalitySelectionChoose to execute one statement (or group of statements)or another statement (or group of statements)IF ( age 12 )Write "Pay children's rate"Write "You get a free box of popcorn"ELSE IF ( age 65 )Write "Pay regular rate"ELSEWrite "Pay senior citizens rate"30

Control StructuresControl structureAn instruction that determines the order inwhich other instructions in a program areexecutedCan you name the ones we defined in thefunctionality of pseudocode?31

Selection StatementsFlow of control of if statement32

Algorithm with SelectionProblem: Write the appropriate dress for a giventemperature.Write "Enter temperature"Read temperatureDetermine DressWhich statements are concrete?Which statements are abstract?33

Algorithm with SelectionDetermine DressIF (temperature 90)Write “Texas weather: wear shorts”ELSE IF (temperature 70)Write “Ideal weather: short sleeves are fine”ELSE IF (temperature 50)Write “A little chilly: wear a light jacket”ELSE IF (temperature 32)Write “Philadelphia weather: wear a heavy coat”ELSEWrite “Stay inside”34

Pseudocode FunctionalityRepetition Or IterationRepeating a series of statementsSet count to 1WHILE ( count 10)Write "Enter an integer number"Read aNumberWrite "You entered " aNumberSet count to count 1How many values were read?35

Pseudocode ExampleProblem: Read in pairs of positive numbers andprint each pair in order.WHILE (not done)Write "Enter two values separated by blanks"Read number1Read number2Print them in order36

Pseudocode ExampleHow do we know when to stop?Let the user tell us how manyPrint them in order?If first number is smallerprint first, then secondOtherwiseprint second, then first37

Pseudocode ExampleWrite "How many pairs of values are to be entered?"Read numberOfPairsSet numberRead to 0WHILE (numberRead numberOfPairs)Write "Enter two values separated by a blank; press return"Read number1Read number2IF(number1 number2)Print number1 " " number2ELSEPrint number2 " " number1Increment numberRead38

Logical operators AND True only if both the conditions are correct OR True if one of the conditions is true NOT True of the condition is False54

What is the output of following:x 10y 5z 25if(x y AND x z)print “x is the largest”else if (y x AND y z)print “y is the largest”elseprint “z is the largest”55

The output depends on values of x, y and z.For above examples, the output is - z is the largest.56

Write the outputx 10y 40if (x 10 OR y 40)print xelse if (x 5 OR y 100)print yelse if(x 5 OR y 100)print xprint y57

The output should104058

Find the outputx 50if( NOT (x 50))print “x is not equal to 50”elseprint “x is equal to 50”59

Output:x is equal to 5060

Find the outputnumber 5while (number 51)print numbernumber number 561

Output510152025303540455062

Find Outputsum 0number 0while (number 5)sum sum numbernumber number 1print sum63

Looping StatementsFlow of control of while statement79

Looping StatementsA count-controlled loopSet sum to 0Set count to 1While (count limit)Read numberSet sum to sum numberIncrement countWrite "Sum is " sum80Why is itcalled acount-controlledloop?

Looping StatementsAn event-controlled loopSet sum to 0Set allPositive to trueWHILE (allPositive)Read numberIF (number 0)Set sum to sum numberELSESet allPositive to falseWrite "Sum is " sum81Why is itcalled anevent-controlledloop?What is theevent?

Looping StatementsCalculate Square RootRead in squareCalculate the square rootWrite out square and the square rootAre there any abstract steps?82

Looping StatementsCalculate Square RootSet epsilon to 1WHILE (epsilon 0.001)Calculate new guessSet epsilon to abs(square - guess * guess)Are there any abstract steps?83

Looping StatementsCalculate New GuessSet newGuess to(guess (square/guess)) / 2.0Are there any abstract steps?84

Looping StatementsRead in squareSet guess to 0.1Set epsilon to 1WHILE (epsilon 0.001)guess (guess (square/guess))/2.0Set epsilon to abs(square - guess * guess)Write out square and the guess85

Pseudocode for CompleteComputer SolutionWrite "Enter the new base"Read newBaseWrite "Enter the number to be converted"Read decimalNumberSet quotient to 1WHILE (quotient is not zero)Set quotient to decimalNumber DIV newBaseSet remainder to decimalNumber REM newBaseMake the remainder the next digit to the left in the answerSet decimalNumber to quotientWrite "The answer is "Write answer86

Pseudocode for CompleteComputer SolutionWrite "Enter the new base"Read newBaseWrite "Enter the number to be converted"Read decimalNumberSet quotient to 1WHILE (quotient is not zero)Set quotient to decimalNumber DIV newBaseSet remainder to decimalNumber REM newBaseMake the remainder the next digit to the left in the answerSet decimalNumber to quotientWrite "The answer is "Write answer87

LoopsThe while loops have three parts:1. Initialization - fix the initial value2. Condition - when will we stop? until whileshall we continue?3. Update - update the value of variable sothat the condition is changed.Let’s explain with example.88

Q. Write pseudocode to print numbers from1 to 1001. Initialization - where to start? We startfrom 1set number 1 (initial value)2. Condition - until while to continue.continue until number becomes 101means while (number 101)89

3. Update - But the value of number is 1. Sowe need to increase the value and print it.We increase by 1.number number 190

The complete pseudocodenum 1(Initialization)while (num 101)(Condition)print numnum num 191(Update)

Q. Pseudocode to calculate the sum ofnumbers from 1 to n where n can be enteredby user.sum 1 2 3 . nAns:Read n from usernumber 1sum 092Initialization

while (number n)Conditionsum sum numberprint “Number:” numberprint “Sum:” sumnumber number 1Updateprint “Final Sum:” sumOutput: Let’s suppose the user entered n tobe 693

IterationNumberSum111223336441055156621Iteration means the number of times the loop isrun. For this loop the total number of iterationswill be n i.e. 6.94

Number: 1Sum: 15Sum: 1Number: 6Number: 2Sum: 21Sum: 3Number: 3Final Sum: 21Sum: 6Number: 4Sum: 10Number: 595We can actually print thefinal sum only as that’s whatwe need.

Q. Pseudocode to calculate the sum of squaresfrom 1 to 5.sum 12 22 32 42 52Ans:Instead of adding the number we just need toadd the sum of numbersum 0number 1while (number 6)sum sum number*number96

number number 1print “Final sum:” sumWhat should be the final sum?97

Q. Pseudocode to print the multiplicationtable of 5. You just need to print the valueslike 5, 10, , 50Ans:num 5while (num 51)print numnum num 598Can you figure outthe output?

Q. Pseudocode to convert decimal to binaryn 2Remainder is binary digit.Check Chapter 1 if confused.read decimalNumberwhile (decimalNumber 0)quotient decimalNumber / nremainder decimalNumber % 2print remaindermove remainder to the left of answerdecimalNumber quotient99

Q. Extract digits from a decimal numberRead numberwhile (number 0)% calculates the remainderThe digits here areremaindersremainder number % 10quotient number / 10number quotientprint remainder100

How to swap two numbers in variables?a 20b 30c aa bThis is similar to changing the glass ofjuice and beer. To do that, we need oneextra glass. We first pour beer in theextra glass, then pour juice in the beerglass and beer from extra glass to thejuice glass.b cprint “a ” aprint “b ” b101So what should be the value of a & b.

Q. Pseudocode to find the factorial of anumber.factorial (5) 1x2x3x4x5limit 5 (this could be any number)factorial 1num 1while (num limit)factorial factorial * numnum num 1102

Q. Pseudocode to calculate 3n.3n 3x3x3x .n timesRead n from user (or use n 10 or any number)num 1Difference between factorial and power.power 1while( num n)power power * 3num num 1103

A count-controlled loop. 81 Looping Statements Set sum to 0 Set allPositive to true WHILE (allPositive) Read number IF (number 0) Set sum to sum number ELSE Set allPositive to false Write "Sum is " sum Why is it called an event-controlled loop? What is the event? An event-controlled loop. 82