15-110 Fall 2010 Homework 1
Due Sunday, 23-Jan, at 10pm

Read these instructions first!

• Include your name, AndrewID, and section clearly on the top of each file in your assignment.
• You must type your solution.  No handwritten solutions will be accepted, even if they are scanned into a document.
• That said, don't be obsessed with perfect formatting.  Any reasonable formatting will be accepted.
  
• Place all your solutions in a single file named Hw1 (with whatever extension is appropriate for the format you choose, such as Hw1.txt or Hw1.html, etc).  You must use one of these file formats (that are all readable by OpenOffice, in case you were wondering): plain text (txt), HTML (a single html file), Word (doc but not docx), OpenOffice (odt), or PDF.  No other file formats will be accepted.
• Show your work.  Correct answers without supporting calculations will not receive full credit (and in some cases will receive no credit!).

How to submit:

• Start at the course web site (http://www.cs.cmu.edu/~110)
• Select the Autolab link (which may not be active until later this week)
• Select the Hw1 link
• Select the Submit link
• Click on the “Choose File” button
• Find your Hw1 file that you are submitting
• Click on the “Upload” button
• If it worked, you will see this text:  Submission Accepted
• Your submission is not completed until you see that text!!!
  

Q & A
 Q:  Can I submit multiple times before the deadline?
 A:  Yes, but only the last submission is graded.
 Q:  Can I submit if I am waitlisted and not yet enrolled?
 A:  Yes.
 Q:  What if I’m having problems?
 A:  Email your recitation CA’s.  They will help you!
 Q:  Are submissions that are just a few seconds late ok?
 A:  No, they are late.  The deadline is exact, according to Autolab's clock (not yours!).
 Q:  What happens if I miss the deadline?
 A:  You then have 24 hours from the first deadline to submit with a 25-point penalty.  That deadline is also exact.
 Q:  What happens if I miss that second deadline?
 A:  You then receive a 0 for the assignment.
 Q:  How do I get my grade and the graders’ comments?
 A:  Go back to Hw1 in Autolab and select “view scores”.

---

0. AndrewID
   List the first 3 letters of your andrew id in easy-to-read upper case.
   
   
1. Representation  [25 pts]
1. ASCII  [3 pts]
   Convert the 3 letters in the previous answer to 3 integers using ASCII (call these i1, i2, and i3).
   
   
2. Decimal-to-Binary  [5 pts]
   Convert i1 to binary (8-bit unsigned binary, to be exact).  Show your work.
   
   
3. Binary-to-Decimal  [5 pts]
   Find i4, which is the product of i2 and i3.  Then, construct the binary number b4 as follows:  replace each odd digit in i4 with a 1, and each even digit in i4 with a 0.  For example, if i4 was 512348, then b4 would be 110100.  Finally, convert b4 to decimal.  Show your work.
   
   
4. Short Answers  [12 pts]
   
1. [4 pts]  RGB values usually range from 0 to 255.  Now, 255 seems like a strange number to use as the maximum value of this range.  Explain why 255 actually makes sense.  Hint: think binary.
   
   
2. [4 pts]  Say you have a huge sequence of 1’s and 0’s.  Of course, we cannot know what those values represent -- maybe a string (well, maybe a novel), maybe a picture, maybe something else.  But with some thought, we may be able to make an educated guess if it is in fact a novel.  What kind of analysis might we do to figure that out?
   
   
3. [4 pts]  Say there was a new kind of computer that somehow stores one of three values in each “bit” of memory instead of two.  Can this amazing invention be used to represent new kinds of things that could not be represented using conventional digital computers?  Explain.
   
   
2. Knights-and-Knaves  [25 pts]
1. 2-Person Knights-and-Knaves   [12 pts]
   Find i5, which is the remainder when you divide i4 (from the previous problems) by 20.  Then, find i6, which is i5 plus 2.  Then, solve the 2-person Knights and Knaves puzzle number i6 (so if i6 equals 18, for example, you would solve Knights and Knaves puzzle #18 -- be sure to type this number into the dialog box at the bottom so you see "This is puzzle number 18" (or whatever number you are expecting)!).  Show your work using the same approach and same format we used in the class notes on Knights and Knaves.
   
   Note:  The Knights and Knaves puzzle page apparently has trouble with some browsers (like Chrome).  If you are experiencing difficulty, try another browser (Firefox, Safari, IE, etc).
   
   
2. 3-Person Knights-and-Knaves   [13 pts]
   Find i7, which is the product of i1 and i2 and i3 (from the previous problems).  Then, find i8, which is 52 plus the remainder when you divide i7 by 20.  Then, solve the 3-person Knights and Knaves puzzle number i8.  Again, show your work using the same approach and same format we used in the class notes on Knights and Knaves.
   
   
3. Sorting  [25 pts]
1. Selection Sort  [12 pts]
   Write the numbers i8, i7, …, i1 (from the previous problems) in a list (so i8 is first, i1 is last).  Then sort the list into increasing order using selection sort (use the version that finds the min on each pass, and not the max).  Each time the algorithm would swap two items, highlight (in some obvious way) those two items and write a new list below with the items swapped.  Continue in this fashion until the list is sorted.
   
   
2. Merge Sort  [13 pts]
   Once again, write the numbers i8, i7, …, i1 in a list (so i8 is first, i1 is last).  Then sort the list into increasing order using merge sort.  Each time the algorithm would copy all the items back into the original list, just write that new list below.  Continue in this fashion until the list is sorted.
   
   
4. Readings in Computational Thinking  [25 pts]
• For each of these questions:
• Carefully read the entire articles, not just the parts required to answer the questions.
• Note that any part of the articles may appear on a future quiz or test (so do read them in full).
• Do not copy or quote any text from the articles.  Instead, restate them in your own words.
• Provide well-written, coherent, and concise paragraphs and not just single-word or bullet-list answers.
  
  
1. Computational Thinking  [9 pts]
   Read Computational Thinking by Jeannette Wing.  The article says “Computational thinking thus has the following characteristics”.  List those characteristics  (for this you may quote the italicized text in the article).  Then, in your own words, expound on any one of these characteristics (say, how does it apply to your area of study? Or how does it affect your daily life?  Or any other interesting extension of the article), providing at least one concrete example to support your claims.
   
   
2. CAPTCHA's  [8 pts]
   Jeannette’s article refers to “CAPTCHA’s” (invented at CMU!).  Read the Wikipedia page on CAPTCHA’s.  That page says that CAPTCHA’s are something of a Reverse Turing Test.  Explain in your own words what that means.
   
   
3. eTeRNA  [8 pts]
   Read the New York Times article: “RNA Game Lets Players Help Find a Biological Prize”.  Explain in your own words how eTeRNA is trying to leverage humans as computing agents to solve important questions in biology.
   
   
5. Bonus/Optional:  Arithmetic as Logic   [5 pts]
   This bonus activity serves two purposes:  (1) to expose you to interesting, somewhat more challenging concepts that extend the topics covered in this assignment; and (2) to give you a sense of what the Honors mini will be like (as it will follow this same basic format, with about the same rigor).  Total time invested in this activity should be around 1.5 to 2 hours (which is about half the expected time for future Honors assignments), and you must complete the entire activity to receive credit.
   
   
1. Bonus Lecture
   A lecture covering this week's bonus topics will be presented on Tuesday 18-Jan at 4:30pm, and should last about 30 to 45 minutes (again, about half the expected time for future Honors lectures).  Attendance is encouraged but not required (and space may be limited, so we will have a sign-up sheet for those interested).  A video of the lecture will be made available (perhaps online or perhaps via DVD's to loan).  If you do not attend the lecture, then watch this video (in its entirety and with the same focused attention that you would have in the classroom).  Also, here are the lecture notes.
   
   
2. Bonus Assignment
   Note #1:  For this assignment, you will create and submit circuits using xLogicCircuits.  In order to be able to save your work, you will have to use the offline version (and not the applet), which you can obtain here.
   
   Note #2:  In the bonus lecture, we said you shoud use screenshots to save your work.  Untrue.  Instead, you should use the offline version so you can save your work into text files.  Much nicer (not only are these smaller, but you can reload them later for your own use, plus we can load them to test them while grading).
   
   Note #3:  Since the bonus portion includes more than one file, you will have to submit them along with your main Hw1 solution file in a single zip file.  To do this, put all your answers in a single folder, then zip that folder and submit the zipped folder (which is a single file at that point).  If you do not know how to do this, ask your CA for help.
   
   
1. Construct a truth table for (A = B), then convert the expression into Disjunctive Normal Form.  Show your work.
   
   
2. Create a circuit for your answer to the previous question.  Store this in the file EqualsUsingAndOrNot.txt.
   
   
3. Using DeMorgan's Law, convert your answer to #1 into an expression using only "or" and "not" (no "and").  Replace (not not X) with X where appropriate.
   
   
4. Create a circuit for your answer to the previous question.  Store this in the file EqualsUsingOrNot.txt.
   
   
5. We covered addition in the lecture, so let's do subtraction here.  Construct a logical expression using only and/or/not (hint: think DNF) that computes the signed difference between two unsigned one-bit numbers.  As the result can be negative, we will represent the result in sign-magnitude using 2 bits.  The leftmost bit of the answer is the sign bit, which is 0 if the number is non-negative, and 1 if the number is negative.  The rightmost bit of the answer is the magnitude.  So, for example, 01 equals +1 and 11 equals -1.  We'll take 00 to mean 0 and 10, which technically means -0, will be unused.  So this has 2 bits of input:  A B (representing two unsigned one-bit numbers), and 2 bits of output:  C1 C2 (representing one signed two-bit number C).  Be sure that C = A - B, the signed difference between A and B.  Show  your work.
   
   
6. Create a circuit for your answer to the previous question.  Store this in the file SignedDifference.txt.
   
   
7. To construct a 32-bit adder, we used 32 daisy-chained full adders.  Instead, we could have gone back to first principles and constructed a 32-bit adder using DNF.  Explain in precise terms why this is impractical.
   
   
8. In a short paragraph, in your own words, and avoiding technical jargon as much as possible, explain the Big Ideas of this week's bonus lecture in a way that might be consumed by a non-technical audience.