CS W1001-01 Introduction to Computer Science
Homework 1 (10 points)
Algorithms, Boolean Logic and Spreadsheets
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.
"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)
email: evs at cs dot columbia dot edu
- 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
These directions are mostly for your own learning purposes, but
they include asking you to add a column, which you are required
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.
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.