The next thing is that the video recap quiz, so we have, so this sheet all of you should have in fact you know I am just trying to say that you have to fill up your video quiz, the recap quiz questions that I will now be projecting you have to fill up your answers in the sheet that is given to you and then hand it over to the TAS, TAS please collect it from the set of students get it to you. You have to fill in your roll number, name, the slot, so we are in slot 11, today's date and then you know we may not have 8 questions every day but up to 8 questions can be given. We may not have all 5 options for every question but up to 5 options will be given and you have to take all that are applicable. Some of the questions can one correct option, you have to take them for example in this case you know this is just a sample one, it does not mean that today's quiz will have these as the solution. So, there is a for loop in C plus plus where the different place holders have been filled up with x, y, z and w and you are required to tell us which of the following statements is correct. We are not asking for the correct ones, we are asking for the correct ones, the option A is x, y and z may be empty but w cannot be, B is all of them may be empty and C says if y is not empty then x and z cannot be empty and D is none of the above. If you have seen the video lectures it should be very straight forward. So, we will give you a minute and after that we will move to the next question. Now we move to the next question which of the following is a C plus plus expression and more than one answer may be correct. The first option is x is assigned y plus z then it is x plus plus, it is while true x plus plus semicolon and break semicolon. So, we move to the next question, the precedence of assign as an operator is which of the following and more than one may be correct, same as that of plus and minus less than that of plus and minus more than that of star and slash multiplication and division and less than that of logical and logical law. Once again these are not meant to be tricky questions, these are straight from the video lectures. If you have just seen the video lectures carefully you should be able to answer them. It is just to figure out whether you are actually watching the videos, let us go to the next one. It is about the continue statement in a for loop, what does it do? It specifies that the loop must execute infinitely, causes the next loop iteration to start, causes the program to terminate immediately, causes the loop to exit immediately. So, we move to the next question, consider this for loop and which of the following are correct.  We move to the last question, specifying loop invariance as comments serves which of the following purposes, helps the compiler optimize the loop, helps us reason about the loop's correctness, helps the compiler ignore errors in the loop, helps the computer skip executing the loop. So what we will do now is, you know I hope all of you have answered the questions correctly, if you have seen the video lectures it should have been very easy. What we will do now is, we will quickly go through some of the important slides from lectures 23, 24, 25 based on which the current quiz was and then we will look at problems. So if you have seen the lectures, you would have already seen that the assignment operator, assignment can also be viewed as an operator, not only as a statement. For example, when we write something like x is assigned y plus z, if you put a semicolon at the end of it, this is a statement, it computes the value of y plus z, y plus z is an expression, it computes the value of y plus z assigns it to x and without the semicolon this will be viewed as an expression, where the assigned symbol is treated as an operator just like plus is an operator here. And what does this expression do? The type and value of this expression are the same as the type and value of the part to the right hand side of the assigns operator and when you evaluate such an expression with an assignment operator, there is a side effect, the side effect is that the value of this expression gets stored in the variable x. So with the assignment symbol, not only can you write assignment statements, but you can also write assignment expressions as a side effect of which you get the actual assignment of a value to a variable. So this was there in the video lectures. So for example, in a for statement, if I say count is assigned 1.0 here and count is assigned count plus 1 here, these are really assignment expressions with side effects. You could put other expressions also there, that is fine, but if you put these expressions and there are those side effects that something is getting initialized, something is being updated at the end of the iteration. This expression will be evaluated once before you enter the loop. This expression will be evaluated at the end of every iteration of the loop and if evaluating the expression has a side effect, then the side effect will also happen at the end of every iterate. And then we looked at some special assignment operators, the post increment operator which is x plus plus. So this is an expression, what is the type and value that it has? It has the same type as x and the value it has is the same as that of x before it is incremented, but it has a side effect and the side effect is that the value of x will actually be incremented. So the value of the expression x plus plus is the value of x before incrementing. Evaluate the section, it has a side effect which is that the value of x will actually get incremented. And if you have this y assigned x plus plus semicolon, so this is an assignment statement on the right hand side is the expression x plus plus and suppose we say that the value of y prior to execution of the statement is 10, the value of x prior to execution of the statement is 2, then what will be the values of y and x after the statement executes? So y will get assigned the value of the expression x plus plus, what is the value of the expression x plus plus? It is the value of x before incrementing, what is the value of x before incrementing that is 2. So y will get assigned the value 2, but in evaluating the expression x plus plus you would end up incrementing x, so the value of x after the statement would be 3, is that clear? And similarly you have the pre increment operator where you put the plus plus before the variable or the expression and this also increments the side effect it increments the value of x, but the value of this expression with the pre increment operator is the value of x after incrementing as opposed to the previous one which was the value of x before incrementing. So if you have y is assigned plus plus x semicolon, this is an assignment statement, the expression on the right hand side is plus plus x, if the value of y and x are 10 and 2 before that statement is executed, then when that statement is executed the expression plus plus x is evaluated, what is the value of the expression plus plus x, it is the value of x after incrementing, so that is 3. And what is the value of and what happens when you evaluate this expression is the side effect x is incremented, so x also gets the value of 3, is that clear? And then there are some compound assignment statements which you can think of as shorthands, so when we write x plus equals y plus z, it really means x is assigned x plus y plus z. So whatever comes to the right hand side of this plus equals is what is to be added to the current value of x and the result has to be loaded back into x, it has to be stored back into x. And similarly for the other operators minus equals star equals divide equals remainder equals, so x percent equals 5 means that x will be assigned the value of x percent 5, remainder of x on dividing by 5, so that is straight forward. And then there was an entire video lecture the last one lecture 25 on how to reason about loops, so while we believe that you should know that how to reason about loops, if you are not understanding that immediately right away that is fine you can come and revisit that later. As you write more and more complicated programs you will begin to appreciate the importance of that lecture, when you write a loop you must first be clear in your head what is it that you want that loop to do, so that is captured by preconditions and post condition, precondition is the relation between variables before the loop starts iterating, post condition is the relation between variables after the loop has completed its all its iterations and the loop is basically incrementally changing the relation between variables from what it is in the precondition to what it is in the post condition. And the loop invariant is a relation that holds every time the loop iterates, so in the video lecture we had actually worked out an example where we had shown what the precondition, post condition loop invariant might look like, so precondition and post condition can be seen as special cases of the loop invariant, loop invariant holds at all points whenever you reach whenever you begin an iteration of the loop the loop invariant holds at that point and in order to ensure you know when you write a complicated program and you have a loop there and you have some complex loop condition you want to make sure that the loop actually terminates otherwise it might you know it might be a non-terminating or infinite loop. So, it is desirable to have some integer valued metric typically an expression on the variables of the program which monotonically changes towards a fixed value. So, for example, a counter decrementing from n to 0 or a counter incrementing from 0 to n. So, it is monotonically changing in each iteration of the loop towards a fixed value and this metric which changes in each iteration of the loop and eventually reaches the fixed value is also called a loop variant and this is useful to argue that your loop is actually going to terminate. So, are there any doubts on the video lectures? So, what is not clear can you tell us? So, when you write a loop, so I mean right now we are going to do that we are going to give you some practice problems and we will say write a program with loop which does it. So, how do you go about doing that? You know if I let us say so to take an analogy right I mean if I say that let us go from here to let us say you know Srinagar. Do you just say let me jump onto the road and start walking and then I will figure out how to reach Srinagar. You do not do that right you sort of plan it out beforehand that well maybe I will go from here to here through train and the train will take me from here to here from there to there I will go by bus the rest I will go walking or whatever I will take a boule of cart or something. So, you actually plan out things when you have a certain objective to do you do not just jump onto the road and say let us start walking wherever my eyes can see and finally I will figure out how to reach Srinagar. So, similarly a programming is a similar task if I ask you to solve a problem and if you are trying to solve it through an iteration construct you have to plan it out what is it that you want that loop to do what should be the purpose of that loop why are you putting that loop in there right and the precondition is saying this is the relation that existed between the program variables before the loop the post condition is saying I want this relation to hold after the loop executes. So, that is the precondition and post condition at a very high level it is some relation on the post condition is really what you want to achieve by the loop the precondition is from where you are starting right it is like saying my precondition is I am standing in IIT Bombay in Powai my post condition is that I should be standing in the center of Srinagar and then in between what do I do. So, what I am saying is this is needed in order to plan your program when you write a program you should know what is it that your loop should do from where to where should it take you. So, it should take you from the precondition which is some relation between the variables to the post condition which is again some other relation the desired relation between the variables at the end of the loop iteration is that does that help and then how do you do that you know one could say let me you know take a leap of faith from here and let me just jump and I will land up in Srinagar that is a one step thing right, but alternatively what you could say is that I will do this and then I will do that and then I will do that. So, loop is basically trying to do that right it is saying I will do it in multiple steps, but in each step I will do some action. So, is that when I put everything together I reach my whatever you know I reach the desired goal. So, loop invariant is saying that as you are taking the steps are you sure that you are actually trying to go from where you wanted to go from your you know starting point to your ending point. So, loop invariant is a relation that holds between the variables every time you start iterating the loop every time you say I am going to take a step it should be an invariant that for example, you know the you could say that the distance from IIT Bombay to Srinagar should be the sum of the distance from IIT Bombay to wherever you are standing plus the distance from wherever you are trying standing to Srinagar. The shortest distance from IIT Bombay to Srinagar should be the sum of the distance that you have already covered in going from IIT Bombay to wherever you are standing plus the shortest distance from there to Srinagar. So, that is the invariant that is the relation which you want to hold at every time you are trying to take the next step right. You do not want to go through a very long and circuitous route. So, you want the shortest distance from your source to your destination to be the sum of the distance that you have already covered and coming from the source to wherever you are plus the shortest distance from there to the destination right. So, loop invariant is something like that. It is a relation that holds every time you are trying to take a step. The first time you are trying to enter the loop, it is basically the precondition and the last time you went to the head of the loop and then you came out because the loop condition was violated that should be the post condition. Does that make sense right? So, as I am saying that you know as you look at more complicated programs you will begin to appreciate this much more, but even for simple programs I think it is very it is important to be clear in your mind what is it that you are doing with the loop? The loop is I mean do I want a loop which does nothing I mean why would I want to put that loop? There is no point putting that loop right. So, if I am trying to get the loop to do something useful let me be very clear about what is that useful task? What is the initial relation between variables? What is the final relation between variables and how am I progressing from the initial relation to the final relation? That is the loop invariant a special case of which is the precondition and the post condition and as you iterate through the loop you are maintaining that invariant, but you are moving from the precondition to the post condition and the loop variant is just saying that you want to make sure that this entire process terminates right that you do not go on forever. So, as long as in your loop there is a counter or something which is monotonically changing and you know that it can only change for only finitely many times then you know that the loop is only going to iterate finitely many times. So, now what we are going to do is we will start with the practice problems. So, this is our first practice problem. So, the question marks show up red here, but they show up black here. So, I guess you can see the question marks. So, this is a program fragment where we have three integer variables i j and n we read the value of n and then we have a for loop the three parts of the for loop are separated by semicolon right. So, it is ok. So, this is the first part i assigned 0 comma j assigned something that is the first part then the semicolon then there is the second part which should be the loop condition and then there is the third part which is what should be executed every time the loop iterates after the end of every iteration the expression there is going to be evaluated and the only statement you have in the loop body is printing out j and what do we want this little code fragment to do we wanted to output the first five powers of n whatever this n you have read in over here. So, n raise to 1 n raise to 2 n raise to 3 n raise to 4 n raise to 5. So, you have to fill in the missing parts. So, that this code outputs the first five powers of n is the question clear ok. So, for the next five minutes try to write down the answer in your notebook is not a very difficult problem, but you should know what the different constructs are. So, remember this part is executed just once this is the expression that is evaluated before you entered the loop just once this condition is checked every time you want to get into the body of the loop and execute it and this is also executed every time you have finished the body of the loop. So, this will be executed after this this will be evaluated before this and this whatever is over here will be evaluated just once before you entered the loop for the first time. Interestingly almost everybody has come up with a very similar looking solution. So, i is 0 j is 1 and then i less than or equal to 4 j is j star n and i i plus plus. So, is this correct? No why j equals to 1 is wrong. So, why is j equals to 1 wrong the first time. So, this statement is executed only the first time this expression is evaluated only. So, where is sahid? So, this statement is this expression is evaluated only the first time before you entered the loop after that this condition is checked and after that you execute this statement. So, when you evaluate this expression j gets assigned the value 1 then 1 is indeed less than or equal to whatever 0 is less than or equal to 4 and then you will print 1. So, regardless of what n you input you will print 1 and what is the fix for that n. So, that is one solution here is another one. So, does this work? i is oh wow. So, there are 1 2 3 semicolons here or maybe even 4 semicolons here this is not even going to compile must have only 2 semicolons there are 3 parts which are separated by semicolons. So, which one of them do you want to keep as a semicolon and which one of them, but you know in the original question I had a comma over here. So, you have changed that comma to a semicolon. So, you have to understand the difference between a comma and a semicolon right it is clearly explained in the video lectures. So, suppose this was a comma and let us say that was also a comma. So, would that be correct? Would that solution be correct? How many times would it iterate? It would iterate 6 times right it is less than or equal to 5. So, less than or equal to is written by a less than followed by an equal to in the program, but even if you wrote less than or equal to the right way this will iterate 6 times. So, it will print the 6 powers of n. So, that also seems to be an error let us look at this this is shantanu's copy j is assigned n i less than 5 j star equals n i plus plus is that correct? So, some kind of intrigues that all of I mean all that we required was that this loop should iterate 5 times right. So, i is 0 i plus plus i less than 5 is certainly one way of iterating the loop 5 times that is not the only way. For example, I could increment i by 2 and then check whether i is less than some 10 or something. So, this is not even a single solution in this class which looks like that. So, you know if you look back at the original question all we have done is we have initialized i with 0 and then we have required the loop to be iterated 5 times right, but they could be different ways of incrementing it and corresponding conditions to be checked and all of those would be correct as long as you iterate 5 times. So, in some of the you know whether you put less than 5 or less than or equal to 5 it does matter whether the exact number of iterations it will have. So, the T is could please distribute these copies. So, now we will go to the second program or the second problem. So, is everybody fine with this question right we just want the loop to iterate 5 times i is doing that job you can do it in one of several ways looks like everybody has incremented it by 1 and then check whether it is less than 5 and then the real action that happens with j is it has to be initialized to n over here and has to be multiplied with n in every iteration. So, now you can exchange your copies with your neighbors this is a simpler question and of course, in this case there is only one correct answer. So, what do you think gets printed out here? Sir 10. 10 and why do you think 10 gets printed out there? Sir x plus plus is a post increment operator. So, first it will give the output as 10 and then it will increment the value of x. And then the next one is y 1 minus minus y. Yes sir. So, it is a pre decrement operator. So, first it will decrease the value of y by 1 and then it will give the output. So, good. So, now let us hear about the other two from. So, does everybody agree with these two? So, who has got a different answer from this? So, all those differing pairs you agree with the first two. There you agree with the first two.  It prints 12. It prints 12. So, how many of you agree that this will print 12? Sir I got 11. You got 11. So, how did you get 11? Sir because x has value 10. Oh no no no it will be 12 it will be 12. It will be 12. Yeah x will become 11 and then y is 1. So, 11 plus 12. Okay. Sir x is 11 and y plus plus gives out 2. So, x is 11 and y plus plus will give 2. Y plus plus will give 2. Okay. Why should y plus plus give 2? Because the value of y is 1 and y plus plus is y equal to y. So, if you remember what is this? This is an expression y plus plus is an expression with side effects. If it is an expression it must have a value and a type and then it will have some side effects also. So, the value of this this is a post increment operator. So, the value of this expression is the value of y before the increment. The side effect of this expression is that y will be incremented. So, the value of this expression is the value of y before the increment. What is the value of y before the increment? It is the value of y after the previous decrement. So, therefore, although y will get incremented as a side effect but the value of the expression y plus plus is the value of y before the increment. So, this is important that the side effect and the value of the expression may not match in their values. So, the next question is this code fragment and you are required to figure out what will be output. So, it is very important when you write a piece of code at least small pieces of code to be able to sort of mentally executed or executed in your copies and to understand what will it do for some given values of the input. So, this is basically an exercise in that given this code fragment and we mentally run it or can we run it on our copies and find out what the output should be. So, here there are two integer variables num and i, num is already initialized to 0 while declaring i is not initialized and then there is a simple for loop this is the remainder on division by 2 is the continuous statement and then something is printed out. So, any disagreements any pair of students whose outputs disagree? 1, 4, 9, 16, 25, ok. So, let us just see, so i will go from the value of i changes from 0 to 9, i is 0 till i less than 10 and each time if I take the remainder with 2 then it will keep once it will be 1 the next time it will be 0 or even numbers the remainder is 0 the odd numbers remainder is 1. And if you look at the original problem if the remainder is 0 then you continue which means what what does continue do you just forget about whatever you are doing and go back and start the next iteration right and of course, before starting the next iteration you increment it and then you start the next iteration and otherwise for odd values of i, num plus equals i. So, is this clear what that does num plus equals i basically means i is added to num and the value is stored back in num ok. So, we had shown this earlier x plus equal to y plus z means x plus y plus z and it is assigned back to x. So, num plus equal to i what does it do? This is the same as saying num is assigned num plus i num plus equal to i just means this ok. So, if you keep adding the numbers then you will find that you get the squares of the first 5 numbers ok. So, initially so num is 0 to begin with. So, initially num is 0 and then when i is 1 num becomes 1 right then when i is 3 num becomes 1 plus 3 which is 4 and then when i is 5 num becomes 4 plus 5 which is 9 and so on is that clear right. So, this is just a matter of executing the program just following the instruction step by step ok you just start iterating. So, if i is 0 then 0 divided by 2 the remainder is 0. So, you continue.  So, you execute this right what is going to be printed here? The value of this entire expression this is an assignment expression the value of the assignment expression is the expression on the right hand side of equal ok. So, now this is the last problem. So, in the last class we actually saw how to compute the nth power of an integer using repeated squaring ok. So, we said that n squared is n times n n raise to 4 is n squared times n squared n raise to 8 is n raise to 4 times n raise to 4. So, basically the number of multiplications we were doing is log n base 2 calculate n raise to 8 you needed to do 3 multiplications n times n which was n squared n squared times n squared which was n raise to 4 and n raise to 4 times n raise to 4 which is n raise to 8. So, now the question is if m is not a power of 2 of course, I can always calculate m raise to n by multiplying m n times I can use whatever you know n minus 1 multiplication operators and get m raise to n. But if n is not a power of 2 we would like to compute m raise to n using not too many more than log n. So, maybe twice log n of course, log of n base 2 and all of that ceiling and all is fine. So, many multiplications. So, you are required to write a C plus plus program with loops to do this and here is a hint. So, suppose n is 13. So, as an unsigned integer I can represent it as 1 1 0 1. So, here is where your understanding of binary representations of integers actually comes of use. So, if it is 1 1 0 1 then m raise to n which is m raise to 13 in this case can be computed as m raise to 8 times m raise to 4 times m raise to 1 8 plus 4 plus 1 is 13. But why did I get this 8 plus 4 plus 1 that is exactly how 13 is represented in binary this is 8 this is 4 this is 1. So, because 13 is 8 plus 4 plus 1. So, when you write something in binary of course, you are adding up different powers of 2 to get the final number. So, whatever you are adding up is a power of 2 and if something is a power of 2 we have already seen how to calculate m raise to that power using just. So, if I ask you to calculate m raise to 13 you should first calculate m raise to 8 m raise to 4 m raise to 1 and then just multiply them m raise to 8 can itself be calculated using 4 you must have calculated n root to calculate m raise to 8 and m raise to 1 you must have calculated n root when calculating m raise to 4 and then you just multiply them together. So, we want you to write a C plus plus program using. So, you know if you cannot get it in 2 times log n it is fine if you can get it in 3 times log n 4 times log n it is fine, but some linear multiple of log n it should not be n or n minus 1 and I hope you see that this makes a huge difference. So, suppose if n was 1000 then log 1000 base 2 is something like 10. So, doing 10 multiplications or even 20 or 30 multiplications is far less than doing 1000 multiplications. So, this is basically a smarter way to calculate the exponent m raise to n the exponentiation and you are I think from what you have learnt so far you should be able to write a C plus plus program with loops to do this. So, I request all of you to write that down in your notebooks. So, the question is that we want to calculate m raise to n. So, you will read m as an integer n as an integer and I want to calculate m raise to n. Now, in the last class what we saw is that if n was a power of 2 we could do this in a smart way by using only log n multiplications basically you repeatedly square it. So, now we want to do this when n is not necessarily a power of 2. So, basically the problem is that write a C plus plus program with loops to calculate m raise to n in which the number of multiplication operations you are using the number of times you will have to actually use multiplication is some you know I mean if you do not get it in 2 times log n it is fine 3 times log n 4 times log n, but it is some constant times log n it should not be n minus 1 n and log n are very different right 1 is exponential. So, that is what we want you to do and here is I guess you can see how it at least in your mind you can see how this can be done basically take n think of it as a binary number and you are really adding powers of 2 to get that number for each such power of 2 you know how to get m raise to that power in an efficient way and then adding numbers in the exponent is equivalent to multiplying those corresponding numbers m raise to 8 plus 4 is m raise to 8 times m raise to 4. So, let us say that n is 33. So, we know that 2 raise to 5 is 32 and 2 raise to 6 is 64. So, log n base 2 will be 5 point something. So, what is the ceiling of log n base 2 that will be 6. So, what is 2 times ceiling of log n base 2 is 2 times 6 it is 12 right. So, basically what we are asking is if you have to calculate m raise to n in this case n is 33. So, basically if you have to calculate m raise to 33 write a program which calculates m raise to 33 using at most 12 multiplications right. The simple way to do it is to keep multiplying m and. So, you will need 32 multiplications right m square can be calculated using 1 multiplication m cube using 2 multiplications. So, here raise to 33 can certainly be calculated using 32 multiplications, but we want you to get using only 12 multiplications. Is the problem clear? We are basically trying to optimize on the number of multiplications because multiplication is actually an expensive operation on a computer takes time takes power. So, if I can have an efficient way of calculating exponents that is good. Has anybody come up with the solution? So, Rudrajit basically reading in m and n that is fine while a is greater than 0 a is initialized to n over there and while a is greater than 0 r is the remainder of a divided by 2 a is divided by 2. So, what is this loop computing? Rudrajit so while a is greater than 0. So, this will basically I think end up computing the most significant bit or something right. Oh you are just calculating how many number of bits by using this s plus. So, you know I mean I guess this is a very good example you write a loop like this and then Rudrajit and I are trying to understand what this loop does. I mean if there is a if there are comments if there are preconditions post conditions it will become very clear and we can also go and check whether all of that is correctly being done right. So, when you write a loop to do something put those comments in it helps you also as you write the program it helps somebody else to understand ok. So, basically he has used this loop to calculate the number of bits in the binary representation of n and then while n is greater than 0 you are just calculating the bits is it? C is m. So, this is where the repeated squaring is happening and you are repeatedly squaring it for the number of bits I can see that ok. So, there is a while loop here and within the while loop there is a for loop. So, what is the while loop doing? So, there is some nice logic that he has used here, but the way it has been written it becomes difficult to read. So, please you know when you write program put comments I think your program is correct, but you know I have not checked every detail. I can also see something interesting over here that Rudrajit has actually tried out some input examples and I think this is very important you should do this. When you write a loop work it out by your hand to make sure that it is really calculating what it is supposed to do and then and only then can we figure out. So, here is a you know interesting piece of program with one while loop at the top that calculates the number of bits in n and there is another while loop at the bottom with a for loop inside that, but you know I think while you have followed the spirit of the problem, but it looks like every time you will every time in this loop you will start with m and you will go and multiply this for the example I showed which was 13. So, in 13 it has to compute m raise to 8 it has to compute m raise to 4. So, it looks like your first computing m raise to 8 and then a fresh computing m raise to 4. So, but you know you need not have done that in computing m raise to 8 you have already computed m raise to 4 when you do this repeated squaring. So, what you might have ended up doing is that I think in your case the number of multiplications can probably go as much as log n times log n. So, I mean while the idea is interesting, but I am not sure if you can do it in a constant times log n because you are recalculating things that you have already calculated right m raise to 8 and m raise to 4 you are recalculating m raise to 4 again you are already calculated that when you calculate m raise to 8. So, ok so in the interest of time what we will do is. So, please complete this problem on your own try it out in your lab sessions and then we will discuss some solutions in the next class and try to keep in mind that we are trying to minimize the number of multiplications.