This course introduces the mathematical analysis of algorithms. An
algorithm is a procedure for solving a problem, expressed in a way
that can be effectively implemented on a computer. Useful algorithms
are both **correct** and **efficient** -- they produce the right
answer and run in a reasonable amount of time/space as a function of
the size of the problem being solved.

We will study a number of different types of algorithms, such as
divide-and-conquer, greedy, and dynamic programing. Our goals are to
understand why these methods work and how to quantify their
efficiency. "Efficiency" in computer science is traditionally measured
as the worst-case time for an algorithm to process any one input of a
given size. However, in some contexts, other measures of efficiency
may be more useful, such as average-case efficiency, amortized
efficiency over a large number of inputs, or competitive efficiency
relative to some other algorithm. Also, clever use of random numbers in
an algorithm may allow us to guarantee efficient execution "most of
the time," *regardless* of the input. Finally, some problems
are *intractable*; that is, they are inherently resistant to
efficient implementation. We'll introduce the study of intractability
and how to tell when a problem is likely intractable.

Because algorithms and their analysis can be technically complex,
trying to understand their behavior based solely on informal arguments
(sometimes called "hand-waving") is fraught with peril. The safest
way to avoid being wrong is to pursue rigorous correctness and
efficiency arguments (i.e. proofs). We will strive for mathematically
rigorous argument, both in class and on your assignments.
*An important part of learning about algorithms is learning how
to argue rigorously about their behavior*; this class will give
you lots of practice to help build up your "CS theory muscles."

After successfully completing this class, you should be able to
understand and rigorously analyze a wide variety of algorithms
encountered in practice. You should also be able to articulate what
it means for a problem to be intractable, to recognize intractability
in some cases, and to propose approaches to make progress on
intractable problems. The skills you gain will be particularly
important if you have occasion to design your own algorithms in the
future; however, *everyone* in CS should be an "informed user" of
algorithms.

Informally, 347 demands that you develop "mathematical maturity" -- the ability to read, understand, and produce rigorous mathematical arguments (i.e. proofs). We will use basic logical techniques such as induction, proof by contradiction, and proof by cases extensively, as well as elementary probability and combinatorics. You will practice communicating your ideas in the form of proofs through your classroom interactions, recitation sections, and homeworks.

We will use Jon Kleinberg and Eva Tardos's
*Algorithm
Design*. This is a required text -- some of the homework
problems will be assigned from it. The
course schedule indicates which
sections of the text correspond to each class meeting.

Besides our regular class meetings, the instructors, TAs, and graduate
recitation leaders will hold weekly office hours. We will also offer
weekly 90-minute *recitation sections* led by CS graduate
students. In recitation, you will have the opportunity to work in
small groups on solving computational problems and analyzing your
solutions, and on communicating your analysis in the form of
proofs. *We strongly recommend making time to regularly attend
recitation*, particularly if you have little prior experience with
rigorous mathematical proof.

You can also interact with us through the class discussion board,
which are hosted on *Piazza*. We will also use Piazza to
maintain up-to-date information about office hours and to post class
announcements. The Piazza board for this class is located at
piazza.com/wustl/fall2017/cse347/home.

All students will be automatically signed up for Piazza by the start of class. If you have not yet registered on Piazza, you should receive an email inviting you to join. Please register as soon as you receive the e-mail, if you haven't already.

