Announcements
- Starting with the homework that is due on Monday September 8, you
must use LaTeX to prepare
your homework solutions. You can hand draw pictures if you like. But
you must use LaTeX for the text.
- Please join the course group http://groups.google.com/group/cs-1510
The group email address is: cs-1510@googlegroups.com.
This group should be used for questions of general interest. You need
not reveal you identity, so your questions are confidential.
- Bill Gates quote on Computer Science Education from an interview
(local copy)with Maria Klawe:
- Well, certainly it's the goal of our University
Relations Group to make sure that we're talking about what we think the
state of the art problems are, finding out from the universities and a
lot of dialogue back and forth about that. In a certain sense, yeah,
the curriculum has changed, but say somebody came for an interview and
they said, "Hey, I read the 'Art of Computer Programming', that's all I
ever read, I did all the problems, I would hire them right then."
Even if they didn't do the double-star problems, I mean, just the fact
that they'd read the whole book, you know, those are the kinds of
things you need to know to be a good programmer. Actually, there's some
of that you don't even need to know, but the kind of algorithmic
thinking that's promoted there.
- A Microsoft interview?
- Another cartoon. Thanks to Andrew.
Reading Assignment
- Syllabus
- Chapter 4 on greedy algorithms.
- Chapter 3 on dynamic programming.
- Chapter 9 on computational complexity, reductions, NP-hardness,
and approximation algorithms.
- Chapter 10 on parallel algorithms
- Section 7.8 and Chapter 8 on lower bounds and adversarial
arguments.
Notes
Disclaimer: These are intended to to be minimal notes for those
missing class, etc. They are not meant as an equal substitute for
either
the text or for attending class.
Homework Problems
An explanation of the problem difficulty rating can be found
here .
Homework Assignments
- Due Wednesday August 27:
Google " Google interview questions"
and " Microsoft interview questions".
Turn in three purported interview questions that are "algorithmic" in
nature. Also due is Greedy Homework Problem 1.
- Due Wednesday September 3: Greedy homework problems 2, 3 and 4
- Due Monday September 8: Greedy homework problems 5, 6, 7, and
8. Starting with the homework that is due on Monday
September 8, you must use LaTeX
to prepare your homework solutions. You can hand draw pictures if you
like. But you must use LaTeX for the text.
- Due Wednesday September 10: Greedy homework problems 9, 10, and 11
- Due Monday September 15: Greedy homework problems 12, 13, and 15
and maybe some dynamic programming problems. Note problems were
renumbered on Sept 3.
Old Tests
- 1995(postscript): Midterm
1 ,
Midterm 2 , Midterm 3
,
Midterm 4 .
- 1996(postscript): Midterm
1 ,
Midterm 2 , Midterm 3
.
- 1997 (html):
Midterm 1 ,
Midterm 2 .
- 1998 summer (html):
Final .
- 1998 (html):
Midterm 1 ,
Midterm 2 .
- 1999 (html):
Midterm 1 ,
Midterm 2 .
- 2000 (html):
Midterm 1 .
Midterm 2 .
- 2001 (html):
Midterm 1 .
Midterm 2 .
- 2002 (html):
Midterm 1 and Midterm 2.
- 2003: Midterm 1, and Midterm 2, and Midterm 3, and Midterm 4.
- 2005: Midterm 1 and Midterm 2
WWW Resources
If you find any good sources of information on the WWW, related
to what we're doing in class, I'd appreciate if you would let me know.