MA/CSSE 473 Design and Analysis of Algorithms
Summer, 2016 - a.k.a. 201640 

 

Instructor Info and Main Web Locations

Instructor  Claude Anderson
Office Phone  877-8331
Office Address  (summer) Email, Piazza
Office Hours  I will respond to questions on Piazza or to email quickly.  I plan to have virtual office hours twice most weeks:  Mondays 9:00-10:00 AM, Thursdays 9:00-10:00 PM
E-mail  anderson@rose-hulman.edu
Schedule page
(bookmark it in your browser)		 http://www.rose-hulman.edu/class/csse/csse473/201640/Schedule/Schedule.htm
This is the place where I will post most course materials.  Videos and things that are interactive or that I do not want to post publicly (such as reading materials and homework solutions) will be posted on the course Moodle page.
Course announcements, questions, and discussions will be on Piazza. http://piazza.com/rose-hulman/summer2016/csse473/home

Textbook(s)

Required: The Design and Analysis of Algorithms, 3rd Edition  by Levitin (Pearson, 2012).  If you can find the 2nd edition for less money, you are welcome to use it. On homework assignment documents, I will list the problem numbers from both editions.  An electronic version of the 3rd edition is also available from http://www.vitalsource.com .

Highly Recommended: Data Structures and Problem Solving Using Java, 4th or 3rd Edition  by Weiss (CSSE 230 text)
Because you should already be familiar with the style and context of the Weiss book, I will sometimes place sections of this book in the reading assignments on the schedule page, to provide an alternate explanation of things.  Unless I explicitly say otherwise, all such references to Weiss are optional readings;  the contents of the occasional required readings from Weiss will be placed online for you to read.

An excerpt from the Dasgupta Algorithms book listed below has been provided for you (on Moodle), and is part of some early reading assignments for the course. 

Approximate reading schedule Levitin 3rd edition, (2nd similar, chapters 4 and 5 reversed)

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

Other Related Books

  • The other prerequisite for this course:
    • Grimaldi, Ralph P. Discrete and Combinatorial Mathematics (Addison-Wesley, 2003)
  • Other good books on Algorithms, mostly at the level of this course:
    • Algorithms by Dasgupta, Papadimitriou, and Vazirani (McGraw-Hill, 2008)
    • Algorithms by Johnsonbaugh and Schaefer (Prentice-Hall, 2004)
    • Algorithms by Sedgewick and Wayne (Addison-Wesley, 2011) [notice the creative trend in book titles!]
    • An Introduction to the Analysis of Algorithms by Sedgwick and Flajolet (Addison-Wesley, 2014)
    • Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (MIT Press, 2010).  This large book is a great reference for students who have already taken MA/CS 473.
    • Data Structures and Algorithm Analysis in Java, 3rd ed  by Weiss (Addison-Wesley, 2012) (not the CSSE230 text)

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).

Prerequisites

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

This course will include quick reviews (most of that review is only in the reading assignments) of the following topics. If you did not understand those topics from the previous courses, you will need to do some extra review work:

  • Elementary data structures and their implementations (stack, queue, list (linked and sequential), tree, binary search tree, AVL tree, digital search tree (a.k.a. trie) priority queue and its heap implementation, set, hash table, graph, various sorting and searching techniques)
  • Basic proof techniques, including proof by contradiction, contra-positive, and mathematical induction.  Understand the difference between "for each x there exists a y" and "there exists a y  for each x"
  • Elementary tools of analysis, including summations, integrals, inequalities, logarithms, counting techniques,  big-O and its cousins big-theta,  big-omega, etc., recurrence relations, master theorem.
  • Reading, using, and adapting mathematical notation
  • Simple programming techniques, including functional decomposition, recursion, iteration, arrays, references, pseudocode
  • Basics from your calculus course (integrals, derivatives, summations, exponential and logarithmic functions)

