Style and Format of the Quiz

Will this be Synchronous or Asynchronous and how much time will I have?

The quiz will of a take-home style, just like last time. It will be released on Tuesday 10/20, 4:45 PM Eastern Time and be due at midnight, Tuesday 10/20, 11:59 PM Eastern Time.

International students who opted into the 4:45 AM Eastern Time quizzing will begin theirs via the INTL Gradescope account at 08:45 GMT 10/21/2020 and submit by 4:00 PM GMT.

On this quiz we will have certain parts due by different times. The memory diagram questions will be due about an hour or so after the quiz opens up, while you will have the rest of the night to finish the code writing.

Am I allowed to use notes, VS Code, and/or the Internet?

Yes to notes, anything on the course site, and VS Code… you are encouraged to try things out in the REPL!

No to using the Internet. While you may think there is no way for us to check whether the Internet was used, it is obvious to tell what methods to program coding were taught in class versus something that was pulled from the Internet. Using obscure methods from the Internet either way will probably get points taken off anyway for not following the conventions we use in class.

And NO to collaboration with other students. As you saw, it is very easy to tell when someone has just changed variable names or move small things around.

Will I need to hand-write anything?

Memory diagrams will be on this quiz, meaning you will have to have some sort of app to take pictures of your diagram to upload to gradescope.

What new topics should I know for the quiz?

• Always good to refresh quick on what we previously covered for last quiz (see FAQ for quizzes 0 and 1!)
• Memory Diagrams
  • For lists
  • For objects
  • For dictionaries
• Dictionaries
• Classes and Objects
  • Note: There won’t be any code writing relating to classes and objects. Just know the concepts well enough to interpret them on the memory diagram questions!

What is the breakdown of question styles?

There will be some questions that are similar to the previous quizzes in that they will ask you to implement some sort of function following the requirements given.

In addition to this though, a big focus will be on creating memory diagrams! The bright side of these is that you will not have to worry about writing code, rather you will be given a code snippet and will have to interpret what’s happening, which the diagram should actually help with! There also may be questions about your memory diagram, such as “How many objects are on the heap?” or “What is the value of x in the main frame?”. This is just a matter of interpreting what you drew!

Memory diagrams

Memory diagrams can be a blessing in the sky if you are trying to interpret programs or even trying to test your own! They are an effective way to essentially keep track of what variable values are as the program runs. With many function calls, it can be complicated to track things like lists and objects in your head.

The setup will always be the same. You will have three sections:

• Call Stack
• Heap
• Output

The call stack is where the globals frame will go, along with frames representing any function call that gets made.

The heap is where functions, lists, objects, and dictionaries would go. Any variable that is ‘primitive’ or simple like strings, integers, floats, or booleans will not need to go on the heap, and can instead be written in the small box within the frame.

Output is where printed output gets logged. Only use this section if you see print statements encountered.

Here is how drawing it will start off like (every time!):

Next, we will put functions declared in the program on the heap. Let’s take this:

Main is declared from lines 3-8 and foo is declared from lines 11-14. Let’s put this in our global frame:

Then, whenever any function call is made, we add that to our call stack. The number of times a function is called in the running of the program is the amount of frames that should be drawn on the stack. This does NOT mean you count every call that exists in the code, you have to actually check if those calls are reached when the program runs.

main() is called on line 18, so we will make a frame for this.

One thing to note is that every frame (except for globals) must have a return address and return value declared. Do NOT forget to include these!! Easy points can be given by having the return address and values correct on the frame. Since main was called on line 18, the return address will be marked as 18. As main’s return type is None, we will use a 0 with a slash marked through (which you should do any time a function’s return type is None).

Now time to actually run through the main function! In line 4, we have printed output, and in line 5, an int, x, is declared and initialized. We will put the output under the ‘Output’ column and put x in main’s frame. The variable x can now be accessed within the main frame.

