MA/CSSE 473 Design and Analysis of Algorithms

Instructor info

Instructor	Claude Anderson
Office Phone	877-8331
Office Address	F210 (Northeast corner, top floor of Moench)
Office Hours	I am generally available all day when I am not in class or meetings. You can find my schedule at: https://calendars.office.microsoft.com/pubcalstorage/grpzhl8z192733/Anderson_Claude_W_Calendar.htm
E-mail	anderson@rose-hulman.edu

Required Text

The Design and Analysis of Algorithms, 2nd Edition by Levitin (Addison-Wesley, 2007)

Approximate reading schedule

Weeks 0-1	Review, Overview of Data Structures, Algorithms and their analysis	Chapters 1-3
Weeks 2-3	Divide-and-Conquer, Decrease-and-Conquer, Transform-and-Conquer	Chapters 4-6
Weeks 4-6	Space-Time Tradeoffs, Dynamic Programming, Greedy Technique	Chapters 7-9
Week 7	Iterative Improvement	Chapter 10
Weeks 8-9	Limitations of Algorithmic Power, Heuristic and Approximate Algorithms	Chapters 11-12
Week 10	Overflow, miscellaneous algorithms

Other Books

A book that I recommend for every Computer Scientist's library:
Grimaldi, Ralph P. Discrete and Combinatorial Mathematics (Addison-Wesley, 2003)
Other good books on Algorithms:

Algorithms by Dasgupta, Papadimitriou, and Vazirani (McGraw-Hill, 2008)
Algorithms by Johnsonbaugh and Schaefer (Prentice-Hall, 2004)
Algorithms in Java by Sedgewick (Addison-Wesley, 2004)
This book is available online, through Safari. You can access it by going to the Logan Library web page and finding Safari in the Databases area near the top of the page.
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (MIT Press, 2001)
Data Structures and Algorithm Analysis by Weiss (Addison-Wesley, 2007)

Course Description

Catalog Description

Students study techniques for designing algorithms and for analyzing the time and space efficiency of algorithms. The algorithm design techniques include divide-and-conquer, greedy algorithms, dynamic programming, randomized algorithms and parallel algorithms. The algorithm analysis includes computational models, best/average/worst case analysis, and computational complexity (including lower bounds and NP-completeness).

Instructor's Description

This course is a study of algorithms, including their design, analysis, and proof of correctness. A large portion of our time (in and out of class) will be spent solving problems. There will also be some implementation exercises, but they will play a lesser role than in CSSE 230. Students will also present solutions in class and/or lead class discussions of problems.

Prerequisites

CSSE 230 Data Structures and Algorithms MA 375 Discrete and Combinatorial Algebra II

This course will include quick reviews of the following topics. But if you did not understand them from the previous courses, you will need to do some extra review work on your own:

Elementary data structures and their associated algorithms (stack, queue, list—linked and sequential, tree, binary search tree, priority queue—and its heap implementation, set, hash table, graph)
Basic proof techniques, including proof by contradiction, contrapositive, and mathematical induction
Elementary tools of analysis, including summations, integrals, inequalities, logarithms, counting techniques, big-oh and its cousins big-theta, etc., recurrence relations
Reading, using, and adapting mathematical notation
Simple programming techniques, including functional decomposition, recursion, iteration, arrays, references, pseudocode

The main things that you should bring into this course

enthusiasm, curiosity, perseverance, and a "can do" attitude
willingness to work cooperatively with other students (inside the classroom and out) to enhance the learning environment for everyone
willingness to consistently devote enough time to the course
commitment to read the textbook and get all you can from it, so that more class time can be spent on problem solving
commitment to avoid getting behind, and to ask questions when you don't understand something
a reasonable comfort level with elementary discrete mathematics (including proofs)
ability to work as an independent programmer; i.e., to be able to design, code, and debug solutions to simple and medium-difficulty problems without a lot of help from others

Instructor's Course Objectives

Increase student appreciation for the value of theoretical Computer Science
Increase student understanding of mathematical tools from previous courses by applying them to algorithm analysis
Enhance student ability to create and present proofs and mathematical arguments
Expose students to various classes of algorithms with applications to a variety of mathematical disciplines
Give students an understanding of major classical approaches to algorithms, increasing their ability to choose the best kind of algorithm for a specific need
Help students understand some limitations of computer algorithms via the study of NP-complete problems

Course Requirements

The nature of the assignments

One small component of your Assignments grade will be occasional Readiness Assessment Tests (also known as quizzes, which will not always be announced in advance) over reading assignments, to make sure that you have prepared for class. Also written exercises (some in class, some to be done at home), and in-class discussions of homework problems, and possibly some programming exercises.

When I give a reading assignment, I seriously expect you to read it. In-class discussions will assume that you have done the reading and understood the "easy stuff" before class. You may of course ask about any details that you do not understand. I strongly believe that reading the textbook will help you; sometimes there may be an ANGEL quiz that covers a reading assignment.

