Description

Background
TAs: Longxiang Zhang, Yuwei Qiu, Yang Yu, David Xu, Eric Chen
START HERE: Instructions
cmu.edu/~mgormley/courses/10601/about.html
• Late Submission Policy: See the late submission policy here: http://www.cs.cmu. edu/~mgormley/courses/10601/about.html
• Submitting your work:
– Autolab: You will submit your code for programming questions on the homework to Autolab (https://autolab.andrew.cmu.edu/). After uploading your code, our grading scripts will autograde your assignment by running your program on a virtual machine (VM). The software installed on the VM is identical to that on linux.andrew.cmu.edu, so you should check that your code runs correctly there. If developing locally, check that the version number of the programming language environment and versions of permitted libraries match those on linux.andrew.cmu.edu. (Octave users: Please make sure you do not use any Matlab-specific libraries in your code that might make it fail against our tests.) For this homework ONLY, you have unlimited number of submissions; you’ll be given a finite number of submissions for future homework, use them wisely. In order to not waste Autolab submissions, we recommend debugging your implementation on your local machine (or the linux servers) and making sure your code is running correctly first before any Autolab submission. The above is true for future assignments, but this one allows unlimited submissions.
• Materials: Download from autolab the tar file (“Download handout”). The tar file will contain all the data that you will need in order to complete this assignment.
For multiple choice or select all that apply questions, shade in the box or circle in the template document corresponding to the correct answer(s) for each of the questions. For LATEXusers, use and for shaded boxes and circles, and don’t change anything else.
1 Hello, Autolab! [29 Points]
1.1 Introduction
The goal of this assignement is to ensure that you:
1. Have a way to edit and test your code (i.e. a text editor and compiler/interpreter)
2. Are familiar with submitting to Autolab
3. Are familiar with file I/O and standard output in the language of your choice
1.2 Reading from a file [19pts]
In reverse.{py|m|java|cpp}, implement a program that reads in the lines of a file, then writes them in reverse order to an output file. Specifically, your program should take two command line arguments: the name of the input file and the name of the output file. It should read the lines of the input file and write them to the output file from last to first, separated by “ ”. You should assume that the input file has unix-style line breaks. (Windows uses “ ” to indicate a new line. Unix uses only “ ”.)
For example, if the file input.txt contained the stream
#pineapples #pinstripes #pinwheelofdoom #pinsir
which is commonly displayed as
#pineapples
#pinstripes
#pinwheelofdoom
#pinsir
depending on your language of choice, one of the following:
• python reverse.py input.txt output.txt
• octave -qH reverse.m input.txt output.txt
• javac reverse.java; java reverse input.txt output.txt
• g++ reverse.cpp; ./a.out input.txt output.txt
should write the following to output.txt
#pinsir #pinwheelofdoom #pinstripes #pineapples
which is displayed as
#pinsir
#pinwheelofdoom
#pinstripes
#pineapples
Note to Octave users: Please be sure that reverse.m is a script that gets its arguments from the command line rather than a function.
1.3 Test Code on linux.andrew.cmu.edu Machines
Before submitting to Autolab on this and every future assignment, you should check that it behaves correctly when run on the linux.andrew.cmu.edu machines, since they mirror the software installed on the Autolab virtual machines (VMs). These instructions assume you are working on a unix based operating system (e.g. Linux, Mac OS) – if you are using Windows you can install cygwin (https://www.cygwin.com/) which provides a unix-like environment. (Of course, you are also welcome to develop your code directly on these same servers.)
Follow the three stpes below. Here we assume your code and the example.txt file are located in a subdirectory ./reverse/.
1. Copy your code to the linux server:
rsync -a ./reverse/ <Your Andrew ID>@linux.andrew.cmu.edu:~/reverse/
2. Log into the linux server:
ssh <Your Andrew ID>@linux.andrew.cmu.edu
3. Change directories to where you just copied the code:
cd ~/reverse/
4. Run the code with one of the below:
• python reverse.py example.txt output.txt
• octave -qH reverse.m example.txt output.txt
• javac reverse.java; java reverse example.txt output.txt • g++ -g -std=c++11 reverse.cpp; ./a.out example.txt output.txt
5. Check that it was properly reversed:
cat output.txt
1.4 Command Line Arguments
In this and future programming assignments, we will use command line arguments to run your programs with different parameters. Below, we provide some simple examples for how to do this in each of the programming languages you can use in the course.
Python:
from __future__ import print_function import sys
if __name__ == ’__main__’: infile = sys.argv[1] outfile = sys.argv[2] print(“The input file is: %s” % (infile)) print(“The output file is: %s” % (output))
Java:
public class myclass { public static void main(String[] args) {
String infile = args[0];
String outfile = args[1];
System.out.println(“The input file is: ” + infile);
System.out.println(“The output file is: ” + outfile);
}
}
C++:
#include<iostream> #include <string> using namespace std; int main(int argc, char **argv){
if (argc >= 3) { string infile = string(argv[1]); string outfile = string(argv[2]); cout << “The input file is: ” << infile << endl; cout << “The output file is: ” << outfile << endl;
}
return 0;
}
Octave:
args=argv(); infile=args{1}; outfile=args{2}; disp(horzcat(“The intput file is: “, infile)) disp(horzcat(“The output file is: “, outfile))
1.5 Autolab Submission [10pts]
You must submit a .tar file named reverse.tar containing reverse.{py|m|java|cpp}. You can create that file by running:
tar -cvf reverse.tar reverse.{py|m|java|cpp} from the directory containing your code.
Some additional tips: DO NOT compress your files; you are just creating a tarball. Do not use tar -czvf. DO NOT put the above files in a folder and then tar the folder. Autolab is case sensitive, so observe that all your files should be named in lowercase. You must submit this file to the corresponding homework link on Autolab.
Python3 Users: Please include a blank file called python3.txt (case-sensitive) in your tar submission and we will execute your submitted program using Python 3 instead of Python
2.7. If the file is not present, we will default to running your code with Python 2.7.
Instructions for Specific Problem Types
For “Select One” questions, please fill in the appropriate bubble completely:
Select One: Who taught this course?
Matt Gormley
# Marie Curie # Noam Chomsky
Select One: Who taught this course?
Matt Gormley # Marie Curie
@ @ Noam Chomsky
For “Select all that apply” questions, please fill in all appropriate squares completely:
Select all that apply: Which are scientists?
Stephen Hawking
Albert Einstein
Isaac Newton
I don’t know
Select all that apply: Which are scientists?
Stephen Hawking
Albert Einstein Isaac Newton
@@ I don’t know
Fill in the blank: What is the course number?
10-601 10-S7601S
2 Course Polices [3 Points]
This section covers important course policies that every student should know and understand. These questions MUST be finished in order for the whole homework to be considered for grading.
1. [0.5 pt] Assignment turned in late without prior approval will incur a daily penalty.
How much is the penalty? Up to 1 day: Up to 2 day: Up to 3 day: Up to 4
day:
Select one:
5%, 10%, 15%, 20%
10%, 20%, 30%, 40%
25%, 50%, 75%, 100%
20%, 40%, 60%, 80%
Select one:
As many as I want; Of course!
6; No
8; Yes
6; Yes
3. [0.5 pt] Seeking help from other students in understanding course materials needed to solve homework problems is ALLOWED under which of the follow conditions?
Select all that apply:
No written notes are shared or taken at any time
Learning is facilitated not circumvented; i.e., the purpose of seeking help is to learn and understand the problem instead of merely getting an answer Help both given and received is reported in collaboration questions in the homework
The student updates his/her collaborative questions even if it is after submitting their own assignment
4. [0.5 pt] Which of the following is (are) strictly forbidden in solving and submitting homework?
Select all that apply:
Searching on the internet for solutions or sample codes
Consulting people outside this class who have seen or solved the problem before Turning in someone else’s homework
Using anyone else’s, or allowing other classmates to use your computer, Autolab or Gradescope in connection with this course
5. [0.5 pt] If you solved your assignment completely on your own, you can skip the collaboration questions at the end of each homework.
Select one:
True
False
6. [0.5 pt] What is (are) the consequence(s) of being caught cheating in this course?
Select all that apply.
First time:
A one and a half letter grade reduction (e.g., A becomes B-)
Second time:
Failure of the course
3 Prerequisite Practice[68 Points]
In this section, you will work through a number of problems covering probability, statistics, calculus, linear algebra, geometry, and computer science. First subsection will be covering common course policy questions
3.1 Probability and Statistics [30pts]
Use the following data to answer questions 1-4. Consider data created by flipping a

coin five times S = [1, 1, 0, 1, 1] , where 1 denotes that the coin turned up heads and 0 denotes that it turned up tails.

1. The sample mean for this data is:
1

2. [2pt] The (uncorrected) sample variance for this data is:
Select one:

3. [2pt] With reference to the previous question, what is the probability of observing any combination of this data (4 heads and 1 tails), assuming it was generated by flipping a coin X with an unequal probability of heads (1) and tails (0), where now the distribution is P(X = 1) = 0.75, P(X = 0) = 0.25?
Select one:

4. [2pt] Note that the probability of this data sample would be greater if the value of P(X = 1) was not 0.5, but instead some other value. What is the value of P(X = 1) that maximizes the probability of the sample S? Provide your answer as a fraction.

5. [2pt] State true or false. For events A and B,
P(A ∩ B) = P(A) + P(B) − P(A ∪ B)
Select one:
True
False
6. [2pt] State true or false. For events A and B,
P(A1 ∩ A2 ∩ A3) = P(A3|A2 ∩ A1)P(A2|A1)P(A1)
Select one:
True
False
Use the following information to answer questions 7-8. Whether your car is

P(R) = 0.4
P(W|R) = 0.8
P(W|¬R) = 0.2
7. What is the probability of P(¬R)? (Here ¬R reads: no rain last night)
0.1
0.4
0.9
0.6
8. [2pt] Using the same probabilities as the previous question, what is the probability that your car is wet in the morning?
Select one:
0.64
0.56
0.44
0.4
Use the following information to answer questions 9-10. Consider the follow-

ing joint probability table where both X and Y are binary variables:
X Y Probability
0 0 0.1
0 1 0.2
1 0 0.4
1 1 0.3
9. [2pt] Using the same table, what is P(X = 1|Y = 1)?
Select one:

10. What is P(Y = 0)?
0.2
0.6
0.5
0.3
Use the following information to answer questions 11-13. Let X be a random

variable and the expected value of X is E[X] = 1 and the variance of X is V ar[X] = 1.
11. [2pt] What is E[6X]?
Select one:
1
3
6
36
12. [2pt] What is V ar[3X]?
Select one:
1
3
6
9
13. [2pt] What is V ar[2X + 3]?
Select one:
3
4
5
7
14. What is the mean, variance and entropy of a Bernoulli (p) random variable?
p,p(1 − p),−(1 − p)log(1 − p) − plog(p) p(1 − p),p,−(1 − p)log(1 − p) − plog(p) p,p(1 − p),log(1 − p) − plog(p)
The entropy of a Bernoulli variable is not defined.
15. [2pt] Please match the probability density function of the random variable X to its corresponding distribution name.
(a) prob(X=x) =
(b) prob(X=x) = λe−λx when x ≥ 0; 0 otherwise
(c) prob(X=x) =
(d) prob(X=x) = when a ≤ x ≤ b; 0 otherwise
(e) prob(X=x) = px(1 − p)1−x
Multivariate Gaussian:
Exponential:
Uniform:
Bernoulli:
Binomial:
3.2 Calculus [8pts]
1. [2pt] Find the derivative of y with respect to x, where y = 2×4 − x3 + 5x − 1
Select one:
8×3 − 3×2 + 5
8×4 − 3×3 + 5x
6×3 − 2×2
16×3 − x2 + 5
2. [2pt] Evaluate the derivative of y with respect to x, where at x = 1.

3. [2pt] Find the partial derivative of y with respect to x, where y = 3×2 sin(z)e−x
Select one:
3xsin(z)e−x(2 + x)
−6xsin(z)e−x
3xsin(z)e−x(2 − x)
6xcos(z)e−x
4. [2pt] For the function f(x) = 5×3 +2×2 −3x the value sets the derivative to be
0. What can you say about f(x) at the point :
Select one: a minimum a maximum a minimum or a maximum
None of the above

3.3 Vectors and Matrices [10pts]
1. [2pt] Consider the matrix X and the vectors y and z below: X .
What is the inner product of the vectors y and z? (this is also sometimes called the dot product) Select one:

2. [2pt] Using the same values for X, y, and z as above, what is the product of Xy?
Select one:

3. [2pt] For the matrices A and B What is the product
AB?
Select one:
19
−14
−4
19
9
−2
20 −20 −28
3

3 −14
2
19
−14
−5
4. [2pt] True or False, The matrix A from the previous question has an inverse?
Select one:
True
False
5. [2pt] Given matrix X and the column vector y , what is the
eigenvalue of X associated with y?
Select one:
y is not an eigenvector
-3
2
1.5
3.4 Geometry [6pts]
1. [2pt] What relationship does the vector w share with the line wTx + b = 0? (assume x and w are both two dimensional column vectors, and wT indicates the transpose of the column vector w.)
Select one:
parallel orthogonal depends on the value of b
2. [2pt] With reference to the above question, select the statement which best explains why w and wTx + b = 0 share the above relationship.
Select one:
The inner product wT(x0 − x00), where x0 and x00 are two points on the line wTx + b = 0, is 0
The inner product wT(x0 − x00), where x0 and x00 are two points on the line wTx + b = 0, is 1
The inner product wT(x0 − x00), where x0 and x00 are two points on the line wTx + b = 0, is b0 − b00
3. [2pt] What is the distance from the origin to the line wTx + b = 0? (In the following answers, λ is some constant) Select one:
w
3.5 CS Foundations [14pts]
1. [2pt] If f(n) = ln(n) and g(n) = log3(n) which of the following are true?
Select one:
f(n) ∈ O(g(n)) g(n) ∈ O(f(n))
Both
Neither
2. [2pt] If f(n) = n10 and g(n) = 10n which of the following are true?
Select one:
f(n) ∈ O(g(n)) g(n) ∈ O(f(n))
Both
Neither

Figure 1: Britian’s Royal Family
3. [2pt] Using the tree shown in Figure 1, how many nodes would depth-first-search visit in finding Mia Tindall (including her node)? Assuming we search left-to-right and top-down.
Select one:
3
12
15
18

Figure 2: A Binary Tree with indexed nodes
4. [2pt] Figure 2 is a Binary Tree with indexed nodes. Assume root node is node 1. What is the node-visit order of DFS and BFS of the above Binary Tree?
A depth-first search (DFS) traversal of a binary tree starts with visiting the root node, and recursively searches down the left subtree (i.e., the tree rooted at the left node) before going to search the right subtree (i.e., the tree rooted at the right node) until the traversal is done.
Note: Alternatively, we can also look right subtree before left subtree too, for the question please consider left to right order!
A breadth-first search (BFS) traversal of a binary tree visits every node (assuming a left-to-right order) on a level (with the same distance to the root) before going to a lower level until the traversal is done.
The node-visit order of DFS is:

The node-visit order of BFS is:
5. [2pt] Fill in the blanks in the pseudo code for key search using recursive depth-first search (DFS) traversal.
class TreeNode:
def __init__(self, val): self.val = val self.leftNode = None self.rightNode = None
# (a) the left/right node is denoted as
# node.leftNode/node.rightNode
# (b) left/right node are of type TreeNode
# (c) the value of the node is denoted as node.val
# (d) recursive DFS to search for the node
# with value key in a binary tree
# (e) the left node is assumed to be searched
# before the right node
def find_val(node, key):
if node is None:
return None
if (1)____________________________:
return node
else:
result = (2)___________________________
if result is None:
result = (3)___________________________ return (4)___________________________
Consider the following information to answer questions 6-7:

Given the functions of computing a fibonacci number:
def fib_1(n): if n == 0 or n == 1: return 1
return fib_1(n – 1) + fib_1(n – 2)
d = {} d[0] = 1 d[1] = 1 def fib_2(n):
if n in d.keys():
return d[n]
d[n] = fib_2(n – 1) + fib_2(n – 2)
return d[n]
6. [2pt] Which of the following is the tightest upper bound on the time complexity of computing fib_1(n)?
Select one: O(n)
O(nlogn)
O(2n)
O(n!)
7. [2pt] Which of the following is the tightest upper bound on the time complexity of computing fib_2(n)?
Select one: O(n)
O(nlogn)
O(2n)
O(n!)
Collaboration Questions Please answer the following:
1. Did you receive any help whatsoever from anyone in solving this assignment?
Yes / No.
• If you answered ‘yes’, give full details:
• (e.g. “Jane Doe explained to me what is asked in Question 3.4”)
2. Did you give any help whatsoever to anyone in solving this assignment?
Yes / No.
• If you answered ‘yes’, give full details:
• (e.g. “I pointed Joe Smith to section 2.3 since he didn’t know how to proceed with Question 2”)
3. Did you find or come across code that implements any part of this assignment ? Yes / No. (See below policy on “found code”)
• If you answered ‘yes’, give full details:
• (book & page, URL & location within the page, etc.).