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 subtle, 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 will enable you to understand precisely why they work, and therefore in what ways the algorithms can or cannot be extended or modified to solve variations of the original task or meet other criteria.

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.

In addition to the above skills that are the primary objectives of the course, you may find that you need to acquire some more fundamental skills in applying mathematical modeling and reasoning to real-world situations, as captured by the context in your homework problems. You will have to identify what mathematical techniques you have learned previously can be brought to bear on these problems without explicit guidance. For many of you, this may be the first time you've needed to apply nontrivial mathematical reasoning outside of a math class, or the first time you've needed to solve problems without being explicitly told what technique to apply. This may be awkward and uncomfortable at first, but the mathematical perspective and such problem-solving skills are very useful even beyond the study of algorithms or CS in general. Real world problems seldom come neatly formulated with guides to their solution, and recognizing how they can be captured and solved is a set of skills that you can learn with practice. If you find yourself in this position, you may find this course particularly challenging, but these may be the most valuable skills you learn this semester.

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 and TAs will hold weekly office hours. We will also offer weekly 60-minute recitation sections. 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. You will be required to register for one of the three recitation sections. 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/spring2020/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. (Please don't post homework solutions in public Piazza posts!)

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, two midterm exams, and a cumulative final exam. You will also be assigned credit for participating in activities during lecture and recitation. The course schedule contains a tentative schedule for the homework assignments. Homeworks will be linked from the course schedule as they are assigned.

Each homework assignment will contain three problems. We will use the top two scores out of the three problems to assign a grade for your homework, and assign up to 50% extra credit for the third problem (not exceeding 100% credit total). So, concretely, your total score for the assignment will be the sum of the scores for the two highest-scoring problems plus 50% of the score on the problem with the lowest score, capped at 100% credit overall. Please keep in mind that you will be responsible for the content of all of the homework problems on the exams, so we strongly encourage you to attempt all of the problems we assign.

Electronic Submission of Homework

We will use Gradescope via Canvas 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 Gradescope 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. Everyone is automatically granted two "late days" for each assignment, for any reason. You are not required to contact course staff to use these late days. In other words, you will be allowed to submit an assignment for credit up to two days past the date indicated on the calendar and on the top of the homework assignment. But, we will not accept work submitted beyond these two days. Please note that every day or partial day that a homework is late, including weekends and holidays, counts toward its total lateness.

Any regrade requests must be submitted within two weeks after the grades for the assignment or exam are released.

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 exams to adjust for observed difficulty is at the sole discretion of the instructors. We do not anticipate curving homework grades, and we will not drop exam scores.

NEW Pass/Fail Policy

Recently the McKelvey School of Engineering updated its policy on the Pass/Fail option to allow courses taken Pass/Fail during the Spring 2020 semester to count for any degree requirements. The threshold for a "pass" will be set to the same threshold as previously required for the course to fulfill a core requirement, i.e., a C- or above (70% and up).

CSE 347
Last update: 3/22/20