Quiz 3 - Frequently Asked Questions

Style and Format of the Quiz

Logistics

The quiz will be take-home style, and will be released on Tuesday 11/10, 4:45 PM Eastern Time. You will have 75 minutes to complete the quiz with and turn it in by 6:00 PM Eastern Time with a 10 minute grace period for scanning and uploading your diagrams.

International students who opted into the 4:45 AM Eastern Time quizzing will begin theirs via the INTL Gradescope account at 08:45 GMT 11/11 and will similarly have 75 minutes, until 10:00 GMT, with a 10 minute grace period.

The format of this quiz will be similar to what you can expect on the final and should serve as good practice for it. The focus will be on conceptual questions and diagramming, rather than code-writing.

You will need to have some sort of app to take pictures of your diagram to upload to Gradescope.

What topics should I know for the quiz?

  • Anything previously covered
    • Lists and Dicts can reappear on this, now that we know that they can be used as attributes in classes
    • OOP covered on the last quiz will definitely help understand the more advanced concepts we went into
    • Everything we learned so far about memory diagrams will still be crucial as this quiz covers advanced memory diagrams
  • Classes and Objects - New Topics
    • Constructors / __init__
    • Methods
    • The self parameter
  • Recursion Concepts
    • This will also include knowledge on recognizing a Node and how to track examples of these “linked lists.”
      • Note: There won’t be any code writing related to recursion. Just know the concepts well enough to interpret them on the memory diagram questions!
  • Memory Diagrams - New Topics
    • Drawing frames for class constructors
    • Drawing frames for class methods
    • How to track recursion

Classes and Objects - New

Constructors

Before the quiz, we got a brief overview of classes and objects, only knowing that they have can attributes of different types. However, there is so much more to a class than its attributes!

Notice how we declared classes before:

We have a default value even declared for is_graduating. However, if we wanted to change this attribute’s value, or make sure that name and gpa have values, we have to assign them like so:

This seems easy right? However, what if I had multiple students?

This can get very annoying with many, many objects. For every new Student we declare, we need 3 lines of code just to set its attributes.

What if there was a way to initialize these objects’ attributes in one line? Even better, what if we initialize them in the same line the object is constructed?

This is where constructors come to the rescue! Constructors are defined with the __init__ name in Python and no return type is specified. In addition, a self parameter is defined.

What is self? It is a parameter used by class constructors and methods (which we will talk about later) that is used to refer to the specific object of its class. When calling constructors and methods, we NEVER pass in an argument for this self parameter.

Let’s look an example that simplifies our way of doing things above:

One thing to note is that self does NOT have a type declared. It is already implied that the object in question is of the class type it is currently in, so it does not need a type.

Another thing is that we have two names in this that we need to be concerned about. The reason why this is allowed though is because self.name and name are completely separate. self.name refers to the object’s name property, while name refers to the parameter that is passed in.

We also have our default value for is_graduating moved to our constructor as it is essentially doing the same as before. In this case, we decided not to have another parameter by choice, and this could be the case in the problems he asks on the quiz. Do not assume that any attribute will have a parameter passed into the constructor, unless explicitly said in the instructions.

Now let’s actually use this constructor for our three students:

Look at how much code this saves! A few things to note is that we didn’t have to make any reference to __init__ when using the constructor. We actually just use the same syntax as we did when we didn’t have a constructor, but this time we have formal parameters.

What do we mean by formal parameters? Well we did have self declared as our first ‘parameter’ in __init__, but this is not a formal parameter that a call to the constructor (or methods as we will see) would require. This is because it is alrady implied which object you’re using as self, the one you’re creating or one that you called a method on.

But it looks very similar to what we had last time, but this time less lines of code and we are actually filling the parentheses after the class name. With empty parenthesis, there is an implied constructor of:

But as you can see, the __init__ here is entirely useless in this case so Python allows us to not have to write it unless we need it.

Methods

Before, we have just been initializing and assigning attributes. However, objects can do so much more than this!

Think about it like this: if we were to represent a car as a class, it is not sufficient just to have describe a car with its color, make, model, year, mileage, etc.

