CS50 Quiz 2017: Answer Key

Comparing Students

Answers

1.1: A function pointer that points to a function that accepts two (generic) pointers as arguments and returns an int.
1.2: Because the arguments to qsort's comparison function are generic pointers, they must be typecast to their actual types (const int *) so that the pointers can be dereferenced to actual int values.
1.3

int cmp(const void *a, const void *b)
{
    return strcmp(((student *)a)->name, ((student *)b)->name);
}

1.4

def main():
    students = [
        Student("Stelios", "Branford"),
        Student("Maria", "Cabot"),
        Student("Anushree", "Ezra Stiles"),
        Student("Brian", "Winthrop")
    ]
    print("Before:")
    for student in students:
        print(f"{student.name} from {student.dorm}")
    students = sorted(students, key=lambda s: s.name)
    print("After:")
    for student in students:
        print(f"{student.name} from {student.dorm}")

1.5

function cmp(a, b)
{
    if (a.name < b.name)
    {
        return -1;
    }
    if (a.name > b.name)
    {
        return 1;
    }
    return 0;
}

SQLiTunes

Answers

2.1: ArtistId is a foreign key in the table called Album because it references a (like-named) primary key in the table called Artist.
2.2: If Artist had a column called AlbumId, that would imply that an artist could have only one album, but some artists have many albums.
2.3: It’s more efficient (i.e., faster) to compare INTEGERs (which, in SQLite, are 1, 2, 3, 4, 6, or 8 bytes) rather than email addresses (stored as TEXT) of arbitrary length.
2.4

SELECT SUM(Total) FROM Invoice WHERE InvoiceDate BETWEEN '2010-01-01' AND '2010-12-31'

2.5

SELECT Track.Name FROM Invoice JOIN InvoiceLine ON Invoice.InvoiceId = InvoiceLine.InvoiceId JOIN Track ON InvoiceLine.TrackId = Track.TrackId WHERE CustomerId = 50

2.6: Create a new table called Composer with two columns, ComposerId and Name, where the former is a PRIMARY KEY with type INTEGER and the latter is TEXT, storing each of the unique values in Track.Composer in Name and assigning each a ComposerId (as via AUTOINCREMENT). Then replace Track.Composer with Track.ComposerId, where the latter is now a foreign key that maps to Composer.ComposerId.

Stack is Back

Answers

3.1: When an object of some class is instantiated, __init__ is a method that’s called (potentially with arguments) in order to initialize that object.
3.2

def peek(self):
    """Return top of stack without popping."""
    return self.list[-1]

def pop(self):
    """Remove and return top of stack."""
    self.list.pop()

def push(self, item):
    """Push item on to top of stack."""
    self.list.append(item)

3.3: Whenever a start tag (e.g., <div id="main">) is encountered while parsing a string (as induced by a call to feed), handle_starttag is called.
3.4: Whenever an end tag (e.g., </div>) is encountered, is encountered while parsing a string (as induced by a call to feed), handle_endtag is called.
3.5

def handle_starttag(self, tag, attrs):
    """Handle the start of a tag."""
    self.stack.push(tag)

def handle_endtag(self, tag):
    """Handle the end tag of an element."""
    if self.stack.peek() == tag:
        self.stack.pop()

It turns out this problem had a bug, whereby it wasn’t actually (easily) possible to detect mismatches like <b></i></b> without using exceptions. Since this question explicitly said not to worry about exceptions, we only checked, when scoring handle_endtag, that mismatches like <b><i></b></i> were detected as prescribed.

To be or not to be

Answers

4.1: 1000.
4.2: update_fitness counts the number of characters that a string has in common, in the same positions, with target and then divides that total by the length of target, which yields a value in [0.0, 1.0].
4.3: 1/18 = .056 (because KoMQ%25"zHnGt1whXY has one character in common, in the same position, with to be or not to be).
4.4: Instead of counting the number of characters that a string has in common, in the same positions, with target, you could instead count the minimal number of additions, deletions, or substitutions required to transform the string into target, dividing that number by the length of target.
4.5: If none of the strings in some generation have a particular character in the correct position, their children, after crossover, won’t either. Mutations ensure that the missing character might at least appear in the correct position by chance.

Vantage Points

Answers

5.1: CSV is more space-efficient in that keys are only stored in a CSV file’s first row (if at all), whereas JSON stores one key for every value. CSV also lends itself to appending, since new rows can be added without modifying previously added rows, whereas in JSON, a previously added ] or } might need to be removed or relocated to accommodate new data. CSV files can also be opened as spreadsheets in programs like Excel.
5.2: JSON allows for hierarchical data, since the values of keys can be objects themselves. Languages like JavaScript also have built-in support for JSON.
5.3

https://www.alphavantage.co/query?function=TIME_SERIES_INTRADAY&symbol=NFLX&interval=1min&apikey=NAJXWIA8D6VN6A3K&datatype=csv

5.4: In the JSON output, none of the keys is well-designed. A key like 1. open should instead be just open; prepending 1. ` requires that developers remember that that prefix, including the space. The value of `Time Series (1min) should really be an array of objects, since a series is, semantically, a list.