I will assign some written problems, many of them from the textbook. They will usually be short thought problems, mathematical analyses, formal proofs, or algorithm-design exercises. I expect you to think through them carefully and write your answers legibly and clearly (if you can't write it neatly, type it). On some problems, not only the correctness but also the quality of your solution will determine your grade. Some of the problems will be straightforward practice with concepts from the course; others will require creative solutions. Don't put them off until the last minute!

The usual pattern will be that problems assigned on Fridays will be due at the beginning of the following Tuesday's class, and problems assigned on Tuesdays will be due on Friday. There may be some exceptions due to exams, Fall break, or problems that are difficult enough to require more time. But you can always count on at least that much time between problem assignment and due date.

In general, you may communicate with other students about the problems, and work out solutions together. But when you write it up to turn it in, you must do it on your own without reference to things that you wrote together. You should also acknowledge the collaboration in writing on the paper that you submit.

The textbook has exercises at the ends of the sections; Almost all are likely to be helpful; obviously I cannot assign all of them. For many of those problems, reading and thinking about them will be instructive, even if you don't have time to fully solve them. I recommend that you read them all, regardless of whether they are assigned.

Your solutions to programming problems should be well-designed and well-documented. If you do a problem with someone else (which will be most likely be allowed), it is your responsibility to not allow anyone's name (including your own) to be placed on the submitted program if that person does not understand the solution. Before submission, you should try compiling and running what you are going to submit, so that you can be sure that you did not leave out any necessary files.

At the time that I write this, I have not been able to find a grader for the course. If I cannot remedy this situation, I may need to adopt an unusual policy: select a subset of the problems on each assignment for grading, then include one or more of the homework problems on each exam. It's not ideal, but it may be the best that I can realistically do.

Get started early on all assignments! Sometimes you will need some "incubation time" before the problem is due.

Policy on Late Work: If you want credit for your work, turn it in on-time. If I am able to get enough grading help, I may institute a late-days policy.

Grade Components

10%	Daily quizzes (mainly a note-taking device)
45%	Assignments (including homework, programming problems, in-class exercises, in-class presentations of written problems)
45%	Examinations (two in-class exams, 12% each; final exam, 21%)

Regardless of your overall average,

you may not pass the course unless you pass at least one of the exams.
if you choose not to participate in a reasonable way in class, or with partners and groups on exercises that are so designated (thus lessening the learning experience of others in the course), I may assign a grade that is lower than your average indicates.

Bounty for discovering new errata. If you are the first to find and document an error in the required textbook or in any document that I produce for the course (including this syllabus), I will give you some bonus Assignments points. The number of points is proportional to the importance and subtlety of the error. Even spelling errors will count for something! There will be a discussion forum on ANGEL for reporting these. I recommend that you subscribe to that forum, so that you will become aware of any errors as soon as they are reported.

Citizenship counts! I may adjust your overall average up or down by as much as 5 percent, based on your citizenship in the MA/CSSE 473 learning community. This includes attendance, promptness, preparation for class, positive participation in class and discussion forums, constructive partnership in pair and group assignments, timely completion of surveys, and peer evaluations of other students' work.

Attendance, Laptops in class, Other classroom etiquette

Attendance is expected at all class meetings.

You will not need to bring your laptop computer to class, unless I specify in advance that you need it for a particular day.

The negative rule for the classroom is: Don't do anything that will detract from your learning or that of people around you. Such things include missing class, talking to other people about things unrelated to the course, chewing gum noisily, connecting your computer to the network and using it for things unrelated to the course, refusing to work with a partner on a class activity. Your computer may be a useful tool in class, but it is more likely to be a distraction for you and for others around you. Please don't let it become the latter.

The positive rule is: Do things that will enhance your (and everyone's) learning. In general, no question is too dumb. Ask! Other students will generally be grateful that you did. I will often ask questions in class. You should try answering them aloud. Don't be afraid of answering incorrectly. Sometimes your incorrect guesses may lead to a more fruitful discussion than if you give a correct answer right away!

Academic Integrity

See the CSSE department statement on academic honesty. Dishonesty on assignments or exams may result in a lowered course grade, a course grade of F, and/or disciplinary action. Ask me about the minimum penalty for plagiarism!

I encourage you to discuss the problems and general approaches to solving them with other students. But when it comes to writing up a solution or writing actual code, it should be your own work (or the work of your group if it is a group or partner assignment).

If you use someone else's ideas in your solution (or any other work that you do anywhere), you should give credit to that person in the comment section of your program, and be sure that you understand it as well as if it were your own.

If you are ever in doubt about whether some specific situation violates the policy, the best approach is to discuss it with me beforehand. This is a very serious matter that I do not take lightly. Nor should you.

Email, Discussion Forums, Classmates

I will usually use Rose-Hulman email. But occasionally, the context of a message will make it best to send ANGEL mail. If you do not regularly check ANGEL mail, you should set your ANGEL preferences so that your ANGEL mail is always forwarded to your regular email.
When you send course-related email to me,

include 473 somewhere in your subject line, and also
take a minute to think about a reasonable subject line.

CSSE 473 is a good start, but add something about the specific thing you are writing about. I prefer that you send ANGEL mail. If you must send regular email, begin the Subject: line with 473: , so that I can quickly pick it out from among the dozens of daily email messages that I receive. For example, 473: Question about Exercise 2.1.2

If you think that your question or comment might be of general interest to people in the class, please post it on one of the course discussion forums. First of all, you may get an answer more quickly than if you send mail to me. Second, you may get multiple people's perspectives. Third, you will contribute to an active learning community.

Other students in the course can often be your best source of help. And they will also learn more if they explain things to you. Don't try to be the Lone Ranger in this course, especially if you do not find the course easy. If you find that you have worked on something for 30 minutes without making any progress, it's probably time to seek help.

Suggestion Box

I want your feedback on how the course is going and how it could be improved. While "nonymous" suggestions are even more useful than anonymous ones, I'd like to know what you are thinking, even if you do not feel comfortable with letting me know who made the suggestion. Thus the 473 ANGEL site contains an anonymous suggestion box. I will get your comments, but I cannot trace who sends them.
All I ask is that you only use this only for serious suggestions, not to vent when you are momentarily frustrated. You can also use this survey to tell me about things you like in the course and don't want to change. :)
If you ask a question in your anonymous message, the only reasonable way I can reply is with a post to one of the course's discussion forums. I will do that whenever I think my response is likely to be relevant to several students in the class.