For some of you, it has been a long time since you took CSSE 230 and/or Math 275/375.  Also, there are different versions of those courses, depending on who teaches them.  You may have come out of those courses not feeling very confident about the proofs and algorithm analysis material.  Of course there will be some review in 473, but that will be brief.  Some of you would do well to spend extra time reviewing your areas of weakness.  Or at least recognize in advance that 473 may take significant extra time for you because you need to work on some of the prerequisite material.    It is better to face that reality now than to pretend that 473 will be a "fresh start" that will not really depend on those courses!

I prepared the following document to help you get an idea of what you might need/want to review. It includes references to specific sections of the Grimaldi and Weiss textbooks from the prerequisite courses. http://www.rose-hulman.edu/class/csse/csse473/201640/Homework/BackgroundMaterial.html

 

This document contains some written problems that I have assigned  in CSSE 230.  They are relevant to this course, and may be good practice for you.   http://www.rose-hulman.edu/class/csse/csse473/201640/Homework/230-problems.pdf

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
  • Foster creativity by providing you with problems that require thinking "outside the box"
  • Help students understand some limitations of computer algorithms via the study of NP-complete problems

Course Requirements

The nature of the assignments

When I give a reading assignment, you should read it. 

I will assign several written problems, most 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 many problems, your score will be determined not only by correctness but also by the quality of your explanation. Some of the problems will provide straightforward practice with algorithms from the course; others will require creative solutions. Don't put them off until the last minute!

Written assignments will be submitted to drop boxes on Moodle.  You may either use software to produce your solutions, or write them legibly by hand and scan them.  If you submit multiple documents, please put them into a ZIP or RAR file so you can do a single submission on Moodle. 

When a problem calls for an algorithm, English or some kind of pseudocode  is usually sufficient, as long as the graders and I can understand it.  If you feel more comfortable implementing your solution in an actual programming language, of course you may do so.  If a problem requires such an implementation, it will be explicitly stated in the homework assignment.

The due time for all assignments will be 11:55 PM Terre Haute time (EDT). Moodle does not let me specify 11:59

In general, you may communicate with other students about the problems, and work out solutions together. Collaboration on homework is encouraged, but when you write it up to turn it in, you must do it on your own to be sure that you understand it. You should also acknowledge the collaboration in your submission.

The textbook has exercises at the ends of each section; 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 at least read them all, regardless of whether they are assigned.  I will sometimes pick out specific non-required problems to suggest:

  • Problems that are simpler than the assigned problems.  If you can't do some assigned problem, perhaps one of these will be a "bridge" for you to understand things well enough to do the assigned problem.
  • Problems that are really over material from a prerequisite course (CSSE 230 or Math 375).
  • Problems that are great to think about, but that would take far too long to write up solutions.
  • Problems that are too advanced for this course, but that would be good challenges for the best students.

There will also be a small number of implementation problems, but in this course I would usually rather have you spend your time considering several algorithms at a higher level than spend a lot of time getting bugs out of your code for one algorithm.

Extra Credit: Solution pool.   Many assignments will contain non-required problems.  It would be great to have a set of solutions to those problems so that students can check their answers.  Producing them may be a good community activity.  I will  set up a Piazza discussion folder for this purpose, and I will give a small amount of extra credit for submitting or critiquing a solution.  Start a new topic for each problem.  This will only work well if several students critique each solution to either say that it is great or to suggest corrections or improvements.

Problem hints: Most problems in the Levitin textbook have hints at the end of the book (just before the index).  I suggest that you first try to do each problem without the hint, but if you get stuck, feel free to use the hint.

I often assign one or two implementation problems.  If so, your solutions (in the programming environment of your choice, as long as I can run it on my laptop and/or a web browser) should be well-designed and well-documented. 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.

Get started early on all assignments! Sometimes you will need some "incubation time" before between the time you begin a problem and the time you are able to solve it.  Our brains keep working on problems, even when we are not actively thinking about them, even when we are sleeping.  But of course that doesn't happen unless we have first spent some time actively thinking about it.

Policy on Late Work:

Assignments must be turned in on time if you want credit for them.