**You should use Piazza for all questions not of a personal or
confidential nature.** Your posts will be seen by the instructors,
the other course staff, and (if you don't make your post private) by
your fellow students. You will find it helpful when your classmates
have already asked a question for you -- in fact, someone may already
have answered it! But, in order to sustain this, you must ask your
questions to Piazza as well.

Because 347 is a large class, and your instructors and course staff
already have very full email in-boxes, **we will strictly enforce a
policy of responding only to class questions posted via Piazza**.
Please email your instructors only for personal emails (e.g. letting
us know about an illness or absence) or confidential matters
(e.g. accusations of collaboration policy violations). If you have a
question about homework or class logistics that you don't want to
share with the class, please post it to Piazza, but make your post
private.

Students with documented disabilities are strongly encouraged both to bring any need for accommodation to the attention of the instructors and to make full use of the University's disability resources and accommodations.

Tentatively, there will be 10 weekly homework assignments (plus a shorter homework 0), a midterm exam, and a cumulative final exam. The course schedule contains a tentative schedule for the homework assignments. Homeworks will be linked from the course schedule as they are assigned.

We will use Blackboard for paperless homework submission. To allow
for electronic submission, grading, and enforcement of the
collaboration policy, *we require that you prepare your homework
using a word processor or typesetting program, rather than
hand-writing it*. (You can, however, hand-draw and scan in figures
as part of your solutions.) You can read about how to typeset your
homework, including math and figures, and the rules and procedures for
submission, in our
E-Homework Guide.

Typesetting your homework takes a little more time, at least initially, but you will find it helpful for problem solving. We don't hand-write papers anymore because word processors offer huge advantages in terms of editing your work, particularly rearranging, reusing, and replacing pieces over time. Think of your homework solutions as mini-essays (which, in a certain sense, they are!), and you'll see why it might be helpful to write them electronically. Don't try to hand-write a beautiful solution and then typeset it at the last minute -- use your word processor or editor to capture your ideas and compose a solution as you go.

Homework will be due at 11:59PM on its due date. If all problems for a given homework are not uploaded and submitted through Blackboard by this deadline, the entire homework will be considered late. Homeworks turned in fewer than 24 hours after deadline are one day late; those turned in at least 24 but less than 48 hours after deadline are two days late; and so forth.

The following policy applies to homeworks turned in late. You begin
the semester with a total of six (6) "late days," each of which may be
used to cancel out one day of lateness for one homework without
penalty. *At most two (2) late days may be used for any one
homework.* For each day that a homework is late which is not
canceled out by one of your late days, your score on that homework
will be penalized by 25% of its *total* possible points. For
example, if a homework is worth 100 points, and your "natural" score
is a 93, but you turned it in up to 24 hours after the deadline (i.e.,
one day late), your final score would be 93 - 0.25 * 100 = 68.

Please note that every day or partial day that a homework is late, including weekends and holidays, counts toward its total lateness.

Please see this page for the policy.

The goal of homework is for you to practice the reasoning and analytical approaches that we develop in class to understand new algorithms and design and analyze novel variations on the methods we've studied. Through these homeworks, you will develop your problem-solving skills, learn to recognize which among many possible analytical techniques can be applied, and enhance your ability to communicate clearly in the language of theoretical computer science. Results proved in homework may sometimes be used later on in the course to support new material that we discuss in class.

Algorithms homework can be challenging. Often, you may have to think
about a problem and try alternative approaches for a while before you
can make progress. You might have to put the problem down and come
back to it later. You might intuitively see how to proceed but have
difficulty articulating or justifying your approach formally. *These are
normal parts of the problem-solving process*, and you will get better
at it over time.

Two things to keep in mind are that (1) *we don't expect you to come
up with all of the insights necessary to solve every problem by
yourself*, and (2) *give yourself enough time to do the
homework*. Within the limits of the course
collaboration policy, we encourage
you to work on problems in groups, and to consult appropriate outside
sources. If you get stuck, you can talk to an instructor or other
course staffer or post to Piazza, so that we can try to steer you
toward the next step in the solution.

In order to have sufficient time to work with your peers, seek help,
and prepare your solutions, *please start your homework early, and plan to
devote significant time to it over the week*. Leave yourself time
to ask questions, to talk to others, and to put a problem down and
come back to it. Don't assume that you can do the whole thing in one
sitting.

The breakdown of your final grade will be as follows:

- homework - 45%
- midterm exam - 23%
- final exam - 32%