These are all characteristics of the car. But if we wanted the car to actually do something. Like drive? Or get repainted? We can represent these actions through class methods!

Using the Student example from before, in the event a student’s just finished a class or even declared graduation, we can have a method that can reflect that change, rather than manually manipulating the attributes in main.

We can see that the method here, add_class_grade, can be useful if a Student needed their GPA updated following a class they took. From main, a call to update this would look like:

Notice how we only needed to pass in the letter grade, and the method does the rest of the work for us! We do not need to pass in anything for self, only the formal parameter of grade is needed.

This is by the way a terrible way to update your current GPA. But the point is, for manipulating the state of Student objects, methods are really useful!

Methods can also return a value! Let’s say we want to print a student’s status, but we want a method to do the work for us so we can just call that method for multiple objects:

In get_status, we have no formal parameters, and therefore it only has self as a parameter. However, we do have a return value here!

If we call this on all students, we can easily get the statii of all students we have. If we had a List of Student objects, we can easily iterate through that List and print the statii.

If you test this code above in a main function, you will see that the following will get printed:

Jason has a GPA of 3.42 and is not graduating.
                Julia has a GPA of 3.83 and is not graduating.
                JJ has a GPA of 3.53 and is not graduating.

This is the power of using methods, and we will delve into how to diagram all this code above in a later section!

Recursion Concepts

Although the quiz will only require you to trace through code with recursive functions, it still important to know how to recognize it, and what things to look out for when following the program.

Recursion is when a function calls itself at some point in its code.

We see above that in the else case, the factorial function will call itself, passing x - 1 as the parameter. This is what we call the recursive case.

In any recursive function, it is crucial that any call made to the function can eventually reach an end, or a base case.

For example, if we have this:

We expect 2 factorial to be 2, but this is what happens:

factorial(2) is called, so we need to evaluate it
                It returns 2 * factorial(2 - 1)
                Now we must evaluate factorial(1)
                It returns 1 * factorial(1 - 1)
                Now we must evaluate factorial(0)
                It returns 0 * factorial(0 - 1)
                Now we must evaluate factorial(-1)
                It returns -1 * factorial(-1 - 1)
                Now we must evaluate factorial(-2)
                ....

This will keep going and going until the stack is overflowed (if we think about the memory diagram for this, the stack will be infinitely long).

This is why a base case is necessary.

Now this should work, right?

Let’s try factorial(2) again:

factorial(2) is called, so we need to evaluate it
                It returns 2 * factorial(2)
                Now we must evaluate factorial(2)
                It returns 2 * factorial(2)
                Now we must evaluate factorial(2)
                It returns 2 * factorial(2)
                Now we must evaluate factorial(2)
                ....

Well the base case clearly didn’t help. Looks like getting rid of the minus 1 for fun didn’t work. Not only does a recursive function need a base case, but it will need to make progress towards the base case.

The minus 1 we had before allowed us to make progress towards reaching our base case so our program can finally return.

Let’s go back to what we originally had:

factorial(4) is called, so we need to evaluate it
                1. It returns 4 * factorial(4 - 1)
                Now we must evaluate factorial(3)
                2. It returns 3 * factorial(3 - 1)
                Now we must evaluate factorial(2)
                3. It returns 2 * factorial(2 - 1)
                Now we must evaluate factorial(1)
                4. With the base case of 1 being <= 1, we return 1
                Now we process backwards, starting with step 3
                Return 2 * 1 = 2
                Going back to step 2
                Return 3 * 2 = 6
                Going back to step 3
                Return 4 * 6 = 24

Recursion can be powerful, but confusing when we trace through it without a memory diagram. Later we will go over how to draw a memory diagram for this.

To quickly go over linked lists, known as Nodes, it is best understood as a class that has an attribute referencing itself:

This is very similar to how function can call itself, so this is why we call Nodes a recursive data type.

The data attribute is the data it contains, where as next is really a pointer to another node.

These linked lists are very powerful with recursive functions, which we will see here and when we trace through a memory diagram.

