MA/CSSE 473 Design and Analysis of Algorithms
(Summer on-line course)

Instructor's Description

Prerequisites

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, 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-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
  

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 we will do some review in 473, but that will be brief.  Some of you would do well to review your areas of weakness before 473 begins.  Or at least recognize in advance that 473 may take a lot of extra time for you because you need some remediation in prerequisite material.  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 that are often used for the prerequisite courses. http://www.rose-hulman.edu/class/csse/csse473/201110/Homework/BackgroundMaterial.html

For some day's PowerPoint Slides there were Instructor Notes that the students did not see.  For the summer course I am making those available in separate documents, linked form the schedule page.

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.   http://www.rose-hulman.edu/class/csse/csse473/201110/Homework/230-problems.pdf

The main things that you should bring into this course

• enthusiasm, curiosity, perseverance, and a "can do" attitude
• (not in summer online course) 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

• 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

When I give a reading assignment, you should read it.  The summer course is, after all, an independent study course!

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

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 additional problems to suggest:

• problems that are simpler than the assigned problems.  If you can't do the assigned problem, perhaps one of these will be a "bridge" for you.
• 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 have set up an ANGEL discussion forum for this purpose, and I will give a small amount of extra credit for submitting or critiquing a solution.  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.  I suggest that you first try to do each problem without the hint, but if you get stuck, feel free to use the hint.

Your solutions to programming problems 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 a  problem is due.

Policy on Late Work (Summer):

I recognize that different students have different schedules during the summer.  Some of you know already that certain weeks will  be busy (or will be your vacation week), so I am allowing some leeway on assignment submission. 

I will list due dates on the schedule. If you get each assignment done by its due date, then the work will be spread out reasonably evenly during the summer.  But for each assignment I will list a certain number of "grace days". Submit the assignment within that many calendar days after it is due, and you will not lose any credit for lateness.  At the beginning of the summer, assignments will have 7 grace days.  The number of grace days per assignment will gradually decrease as the summer progresses.  I figure that as the summer goes on, you will have more advance opportunity to anticipate busy or absent weeks and work ahead.  Also, practically speaking, I can't get stuck with grading 60 assignment submissions during the last week of the course!

After the grace days for an assignment have expired, there will be a 25% penalty per additional day or portion of a day that it is late.