But, we all have days when we are extremely busy, or times when a problem takes longer to complete than we expect it will. To account for this(and to avoid having to deal with individual requests for late submissions), I give each student a “late day bank account” that starts with seven late days.

  1. Using (withdrawing) a late day allows you to turn in any assignment up to 24 hours after the time when it is due.  24-48 hours late requires using two late days; 48-72 hours requires using three.
  2. You may earn (deposit) a late day by turning in an assignment at least 24 hours early and earning at least 80% of the possible credit on the assignment. There is no limit to the number of late days you can save up.
  3. At most three late days may be used for any one assignment.  After that, no credit!
  4. Overdrafts are not allowed.  If your late day account is almost empty early, you should take it as a sign that you may need to change your approach to the course.  If your account is empty and you submit an assignment late, you will receive no credit.  It is also time to begin turning assignments in early, in case you need a late day later.
  5. Unused late days have no value (other than fame and glory!)  at the end of the term.

Notifying me of a deposit or withdrawal: You do not have to do anything;  I will keep track of late days and post everyone's balance on the web.  I have not come up with a  better way to keep you appraised you at this point.  If you do not want to participate in the late day bank because you do not want your balance to be public, let me know.  But you will not be able to turn in any late assignments for credit.

Some particular assignments may be designated as ”no late days“ assignments. This might happen because: /p>

  • there is an exam the next class day or the day after, so I want to post solutions right away; or
  • what we will do next depends heavily on something in this assignment; or
  • some other reason that I will explain at the time.

Grade Components

     
70%Assignments (Written and implementation assignments, surveys, discussion forums, etc.)
30%Final exam  (On campus, Wednesday morning, August 31, 2016)

Letter grades.The followinfg table shows the grade ranges. If I perceive that exam(s) have been more difficult than usual, I may lower the cutoff levels for grades a little bit. I will not raise them.

Letter grades cutoff numbers

Regardless of your overall course average, you may not pass the course unless your final exam score is 80% of the lowest passing score for the course (that lowest allowable exam score will probably be about 47%).

Extra credit 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 homework points. The number of points is proportional to the importance and subtlety of the error. Even spelling errors will count for something! There is a discussion forum on Moodle 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.

 

MA/CSSE 473 Community

I encourage you to communicate with other students.  I also encourage you to use the Piazza forums to ask questions about course material or homework, so they can be answered by other students and so everyone can see the questions and answers. 

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 discussion with other students the problems and general approaches to solving them. 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. 

Another kind of plagiarism: Many of the homework problems that I will assign will be repeats from previous terms.  I have posted solutions in previous terms.  It may be tempting to find those solutions and use them.  Don't do it!  If I see that you have done this, it will be considered plagiarism. More important, you will miss the learning benefits that come from struggling with a problem  until you get it.

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.

Plagiarism or cheating will result in a negative score (i.e., less than zero) for the assignment or exam. Typically the negative of the total possible score for the assignment in which the cheating occurred. Egregious cases will result in a grade of “F” for the course. More important, such dishonesty steals your own self-esteem and your opportunity to learn. So don’t do it!

Email, Piazza, Classmates

Piazza will be my main venue for course announcements.  Be sure to sign up for the MA/CSSE 473 Piazza course.   You probably want to sign up to get email notification when someone posts something.  I will occasionally send announcements that are more urgent via Rose-Hulman email.

 

When you send course-related email to me, please

  • include 473 somewhere in your subject line, and also
  • take a minute to think about a reasonable subject line.
  • For example, 473: Question about Exercise 2.1.2

If you there is a chance  that your question or comment might be of general interest to people in the course, please post it to one of the course discussion folders on Piazza. First of all, you may get an answer more quickly than if you only 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  have worked on something for 30 minutes without making any progress, it's probably time to seek help.

Anonymous 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 Moodle course will contain an anonymous suggestion box. I will get your comments, but I cannot trace who sends them.

I ask that you only use this survey 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 respond (since I do not know who asked)  is with a post to Piazza or send an email to the class. I will do that whenever I think my response is likely to be relevant to several students in the course.