Here, we continue down the list by recursively calling product on the next node of the list. We will go over how this looks on a memory diagram later.

Memory Diagrams - New

From before the last quiz, you all have a basic understanding of memory diagrams and tracing through a program with a couple of function calls. You all even had problems where Dicts were involved, and you saw your first objects on the quiz!

However, with our new understanding of classes having constructors and objects, we have some new things to add to our environment diagrams.

Here are some key tips to success with memory diagrams. If you take ANYTHING from this review doc, I would say this is the part to pay the most attention to in order to avoid silly mistakes:

  1. Draw your globals frame and ALL classes and functions declared, including main. The only things you don’t indicate from the program onto your diagram are the imports, and the if block for calling main(). Everything else in some way will be indicated on your diagram as part of your globals.

  2. Every frame except for globals NEEDS a return value and return address indicated. Do NOT lose points just because you forget to do this.
    1. The main frame will always have a null return value, which you can just draw a circle with a line through.
    2. For every function call that happens, once you draw the frame, write the line number of the function call (not the definition) as the return address on that frame.
  3. Every time a new object is created, check to see if its defined class has a defined __init__, also known as the constructor. If so, you must add a frame on the stack for this, titled <CLASS_NAME>#__init__ . Same notation applies for method calls: <CLASS_NAME>#<method_name>.
    1. Basically, if you’re not writing hashtags when calling class constructors/methods, you’re doing something wrong :)

  4. On EVERY frame that has a hashtag, i.e. every frame with something#__init__ or something#<method_name>, DO NOT forget to put the self parameter. I cannot stress enough that this is super important. Just like any function parameter name gets written down on its frame, the self parameter, although an argument isn’t passed in, should get written in the frame and point to the object that is being created/called upon.

  5. In any frame that’s created for the constructor, i.e. any frame that is named something#__init__, the return value will point to the SAME object as self. Golden rule: In all __init__ frames in a memory diagram, RV will point to the same object as self. This should make sense as a constructor creates a new object, which ends up being what self refers to as well.

  6. In recursive calls, DO NOT rewrite values in the same frame. Draw a BRAND NEW frame for every recursive call that’s made.

I review in videos how to trace through the examples from above in a memory diagram. This includes the example with Student, the example with factorial, and the example with product with Node.

Here is the example with Student. Here is the example with factorial Here is the example with product.

Important Note regarding For… in loops in Memory Diagrams

Something extremely important to understand about for in loops is that when we define the counter variable within the for statement, that also gets defined on the memory diagram even though no type is explictly declared. Please make sure that on the quiz, that whenever we have something like:

Make sure you also define x on the frame and update that on your diagram as you go through each item on the list. Just like how you would declare a variable i whenever we have a while loop, you do the same for the variable declared in the for .. in statement.

Another note is that when we use the actual item versus the index in our for in loop, i.e.:

versus

On the heap, the first set of code (where x represents the item on the list) nothing should change on the heap! This is because we define x itself to be each item on that list, and therefore doing x = x + 1 would only affect the x variable in the diagram. The variable x will not always be a direct reference to the item on the list itself. Remember, strings, ints, floats, and bools are not reference types, so a List of these variable types would mean that a for loop directly accessing each of these elements would not be a reference. Again, this is why only x in the first example changes, not the actual element on the xs list.

On the other hand, if we used index accessing like we do in the second set of code, that will change the element on the heap List, since we are directly referring to the list xs when using the bracket notation.

How do I best prepare for the quiz?

  1. For the memory diagrams, definitely work on the practice problems we assign, but also look back at problems done in lecture to ensure you understand the concepts.
  2. To emphasize again about memory diagrams, it is super important to go line by line, starting from the call to main. Try to understand when we make a new frame, when we draw an object on the heap, when we draw arrows, etc.
  3. Tracing through recursive examples from class and the exercises would be a great thing to do as we only just started talking about them.
  4. Look at your current project and try to really study the concepts you learn from it, such as using self, calling other methods, using other class objects within a class, etc.
  5. TA’s are here to help in office hours, please feel free to go through practice problems with them, they will be glad to walk you through understanding these concepts!