Please turn in a PDF through Gradescope. You'll need to access Gradescope through Brightspace the first time (to register you for the course in Gradescope.) Gradescope is pretty self-explanatory, ITaP provides these instructions. Make sure that you mark the start/end of each question in Gradescope. Assignments will be graded based on what you mark as the start/end of each question. Please typeset your answers (LaTex/Word/OpenOffice/etc.)
Note: This is a half credit
assignment, really just to let you make sure you understand some of the basics you'll need for the course.
Jasmine and Sarah compete in two different events at the Olympics. Jasmine and Sarah win the race with probability p1 and p2 respectively. Assuming independence, are these scenarios possible?
Determine whether the following matrix has an inverse without trying to compute the inverse. (Hint: Use determinant)
| 3 | -2 | 1 | 0 |
| 5 | 0 | 2 | 0 |
| 2 | -8 | -1 | 0 |
| 0 | 7 | 0 | 1 |
Find eigenvalues and eigenvectors of the following matrix:
| 3 | -1 |
| 0 | 2 |
Arrange the following functions by increasing order of growth (log base 2):
n0.5, 2log(n), log(n!), log(log(n)), n!, 22n, n log(n), n-1, (log(n))2, 10000
Was it important to know the base of the logarithm? Why or why not?
We noted that finding an optimal solution to the 15 puzzle (generalized as the (n2-1) puzzle, e.g., for the 15 puzzle, n=4) is NP-hard. In other words, as we increase the length of a side (n), it becomes exponentially harder to find the optimal solution to the resulting (n2-1) puzzle.
If we instead said n was the number of tiles (e.g., 15) instead of the length of a side (e.g., 4), is finding the optimal solution still exponential time complexity? Give a proof of your answer.
Find the convex and concave intervals for the following functions:
