CS W1001-01 Introduction to Computer Science

Homework 1 (10 points)

Algorithms, Boolean Logic and Spreadsheets



Due Date:

Tuesday, February 8. Homework is due at the beginning of class on the day of the deadline. If you use one of your "late days" (recommended to be saved until the later, more difficult homeworks), or are late due to an extenuating circumstance (e.g., medical) that you have established with your TA, it is your responsibility to get the hardcopy directly to your TA (e.g., during office hours or by an appointment you establish with your TA via email).

All of the homework below must be submitted by hardcopy (i.e., a physical piece of paper). Place your TA's name on the upper-right corner of the hardcopy. Furthermore, the spreadsheet portion will also be submitted electronically, but not by email -- the course web page will provide directions for this before the due date. The electronic version is due before class of the due date.

These will be the policies for all homeworks this semester.

Reading:

"An Invitation to Computer Science," Chapter 2, Chapter 4 up through Section 4.3, and Sections 11.1 and 11.2 on Spreadsheets (however, you are not responsible for section 11.2.4 at this point). Also read "The Stable Marriage Problem" by Harry Mairson (handed out in class, but also available on the web off the course web page).

Algorithm theory questions (3 points)

  1. Chapter 2, exercise 12
  2. Chapter 2, exercise 13
  3. Chapter 2, exercise 15 (cf. exercise 13 for definition of "unique")
  4. Describe in English (or pseudo-code, if you like) an algorithm to find the second-to-largest value in a list of numbers. Note that this is similar to the Find Largest Algorithm, but will be a little more complicated. If your answer is given in English, it should be no more than 8 or 9 sentences in length! You may assume the input never has repetitions, i.e., all numbers are unique.
  5. After performing or executing or running or doing the Stable Marriage Algorithm for a town with 100 women and 100 men, what is the maximum number of people with their first choice? What is the minimum number of people with their first choice? What is the maximum number of unstable marriages? What is the minimum number of unstable marriages? Explain your answers, at most one sentence per answer.
  6. When performing the Stable Marriage Algorithm for a town with n women and n men, can more than n times n times n proposals take place? More than n times n? More than 2 times n?

Binary numbers and boolean logic theory questions (3 points)

  1. What is the value of the binary number 10110101 expressed in base-10 (i.e., decimal)? Show your work.
  2. Chapter 4, exercises 3, 4, 9, 11 and 12. Show your work.
  3. Make the truth table for (a AND b) OR (NOT c)
  4. Draw a circuit of gates for (a AND b) OR (NOT c)
  5. Chapter 4, exercise 13. You do not have to use the algorithm mentioned in this problem (it is not part of the assigned reading) -- rather, find a solution in any way you like. Show the boolean expression (that is, an expression like that in the previous question) as well as the circuit of gates. It is probably easier if you do the boolean expression first.

Hands-on with a Spreadsheet (4 points)

email: evs at cs dot columbia dot edu