CSci 242 — Analysis of Algorithms

Time and Place: TR 10:00 - 11:15, Welles 121

Final Meeting: Tuesday, May 14, 12:00 Noon

Instructor: Doug Baldwin
Office: South 307
Phone: 245-5659
E-Mail: baldwin@geneseo.edu
Twitter: @DougBaldwin5, #csci242

Office Hours: Monday 2:00 - 3:00, Thursday 1:30 - 2:30, or By Appointment

WWW Pages:
Lecture Notes: http://cs.geneseo.edu/~baldwin/csci242/spring2013/lectures.html
Exercises: http://cs.geneseo.edu/~baldwin/csci242/spring2013/exercises.html

There are many reasons why a computer scientist should study algorithms. First, a great many algorithms exist that are used over and over in larger computing applications. Some of these, for example sorting or searching algorithms, are ones whose importance you probably already appreciate. Others, for example graph or numeric algorithms, sit quietly inside network routers, compilers, DVD or CD players, and other computer systems, where literally billions of people rely on them every day. Anyone who is going to program computers for almost any application should have a broad acquaintance with such algorithms. Second, over the years computer scientists have discovered certain strategies for designing algorithms that apply very widely, to many different algorithms. Sooner or later, every computer scientist will design a new algorithm, and so should have some familiarity with these strategies. Finally, anyone who is going to choose algorithms to use in larger applications, let alone design new algorithms, has to be able to make theoretical and empirical comparisons between algorithms. This course therefore has a number of general goals: to expand the survey of classic algorithms and data structures begun in CSci 142 and 240, to reinforce techniques of algorithm analysis developed in those courses and to introduce new techniques, and to introduce you to some important algorithm design strategies.

Prerequisites:

CSci 240, Math 237 or 239

Learning Outcomes

At the end of this course, students who meet my expectations will...

• Understand graphs, including being able to use them to model problems, implement them, and describe both the behavior and execution time of common graph algorithms.
• Recognize problems for which divide-and-conquer algorithms are likely to be good solutions, and design and analyze such algorithms.
• Recognize problems for which dynamic programming algorithms are likely to be good solutions, and design and analyze such algorithms.
• Recognize problems for which greedy algorithms are likely to be good solutions, and design and analyze such algorithms.
• Recognize problems for which backtracking algorithms are likely to be good solutions, and design and analyze such algorithms.
• Understand hash tables, including being able to identify suitable applications for them, design and implement hash functions and collision resolution algorithms, and discuss the execution time of their main operations.
• Be able to perform probabalistic analyses of algorithms, including analyses of expected execution time and analyses of randomized algorithms.
• Discuss the strengths and weaknesses of various algorithm design strategies.
• Be able to select an algorithm from a range of choices for an application, justify the choice, and implement it in a program.

Books and Other Resources

Text

The (required) textbook for this course is

Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.)

It is available from the College bookstore and other sources.

Online

The accompanying Web site for the textbook is

http://mitpress.mit.edu/algorithms/

Materials from the last time I taught this course (Fall 2012) are at

http://cs.geneseo.edu/~baldwin/csci242/fall2012/

Course Schedule

The following dates are best estimates. They may well change as students’ actual needs become apparent. Refer to the Web version of this syllabus for the most current information, I will keep it as up-to-date as possible:

Grades and Such

Your grade for this course will be calculated from your grades on exercises, exams, etc. as follows:

Late Policy

I will accept work that is turned in late, but with a 10% per day compound late penalty. For example, homework turned in 1 day late gets 10% taken off its grade; homework turned in 2 days late gets 10% taken off for the first day, then 10% of what’s left gets taken off for the second day. Similarly for 3 days, 4 days, and so forth. I round grades to the nearest whole number, so it is possible for something to be so late that its grade rounds to 0.

Policy on Collaboration

Assignments in this course are learning exercises, not tests of what you know. You are therefore welcome to work on them in small groups, unless specifically told otherwise in the assignment handout — a well-managed group makes a successful, and thus more educational, project more likely.

In order to avoid confusion when people work together, please indicate clearly what work is yours and what comes from other sources on everything you hand in. The appropriate “indication” depends on how much work is yours and how distinguishable it is from your collaborators’. At one extreme, if a group of people work together on all parts of an assignment, they could hand in one solution with all their names, and a brief statement of what each person contributed, on it. At the other extreme, if you do most of an assignment on your own but get a specific idea from someone else, you might just include a comment or footnote to the effect of “this idea comes from Betty Smith” in whatever you hand in. The bottom line is that everything you take credit for must include some identifiable contribution by you, and you should never claim credit for work or ideas that aren’t yours. I’ll be glad to advise you on what I consider appropriate forms and acknowledgements of collaboration in specific cases if you wish.

Please note that tests are tests of what you know, and working together on them is explicitly forbidden. This means that if you take advantage of the collaboration policy to avoid doing your share of the work on the exercises, you will probably discover too late that you haven’t learned enough to do very well on the tests.

I will penalize violations of this policy. The severity of the penalty will depend on the severity of the violation.

Accommodations

SUNY Geneseo will make reasonable accommodations for persons with documented physical, emotional or learning disabilities. Students should consult with the Director in the Office of Disability Services (Tabitha Buggie-Hunt, 105D Erwin, 245-5112) and their individual faculty regarding any needed accommodations as early as possible in the semester.