Overview of CSE 347 Analysis of Algorithms

Contents

Course Goals and Content

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.

Prerequisites

Formally, this class requires CSE 247. In particular, we expect that you are familiar with notions of asymptotic worst-case complexity and how to measure it, as well as basic data structures and fundamental methods for computational tasks such as sorting, maintaining dictionaries and search indices, and graph traversal. We also expect that you can make simple arguments in support of algorithmic correctness and complexity, at the level done in CSE 240 and 247.

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.

Textbook

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.

Opportunities to Interact and Seek Help

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.

Disability Resources

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.

Assignments and Grading

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.

Electronic Submission of Homework

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.

Deadlines and Late Homework Policy

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.

Collaboration and Academic Integrity Policy

Please see this page for the policy.

Homework Advice

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.

Breakdown of Final Grade

The breakdown of your final grade will be as follows:

Any curving of assignments to adjust for observed difficulty is at the sole discretion of the instructors.