CS final review notes PDF

Preview

Summary

Lecture notes reviewing material for the final exam along with practice problems...

Description

Hey everyone!

Test 5/the final exam opens on Monday. You must start the test by 11:55PM on Thursday, May 3rd. Any Unit 5 work you complete until that deadline will be accepted as well, although the official deadline for Unit 5 work is today. Test Difficulty Many of y'all found the Unit 4 Test much harder than the Unit 2 and 3 tests. While the averages on the Unit 2 and 3 tests were 96% and 91%, the average on the Unit 4 Test was 72%. Generally, that does mean that the overall test average -- now 86% -- is closer to where we want it. Unfortunately, there's a significant negative skew, so the Unit 4 Test average is pulled down by some far lower scores (in other words, if you did way below 72% on the Unit 4 Test, you're far from alone!). Historically, it's very difficult to gauge the difficulty of Test 5. The all-time class average is low, in the lower 70s, but most students quit the final exam as soon as they reach their max grade threshold. Something absurd like 75% students in the class get within 3 points of a grade cut-off (e.g. 90-92, 80-82, 70-72), indicating most people stop once their final grade is set. So, I tend to gauge its difficulty by looking at how many students end the semester with just below a grade cut-off (e.g. 87-89, 77-79) who could have gotten the next letter grade with a better exam grade, and historically it's very few students. So, it's not quite as challenging as the Unit 4 Test, but it's not quite as easy as the Units 2 and 3 tests. Multiple Choice and Fill in the Blank Like last time, we're giving you two resources from which to work: an outline of the multiple-choice and fill-in-the-blank problems to expect, and a list of possible programming problems we might ask you to complete.

For the Unit 5 Test, multiple choice/fill-in-the-blank questions will make up 20% of your grade, and coding problems will make up the other 80%. 50% of the grade is from Unit 5 specifically, and 50% of the grade is more cumulative over the entire course.

First, here are the multiple choice/fill-in-the-blank questions to anticipate:

#

Point Part Pts/Pa Type rt s s

13

6

0.5

Multiple Choice

23

6

0.5

Multiple Choice

33

3

1

Multiple Choice

43

6

0.5

Multiple Choice

Attempt Description s* You'll be given object definitions and asked to answer questions about them, like "Which of the following is an 2 attribute of the object?" or "Which of the following would create an instance with the following attributes?" You'll be given the code for multiple recursive functions, each with one or more blanks. You'll be asked to select 2 which code segment would correctly fill in the blank to allow the function to work as described. You'll be given a segment of code and asked to select its efficiency in Big O 2 from the ones we've covered (from this table). You'll be given the name of a sort or search algorithm and asked to answer questions like: what will the list be after the next iteration?; what item in the list 2 will be moved first?; how many comparisons will it take to find the search term?

* - Problems may have multiple parts with only one submit button; however, each part is individually marked right or wrong after submitting. Coding Problems There will be 9 coding problems on the test. The first six are worth 6 points each, and the last three are worth 4 points each, for 48 points total. The first three coding problems will be specific to Unit 5; the other six will be cumulative over the entire course. Here are 20 possible problems we might ask. We'll choose 9 of these (3 from the first eight, 6 from the last twelve) to have on the actual test. Note that the TAs will not specifically cover these problems at the review session mentioned in @557 -- they may cover similar problems, but they won't cover these exact problems. You may assume these will all involve writing either classes or functions.

1. Create a class to represent a Right Triangle, similar to the dictionaries you created in Chapter 4.4 or the Force class you created in 5.1. 2. Create a class to represent a basketball game, including both team's names, the score, and a method for retrieving the winner. 3. Using a Student class that we provide, calculate a class average derived from each individual student's get_grade() method. 4. Using an Athlete class that we provide, find the tallest and/or shortest athlete from a list of instances of the Athlete class. 5. Implement a variation of the Fibonacci sequence where instead of adding pairs of numbers, you multiply, divide, or subtract them. 6. Implement a variation of the Fibonacci sequence where instead of assuming the first two numbers are 1 and 1, the first two numbers are instead passed in as arguments (e.g. [5, 7, 12, 19, 31...] or [-1, 1, 0, 1, 1, 2, 3, 5...]). 7. Implement a sorting algorithm, either a specific one (bubble, selection, or insertion -- we won't ask you to implement Merge) or just any search algorithm. 8. Implement a search algorithm that searches a list of instances of a Student object with first_name and last_name attributes and sees if a certain name is found. 9. Interpret a tuple representing the score of a ping-pong game and return who has won or if the game is not over. 10. Interpret a 2-tuple representing an instance of the prisoner's dilemma, where the values of the tuple are booleans representing betray (True) or silence (False), and the outcome is a tuple representing the number of years of prison each person serves. 11. Count the number of positive even numbers from a list of integers. 12. Read in a file of text, make one or more changes to it (capitalize every word, make the entire text lower-case, remove every instance of the letter "e", etc.), then write it back to a different file. 13. Take in a dictionary and a key, and check whether the string corresponding to that key in the dictionary can be interpreted as an integer, float, boolean, or if it's not present at all. 14. Check to see if a string is a palindrone, like "tacocat", "girafarig", or "abeddeba". You may have to ignore capitals and remove punctuation/spaces, as in the case of "Air an aria" or "A man, a plan, a canal: Panama.". 15. Given a list of booleans and a list of integers, change the values in the list of booleans corresponding to those integers. For example, given [True, False, True] and [0, 1], you'd return [False, True, True], having flipped the values at indices 0 and 1. 16. Read in a file containing a list of actors and the ages at which they won Oscars, and return a 2-tuple containing the names of the youngest and oldest actors to win an Oscar from that list. 17. Use the Leibniz Formula to calculate pi based on a specific number of iterations (e.g. leibniz(5) = $$4 \cdot (1 - \frac{1}{3} + \frac{1}{5} \frac{1}{7} + \frac{1}{9})$$ = 3.339

18. Given a day, month, and year, calculate the day of the week corresponding to that date without using the Python DateTime class. (We'll give you a little help with the formula if we select this one, but you may also want to research it on your own in advance.) 19. Read in a file containing a list of movies, their release dates, and their total gross, and create a list of instances of a Movie class with these attributes. 20. Convert a list of dictionaries into a list of instances of an object with attributes corresponding to the original keys, or vice versa (a list of instances of an object into a list of dictionaries with key-value pairs corresponding to the attributes). These descriptions are written so that you have enough information to try out the problem 'idea' yourself, but not so much detail that you can write code that perfectly meets our test requirements. So, you're welcome to work together to work out some of these possible answers before the test, but remember you may not bring any notes into the test. Please do not ask the TAs for help with these before the test, though.

The test allows copy/paste and includes a scratchpad for every problem. For that reason, you should not use any scratchpaper or hand-write anything on your desk during the test. The test will still be 2 hours like the previous tests even though it's the final exam -- it isn't any longer, after all.

1. What Are Objects? At this point, we’ve covered the basics of computing. Congratulations! So far, you’ve covered the principles and methods that put a man on the moon. The techniques you now know covered the state of the art of computing for its first several decades of existence. Surprisingly, though, the principles needed to put a man on the moon were far simpler than the principles needed to load up that gif of a cat falling down on your phone. Modern cloud computing, virtual reality, and even typical web development require more complex frameworks and paradigms than the ones responsible for the early days of the space program. Unit 5 is our “advanced topics” unit. In this unit, we’re going to preview the next topics you’ll cover if you decide to continue your education in computing. We’re going to focus on two topics: objects and algorithms. In many ways, these two topics cover two different directions you could choose to go in computing. If you want to go into developing websites, video games, or other portions of the design side of computing, you’ll be using objects a lot. If you want to go into machine learning, theory, or the more mathematical side of computing, you’ll spend a lot of your time developing algorithms.

What Are Objects? That brings us to the topic for this chapter. What are objects? Surprise! You’ve actually been interacting with objects throughout the past several chapters; we’ve just glossed over them and promised to come back to them later. Well, later is now. Objects are custom data types that you get to create. We usually refer to the data types themselves as Classes. Just like you’ve been using data types to represent numbers, letters, and strings, you can create data types or classes to represent people, places, and items. In creating these, you specify multiple variables to be wrapped up into one data type. One of the biggest strengths of programming with objects is that it lets us write programs the way we think about things in the real world. We’re naturally predisposed to think about the world in terms of generic objects. For

example, you have the concept in you of a person. A person would be a single entity that has lots of variables assigned to them. They have a first name, a last name, and a middle name. They have a height, a hair color, and an eye color. They have a phone number and an e-mail address. These are all variables that we could wrap up into one data type, and call that data type a Person class. The class tells us what variables should be specified for that type of object. A Person object would almost certainly have a first name and a last name, and that’s the reason why we know that asking, “What’s your name?” is a logical question to ask a new person. We know they should have a name because these are variables in that type. By that same principle, if we had a Chair object, we would find it very silly to ask, “What’s your name?” to a chair because “name” probably isn’t a variable we’d associate with a chair type.

Objects vs. Instances Page 256 So,

a class is a generic structure for a certain kind of data. If we have a Person class, we expect it to have a name, a height, and an eye color. These are variables we expect to exist about people.

An instance, on the other hand, is a specific person. A Person class is a data type with variables for name, age, and eye color. David Joyner is an instance of aPerson object with name “David Joyner”, age 30, and eye color brown. “David Joyner”, 30, and brown are values for these variables, just as David Joyner is an instance of an object of type Person. It might seem weird to differentiate the name “David Joyner” from the Person David Joyner, but ask yourself: if I change my name, am I suddenly a different

person? No; having a name is a variable, my actual name is that variable’s value, but even if I change that variable’s value, the person is the same. It’s just difficult to refer to people without using their names! Think about this with something like chairs, though: a chair has a serial number, which is an unchanging name of that specific chair, differentiating it from other chairs of the same type. Even if we remove a leg and change the color, the serial number remains the same. Classes are the general description of the types of variables associated with the type. An instance of the class is a particular example of an object of that type. You know what a person is, and you know that David Joyner is an example—an instance—of a person. Similarly, you know what a chair is in general, and the chair you’re probably sitting on right now is an instance of a chair. You know that chairs can have lots of variables, like a number of legs, a color, and a material; similarly, you know that the chair you’re sitting on is white, wooden, and has four legs. You know that not all chairs are white with four legs, just as you know that not all people are named “David Joyner”. The general concepts are classes, and the specific examples are instances of these classes.

2. Objects and Instances in Python To get started, let’s talk just about how to define classes and instances in Python. We’ve actually already seen these in some places, but we didn’t refer to them by these terms. For this lesson, let’s stick to the running Person example. A Person should have a first name, a last name, an eye color, and an age. We’ll represent the names and eye color as strings and the age as a number.

Declaring a Class Figure 5.1.1 shows how we would define our Person class. Line 2 here is the line that starts off the creation of a new object. This is similar to what we’ve seen in the past with loops and conditionals: the reserved word class tells the computer that it’s about to see a code block contained within the class, after the class name (Person) and a colon as usual. The contents of the class is indented.

Figure 5.1.1 Page 257 What

do we see next? On line 4, we see… a function! A function with the strange name __init__ and the strange parameter self. We’ll talk more about__init__ later, but for now, what you need to know is that __init__ is called when we first create a new instance of this class. Think back to when we would define strings: The string class actually had an __init__ method that was called whenever we created a new string. It just executes some code that will be needed for the rest of the program. Here, when we create a new Person, we want to give some default values to the names and eye color that emphasize that the real values haven’t yet been supplied. When a function is defined inside a class, we call it a method. It still works the same way: when the method is called, the lines of code are executed in order. In the __init__() method here in Figure 5.1.1, there are four lines. Notice that each line starts with the variable name self. self is a little strange: it tells Python to define the following variable (like firstname) for the instance as a whole. If we leave off self, the variable has the same scope as a variable normally would in a function: it stops existing when the function is

over. So, writing self.firstname says, “Any time we look at this instance’s firstname, it should be the same one!” Every method declared inside a class should have self as the first parameter, and every variable for the class should be preceded by self every time the variable is used inside the class. self is a little like saying ‘my’; it collects together the class’s variables. Defining the Person class works just like defining the functions we’ve seen in the past. Seeing the line class Person tells the computer, “Hey, you need to know this concept of a Person.” Later on, we can actually use this concept in our code. Think of declaring a class like teaching someone a concept. If you knew someone wasn’t familiar with books, you would teach them that every book has a title and an author; then when you give them a book, they would know to look for the title and author. Teaching them the idea of a book having a title and author is like declaring a class; handing them a copy of Introduction to Computing by David Joyner is like having them create an instance. Once defined, though, classes work like any data type. You can use instances of them as values in lists or tuples. If some of their variables are lists, you can loop over these lists. You can even use classes as values for other classes. For example, we could create a Name class that has two variables, firstname and lastname, as shown in Figure 5.1.2.

Figure 5.1.2

In Figure 5.1.2, an instance of the Name class supplies the firstname and lastname to the Person class. We can use this to create extremely complex data structures that are nonetheless easy to use because everything is organized in logical ways.

Creating Instances Page 258 Now

that we have the class declared, we can use it in our program! We declare a new person with the line myPerson = Person(), as shown on line 12 ofFigure 5.1.3. Notice that this syntax looks like we’re calling a function because of the parentheses after Person. This line is effectively like callingPerson.__init__(), but Python is smart enough to let us leave out __init__ when it’s written exactly like that. So, calling Person() is like saying to the computer, “Give me a new instance of Person!” As a result, the computer creates a new instance, runs __init__ to do the initial setup, and then returns that new instance so that we can assign it to a variable, all on line 12.

Figure 5.1.3 Then, we can use myPerson like a normal variable. By calling myPerson. firstname on line 14, we access self.firstname from within the instance. Notice that this is similar to calling something like myString.isupper() to check if a string is uppercase: firstname and isupper() are

contained within the instance, and calling them gives an answer specific to that instance. The difference is that firstname is a variable while isupper() is a method, but we’ll talk about that in detail later. Once we’ve created an instance of a class, we can also modify its variables just as if they were variables in our own program, as shown in Figure 5.1.4. We can print these variables by calling print(myPerson.firstname), or we can modify Page 259 them just by reassigning myPerson.firstname. Here on line 16, we reassign it to “David”, then print it on line 18 to see the change. What about in our more complex example, though, where we had separate classes for Name and Person?

Figure 5.1.4 5.1.5, In Figure instead of accessing firstname directly from myPerson (myPerson.firstname), we instead access name from myPerson (myPerson. name), and then access firstname from name (myPerson.name.firstname). nam e.firstname means “get name’s firstname”. So, myPerson.name.firstname “get myPerson’s name’s firstname.” We’ll stick with just one class for the most part, but know we can combine them like this as well.

Figure 5.1.5 The usefulness of objects is that we can create multiple instances, each with their own values. For example, we could create mutliple variables to represent multiple people, and give each person a unique name, as seen in Figure 5.1.6.

Figure 5.1.6 5.1.6, In Figure we define two instances of the Person class, myPerson1 and myPerson2. Changing the first name of myPerson1 doesn’t impact myPerson2, as confirmed by the print() statements on lines 18 and 19. We could thus create lists of lots of instances of Person to represent class rosters or directories, and modifying one instance wouldn’t affect any of the others.

Objects vs. Dictionaries Page 260 Recall

that at the end of the Chapter 4.5 on dictionaries, we briefly discussed usin...