Algorithms and Complexity

Spring 2014

Dr. Stephen Bloch

Post Hall 213,
phone 877-4483,
email `sbloch@adelphi.edu`

Web page `http://www.adelphi.edu/sbloch/`

Class Web page `http://www.adelphi.edu/sbloch/class/344/`

office hours TBA

This is a course for anybody who's ever complained about a computer
being slow. When faced with a computer program that takes unacceptably
long to solve the problem at hand, one option is to buy faster, more
expensive computer hardware. But this option has its limits: perhaps
your money will run out, or perhaps you'll upgrade to the fastest
computer on the market and still be unsatisfied. Often a better option
is to find a more efficient approach to the problem -- to re-think the
*algorithm* so that it makes *better use* of the hardware.
A $1,000 personal computer running a good algorithm can often outperform
a $1,000,000 supercomputer running a bad (though correct) algorithm.

In this course we'll learn how to measure the efficiency of an algorithm,
independent of language, operating system, or hardware. We'll survey a
variety of techniques for designing efficient algorithms.
(Many of these techniques
will help you program correctly even when you're not worried about efficiency.)
We'll even learn how to prove that a given algorithm is “as good as it
can get,” in the sense that *no* algorithm, no matter how clever,
will *ever* be better than this one.

Near the end of the semester, we'll study problems believed to have
*no* efficient solution by computer program,
and even some problems which have *no computational solution at all*,
and how we deal with such problems in reality.

This is a course about problem-solving, and that's how I'd like to spend most of our class time: discussing a problem, suggesting and critiquing ways to solve it.

I've chosen two textbooks to use throughout the two-semester sequence: they cover a lot of the same topics, but sometimes I like one author's treatment better than the other's.

One is the “bible” of algorithms and data structures,
*Introduction
to Algorithms* by Cormen, Leiserson, Rivest and Stein (MIT Press
2009, ISBN 0262033844).
(The “Rivest” author is the R in the RSA cryptosystem, by
the way.)
It's a big, thick book, but relatively inexpensive, because
there's not much
second-hand market for it: once you've bought it, you'll
probably refer to it
for the rest of your programming career. If you really don't want
to buy the big
hardback, the second edition (and several hundred other books) is
*free on-line* to
ACM Student Members. I highly recommend that all CS majors become
members of the ACM: at $19/year, it's an incredible bargain.
The second edition is about 90% the same as the current third edition;
I'll try to have a copy of the third edition on reserve at the
library.

The other textbook is Cliff Shaffer's *Data Structures and
Algorithm Analysis* (Dover 2012, ISBN 0486485811). You can buy a
printed copy,
but it's also available free on-line from
`http://people.cs.vt.edu/~shaffer/Book/`
(in either a Java or a C++ edition).

I may also give out other reading assignments by email, on the Web, or in journals.

This is a 3-credit class, which means you should budget 6 hours per week
outside class for reading and homework. In particular, you'll need to
read about 30 pages per week, on average.
*Make time in your weekly schedule for this!*

I assume that everyone in the class has passed CSC-MTH 156 (Discrete
Structures) or an equivalent course covering Boolean logic and algebra,
graphs and trees, and perhaps recurrence relations. I also assume that
everyone in the class has passed at least a year of programming courses;
I don't care about the language, as long as you have written and debugged
a number of programs and are familiar with the notions of algorithm,
recursion, loop, array, linked list, *etc.*

Most of the students in this class took CSC 343 last semester, but every year there are a few students who take the two courses in the opposite order, and that's OK. There's a bit of overlap between the courses, and it's important enough that I don't mind covering it twice.

The majority of your semester grade is based on written homework and in-class presentations of it. There will be probably 5 written homework assignments and a final exam.

The final exam must be taken at the scheduled time, unless arranged in advance or prevented by a documented medical or family emergency. If you have three or more exams scheduled on the same date, or a religious holiday that conflicts with an exam or assignment due date, please notify me in writing within the first two weeks of the semester in order to receive due consideration. Exams not taken without one of the above excuses will be recorded with a grade of 0.

For each homework assignment, I've allocated two days in the class
schedule. The homework assignment is due at the beginning of the
first of those two class meetings, and the rest of those two classes
will be devoted to student presentations of homework solutions.
*No later than the previous class meeting*,
choose one or two problems from the assignment
that you'd like to present to the class, and confirm your choice with
me. (I don't want three different students presenting the same problem,
so first-come, first-served.) On the scheduled presentation day, try to
get to class a few minutes early and start writing your solution on the
board; you will be expected to explain your solution orally, and answer
technical questions about it from me and from your classmates.
If you're not sure of your
solution or your presentation, feel free to discuss it with me in my office
before the day you want to present it in class.
Your grade for in-class presentations will be my assessment of how well you
presented a solution and answered questions about it.
Homework assignments will *not* be
accepted late, since you've just seen other students' solutions to
several of the problems; however, if you haven't finished all the
problems, turn in the ones you've got.

For all but the last homework assignment, you are invited to *rewrite
and resubmit* within a week after you get it back graded.
Your recorded grade will be MAX(original grade, 0.8 * revised grade),
so there's no point resubmitting if you got above 80% the first time
around; this policy is most helpful if (for whatever reason) you did
really poorly on the initial submission.

There will be several kinds of homework in this class. At one extreme
are the analysis and “thought” problems on paper,
resembling problems
in a math class. At the other extreme are programming assignments,
which may be written in any language that you and I both know and that
runs at Adelphi (*e.g.* Scheme, Prolog, Java, C, C++). In between
are *pseudocode* assignments: these need to be precise descriptions of
an algorithm, like a computer program, but they don't need to meet the
syntactic requirements of a compiler (only a human being will read them)
and you can ignore details that aren't relevant to the problem at hand.
For example, in a problem that wasn't primarily about sorting, you might say
“sort table A in increasing order by value” as one line of the algorithm.
On the other hand, if the assignment *were* about sorting, I would
expect you to give the details of your sorting algorithm.

The Adelphi University Code of Ethics applies to this course; look it up
on the Web at
`http://academics.adelphi.edu/policies/ethics.php`.

Assignments in this class are to be done individually or in teams of two.
You may *discuss general approaches* to a problem with classmates, but
you *may not copy* large pieces of programs or homework solutions.
If you do, *all* the students involved will be penalized
(*e.g.* I'll grade the assignment once and divide the points
equally among the several people who turned it in).

All work on an exam must be entirely the work of the one person
whose name is at the top of the page. If I have evidence that
one student copied from another on an exam, *both* students will be
penalized; see above.

This class meets every Monday, Wednesday, and Friday from 12:00-12:50
PM in Harvey 107, unless we agree to change that.
The schedule of topics, reading assignments, and homework assignments will
be maintained on the Web at
`http://www.adelphi.edu/sbloch/class/344/calendar.html`.
The dates are
subject to change depending on how classroom discussions actually go.
I expect you to have read the reading assignments
*before* the lecture that deals with that topic; this way I can
concentrate my time on answering questions and clarifying subtle or
difficult points in the textbook, rather than on reading the textbook
to you, which will bore both of us. **Please read ahead!**

Last modified:

HTML conversion by TeX2page 20070609