For the string variable, y, that is declared on line 6, we have a function call to foo whose return value is assigned to it, so we have to create a new frame on the stack to account for this! On this new ‘foo’ frame, we can define the return address as 6 since that is where the call to foo is made. We will leave the return value as blank since we know it will return a string by the end of the call.

We can also go ahead and define any parameters within the frame, as they are all local to the function call (you will learn more about this when we discuss scope!) This applies to all functions you may encounter - even though the variables are not declared within the actual block, parameter values are still important to keep track of. Since the argument ‘x’ was passed into this function, we will write in its value 1 as the parameter value within foo, also named ‘x’.

Keep in mind, the x in foo is TOTALLY separate from the one in main. But you might wonder, we passed in the x variable from main as the argument, and therefore the x in foo and x in main have to be related. However, think of it this way, I could have defined the parameter within foo as y. The values of x and y will be the same at the start, but they have no relation at all because whatever changes happen to the parameter in foo will NOT reflect in the variable in main, since we are only dealing with an integer.

As you see in examples with lists, dicts, and objects, this does NOT hold true for those types because those are reference types. When they are passed into functions, a copy of them is not made, but instead, an arrow is drawn to it, meaning the parameter and variable from main would actually be related! Any changes that happen within these will affect all variables that reference it.

In our example though, when the integer gets updated, this change is only made in foo.

Now we have a list to declare on line 13! Now we will create a list on the heap to represent this, and we will draw an arrow from ‘values’ to reflect that it references that list.

The next line is a return statement that returns the value at index ‘x’ from the values list. We know from the diagram that x is 2, and following the values list reference, we know that the value at this index is “it”. This string will now be our return value!

Now we can get out of this frame since we have a return value. This will get assigned to the variable y in main. From there, the value will be printed and so will “End!” to mark the end of the program. Here is what our complete diagram looks like now:

This is a very basic example for review of how a memory diagram is made, but please refer to class notes and practice problems under Resources for more difficult practice!

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:

for x in xs:
                    x = x + 1

That we 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.:

for x in xs:
                    x = x + 1

versus

for i in range(len(xs)):
                    xs[i] = xs[i] + 1

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.

Dictionaries (Dicts)

Think back to when we talked about lists. It was a sequence of values of the same type. How do we access elements within a list? Easy! You just use bracket notation and fill it with the appropriate index. Remember, these indices start from 0 and count up from there.

However, these indices are not something we see when we, for example, print the list. We just know that the value in the second position for example is at index 1, and this holds true for values in a list that whatever is in the nth position is at index n - 1. We can see the limitations however of using indices to refer to values of a sequence:

The index (an integer) does not have any actual significance or relation to the value it represents other than where that value is on the list. It is not practical to remember at which position something on a list exists. If the scores for a class were listed, and we wanted Anna’s grade, we would have to know which position Anna was (in which case we would have to access another list for class names, which we do not even know if the order corresponds with the grades).

grades: list[float] = [ 62.5, 97.8, 83.4 ]
                names: list[str] = [ ‘Kush’, ‘Anna’, ‘Marc’ ] # Here we assume the order corresponds
                
                index: int = -1
                for i in range(len(names)):
                    if names[i] == ‘Anna’:
                        index = i
                
                print(“Anna’s grade is “ + str(grades[index]))

Dictionaries fix both of these problems!!! With the power of ‘keys’, values in a sequence actually have a meaning visibly associated with it that can be utilized within brackets:

grades: Dict[str, float] = {
                    “Kush”: 62.5,
                    “Anna”: 97.8,
                    “Marc”: 83.4
                }
                
                print(“Anna’s grade is “ + str(grades[‘Anna’]))

Notice how easy it is to just refer to the grades dictionary and look for Anna’s grade by using “Anna” as the key! This is the power of dictionaries!

Some trivial things to remember include how to import them and how to declare its type.

import Dict from typing 
                
                grades: Dict[str, float] # First type represents the key type, second type represents the value type

One other really cool thing about dictionaries is that adding values to them is very simple! No need to use special functions like append, all we do is just assign a value to a key that doesn’t exist, and Python is chill with it!

