The final exam is Wednesday December 9, 1:00 - 3:00 PM in our class room. The exam will be written, no notes, no calculator, just pencil/pen/eraser and paper. The format will be very similar to the previous exams, although there will be more problems.
The final is cumulative so anything from the entire course can be on the exam. Having said that, roughly 60%-70% of the questions will be from material from Day 28 through the end of the course (this is material that did not appear on Exam 1 or Exam 2). Look back at the pages for the lectures plus the review pages for the first two exams. The highlights for Day 28 on are
Write a python function with a default argument. For example, write a python function to print out the sum of the first n numbers, where n is defaulted to 100. Call your function once without specifying n, once specifying n with a positional argument, and once specifying n with a keyword argument.
Given a digital circuit, convert it to a boolean expression. If the inputs are specified, what value does the digital circuit compute. Convert a boolean expression to a digital circuit. Here is a problem.
Implement two simple classes, one which inherits from the other. E.g. define a Shape class and two derived classes for Square and Circle with area functions. Alternatively, I give you some python code which has a class inheriting from another plus some code calling the methods and ask you to explain what is happening.
I show you some algorithm, for example the Euclidean Algorithm. (see the implementations section for some psuedocode.). I then ask you to tell me the running time in big-O notation, maybe explain what is happening, why it works, etc.
Some short answer type problems on complexity. What is P vs NP?
How many poker flushes are possible if you know that 4 hearts have already been used? Answer is \(3\binom{13}{5} + \binom{9}{5}\) and I would also ask you to explain why that is the answer.
How many ways are there to pick two cards from a standard 52-card deck such that the first card is a spade and the second is not an ace? Answer is \(12 \times (52-5) + 1 \times (52-4)\).
Call a set \(S\) of vertices in a graph \(G\) independent if there are no edges with both endpoints in the set \(S\). Let \(\alpha(G)\) be the size of the largest independent set in \(G\). Argue that the chromatic number of an n-vertex graph is at least \(\frac{n}{\alpha(G)}\). Hint: Think about the set of vertices receiving the same color.
For sage, I won't ask you to implement/write any sage code. Instead consider some some short answer/true false/multiple choice type problems on sage, symbolic computation, numeric analysis, numpy.
def sum(n=100):
result = 0
for i in range(n+1):
result +=1
print(result)
sum()
sum(40)
sum(n=20)Two classes:
class Shape:
def area(self):
pass
class Circle:
def __init__(self, radius):
self.radius = radius
def area(self):
return self.pi * self.radius ** 2
class Square:
def __init__(self, side):
self.side = side
def area(self):
return self.side ** 2For the algorithm, see the wikipedia page which describes the algorithm.
Poker flushes: First, there are three suits which are not hearts. There are then \(\binom{13}{5}\) ways of picking 5 cards of that suit. What about hearts? There is one way to pick the suit hearts. There are then \(\binom{13-5}{5}\) ways of picking 5 hearts from among the \(13-5\) unused hearts.
Picking spade and non-ace. There are then \(52-5\) ways of picking a second card that is not an ace (4) and also not the card you have already selected. This gives \(12 \times (52-5)\). Then, there is one way to pick the ace of spades. There is then \(52-4\) cards which are not aces that can be selected, so \(1 \times (52-4)\).
All the vertices with the same color must form an independent set since there cannot be an edge between two vertices of the same color. Thus the largest number of vertices which can be given the same color is \(\alpha(n)\). You therefore need at least \(\frac{n}{\alpha(n)}\) colors, since otherwise you wouldn't be able to give each vertex a color.