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)

Chapter 2, exercise 12
Chapter 2, exercise 13
Chapter 2, exercise 15 (cf. exercise 13 for definition of "unique")
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.
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.
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)

What is the value of the binary number 10110101 expressed in base-10 (i.e., decimal)? Show your work.
Chapter 4, exercises 3, 4, 9, 11 and 12. Show your work.
Make the truth table for (a AND b) OR (NOT c)
Draw a circuit of gates for (a AND b) OR (NOT c)
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)

Copy the file ~es66/W1001/example.xls to your home directory (why not put it in a new sub-sub-directory for HW number 1?).
Follow the attached directions to use Excel on this file of student grades. These directions are mostly for your own learning purposes, but they include asking you to add a column, which you are required to do. The directions are stapled to this page if you got this handout in class. If for some reason you did not get the handout but rather are reading this on the web, you need to get a copy of the additional material on spreadsheets from me directly (or from another student in the class). Excel is available in the applications folder on the MacIntosh computers in 251 Mudd. Or, you can get into "Windows mode" on the Sparcs in 251 Mudd.
Next, make new columns for midterm and final exam grades for the class. Make up values for each student and enter them. For example, I'd assume that any student by the name of Victoria would probably get a 100 on the final, wouldn't you?
Now, assuming that the labs, midterm and final are each worth one third of the overall course grade, add another column that automatically computes the final percentage semester grade for each student. Repeat the steps you did above to get each student's letter grade, but this time for the average that includes exam scores.
Print out the pie chart for these new letter grades.
Now expand the row of values at the bottom labeled "Averages", each item being the average value of the numbers above it in the same column. This way, we can see the average score on each lab, the average midterm and final scores, and the average final course percentage grade over all students.
Print out the spreadsheet, and save the file. On the hardcopy, write the spreadsheet formulas. The course web page will tell you how to electronically submit your file before the due date.
Note: after you hand in this and all assignments, keep the files you made on your account (don't erase them). This semester, later homeworks may build on earlier ones.

email: evs at cs dot columbia dot edu