grades[‘Kaki’] = 110.0

If you want to remove a value from a dictionary, use the .pop() method!

grades.pop(‘Kush’) # Removes the {“Kush”: 62.5} pair from the dictionary

If you want to check if a key is already in the dictionary, instead of having to use a for loop to find and compare, there is a very simple syntax to check!

if “Marc” in grades:
                    print(“Marc’s grade is in!”)

Please do not waste time and run a for loop to find if a key exists!! Use if <key> in <dict> like we did above!

For loops will be useful, however, for finding values. In general, if a function takes in a dictionary, your first thought should be to make a for loop (just like we did with lists) to iterate through the key-value pairs. The for … in syntax is very similar for dictionaries, but instead of the item representing an index or an actual value, the item will represent the key!

for key in grades:
                    print(key + “‘s grade is “ + str(grades[key]))

Classes and Objects

One limitation about lists and dicts are that the data within have to be all of the same type, which is whatever is specified upon declaration. What if we wanted to hold data of different types?

This is where classes can be very useful! You creating a class essentially is equivalent to you creating a custom data type! The class can hold whatever attributes you want. To define a class with its attributes:

class [className]:
                    [atrr_1_name]: [attr_1_type] = [optional default_value]
                    [attr_2_name]: [attr_2_type] = [optional default_value]
                    [attr_3_name]: [attr_3_type] = [optional default_value]

An example would be if I wanted to hold data for a student. A student has a name, GPA, and could have a value to represent whether or not they are graduating soon. I can define a Student class to hold these attributes:

class Student:
                    name: str
                    gpa: float
                    is_graduating: bool = False

Notice how I can give a Student a default value for is_graduating if I wanted to!

Now that I have a class declared, I can use it to declare many objects of that class type, each to represent a student!

student_1: Student = Student()
                student_2: Student = Student()
                student_3: Student = Student()

You are not required to know this now, but we can even make lists of these objects! Exciting!!! You will learn more in future lectures!

The next step is to actually assign values to the attributes of the objects we have created. The way to assign and access attribute values is by using dot notation:

student_1.name = "Bob"
                student_1.gpa = 3.2
                student_1.is_graduating = False

A key thing to note is that these objects are reference types. What does that mean? On an memory diagram, this object would go on the heap as we learned earlier. If an object were declared and assigned to a variable, an arrow from that variable name to the object name would be created, so that name references that object. Therefore, if I had something like this:

student_4: Student = student_1

The name student_4 points to, or refers to, the same object as student_1. Thus, any changes that happen to student_4 will also reflect in student_1:

student_4.gpa = 4.0
                print(student_1.gpa) # prints 4.0, not 3.2

Objects being a reference type also implies that if one were to directly pass in an object as an argument to a function, the parameter name in the memory would point to that same object being passed in (a copy is not made).

Again, for the quiz you will just have to be able to recognize the syntax and track the object and its attributes in a memory diagram, so do not spend too much time memorizing the syntax. Just understand how to recognize when an attribute of an object is being accessed or updated, and how overall references work when multiple names are pointing to the same object (the concept is the same in lists and dicts).

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. Focus on these the most since we have not done quizzes or exercises involving memory diagrams yet so you want to get comfortable knowing how to draw them!
3. Really understand how to iterate through dictionaries and how to access values within them. Good practice is available under resources! Also review the Shakespeare exercise and project for this!
4. For classes and objects, as we’ve just talked about them and haven’t had much in terms of practice with those, try to focus on those the most.
5. We are 5 weeks away from the end of the semester! We are almost there! Pat yourself on the back for making it this far, you all should be really proud of yourselves! It is not easy to take on a skill as novel as programming! You all challenged yourselves by sticking through this course, and no grade can tell you otherwise. That being said, stress less about the grade you will potentially make on this quiz, and focus more on reviewing concepts that you feel you may be struggling with.
6. 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!