MA/CSSE 473 Design and Analysis of Algorithms
Winter, 2016-17 - a.k.a. 201720  (under construction)

 

Instructor Info and Main Web Locations

Instructor  Claude Anderson
Office Phone  877-8331
Office Address  F210 (Northeast corner, top floor of Moench)
Office Hours  Whenever I am in my office I am happy to help you (except during 1st hour MTRF).  Most weeks I will be in my office 12:00-4:00 MTRF and a few hours on Wednesdays (Wednesday times will vary). Many days I stay past 4:00. I will have additional meetings from time to time. 
You can view my calendar at http://exchange.rose-hulman.edu/owa/calendar/anderson@rose-hulman.edu/Calendar/calendar.html. The "week view" probably works best.
Feel free to make an appointment or to just drop in.
E-mail  anderson@rose-hulman.edu
Schedule page
(bookmark it in your browser)		 http://www.rose-hulman.edu/class/csse/csse473/201720/Schedule/Schedule.htm
This is the place where I will post most course materials.  On Moodle: Things that are interactive (such as drop boxes and surveys) or things that I do not want to post publicly (such as reading materials and homework solutions).
Course announcements and discussion forums will be on Piazza. http://piazza.com/rose-hulman/winter2017/macsse473/td>

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.  The 3rd edition is also available online from www.vitalsource.com.
Highly Recommended: Data Structures and Problem Solving Using Java, 4th or 3rd Edition  by Mark Weiss (CSSE 230 text)
Because you should already be familiar with the style and context of the Weiss 230 book, I will sometimes place sections of this book in the reading assignments on the schedule page, to provide an alternate explanation of certain course content.  Unless I explicitly say otherwise, all such references to Weiss are optional (but still a good idea);  the occasional required Weiss readings will be available on Moodle. As I am writing this (November, 2016), I see copies of the Weiss 3rd edition on Ebay for under $5.00 (including shipping).
A brief excerpt from the Dasgupta Algorithms book listed below has been provided (on Moodle), and ss part of the early reading assignments. 

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

Weeks 1-2 Review, Overview of Data Structures, Algorithms and their analysis; intro to arithmetic algorithms Chapters 1-3, Dasgupta 0-1
Weeks 3-4 Decrease-and-Conquer, Divide-and-Conquer, Transform-and-Conquer Chapters 4-6
Weeks 5-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. 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 (some of it in the reading assignments) 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, balanced BSTs, priority queue and its heap implementation, set, hash table, 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

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!

http://www.rose-hulman.edu/class/csse/csse473/201720/Homework/BackgroundMaterial.html

 

This document contains some written problems that I assigned once  in CSSE 230.  They are relevant to this course, and may be good practice for you.   I am not saying that you should do all of them, but if you look at this list and find that you would not know how to do very many of them, then you will have your work cut out for you in this course; perhaps you should do some of these problems for extra practice.   http://www.rose-hulman.edu/class/csse/csse473/201720/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
  • 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 a lot (typically 12-20 per week) of 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.  If you write them by hand and plan to scan or photograph them, please do not write on both sides of the paper. "Bleed-through" makes the scanned document very difficult to read.

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). Late assignments will not be accepted, unless there is a verifiable emergency that is beyond your control.

In general, you are encouraged to 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 referring to things you wrote when working with others) to be sure that you understand it. You should also acknowledge any collaboration in your submission. Copying solutions from present or past students or from internet sources is never acceptable.

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 a little too advanced for this course, but that would be good challenges for the best students.

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 folder for this purpose, and I will give a small amount of extra credit for submitting a solution or critiquing another styudent's 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.

There will most likely be a small number of implementation problems, but in this course I mostly prefer that you spend more time considering several algorithms at a higher level than a lot of time getting bugs out of your code for one algorithm.

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. By "get started early", I do not mean "the day before the assignment is due; I suggest that you start thinking about an assignment "the day before the previous assignment is due."

Policy on Late Work:

Assignments must be turned in on time if you want credit for them. If you have a verifiable emergency that is beyond your control, I may excuse you from an assignment.

A typical assignment counts about 1% of your course grade, so missing the credit for one or two assignments is not a disaster, provided that you get the problems done and understand them before the exam.

Grade Components

     
20%Assignments (homework, occasional quizzes, implementation problems, and anything else that is not an exam)
80%Examinations  (16% for each of three in-class exams, 32%  for the final exam).

A "standard" 90-85-80-75-70-65-60 grading scale will be used as the starting point. May be adjusted downward, but do not count on this.

Exams will be closed book and notes. Many problems will be similar to HW problems or in-class examples, but some problems may ask you to apply course concepts to new situations.

Extra credit for discovering new errata. If you are the first to point out an error in the Levitin 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 folder on Moodle for reporting these.

 

MA/CSSE 473 Community

I encourage you to communicate with other students, perhaps to form/join small study groups.  I also encourage you to use Piazza to ask and answer questions about anything in the course, 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.  

I encourage discussion with other students concerning 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 I have designated it as 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 this 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.

Penalty:  The minimum penalty for plagiarism or cheating will be a negative score (If the assignment is worth X points, your score will be -X) for the assignment or exam. AS required by Rose-hulman rules, cases of academic misconduct will be reported to the Dean of Students.  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 other students in the course, please post it to 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.

Disability and Accessibility Issues

I understand that "invisible" disabilities (learning and attention deficit disorders, chronic fatigue syndrome, depression, anxiety, etc.) can significantly affect a student's academic performance. I encourage students to document special academic circumstances with the Student Accessibility Services office, and then to contact me as soon as possible so that we can work together to provide their recommended academic accommodations while protecting your privacy. Please note that it is the student's responsibility to request any approved, documented academic accommodations (such as extra time for an exam) at least a week in advance of the exam.