Computer Science 327:
Data Structures and Algorithms

   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Spring 2013.

   Instructor:  David J. Eck  (eck@hws.edu)
   
   Monday, Wednesday, Friday, 3:00 -- 3:55 PM
        Room Coxe 1.

About The Course

Computer Science 327 is a course in data structures and algorithms. To some extent, it is a continuation of CPSC 225 (Intermediate Programming). In CPSC 225, you encountered basic data structures such as lists and binary trees, and you learned to do some simple run-time analysis of algorithms. For example, you learned that the run time of binary search is Ω(log(n)), where n is the size of the array that is being searched. And you know that this is much faster than Ω(n), the run-time for linear search.

This course will introduce a few new data structures and a wide variety of new algorithms. Furthermore, it will take a much more formal and mathematical approach to the analysis of algorithms. In addition to looking at some specific algorithms, the course will cover some fundamental patterns and techniques that are used in algorithms. The hope is that learning these patterns will help you to develop your own algorithms when you are faced with new problems.

The Textbook

The textbook for this course is Introduction to the Design and Analysis of Algorithms, 3rd edition, by Anany Levitin (ISBN 0-13-231681-1). Almost all the readings and homework assignments for the course will be taken from the textbook, so you really do need a copy. (The regular price of the book is $131, and the price at amazon.com is $106. I will note that an eBook version is available at coursesmart.com for $53.)

We will not cover every section of the text, but we will do at least a few sections from each of the twelve chapters. After an introductory chapter, the book begins in Chapter 2 with an introduction to the mathematical analysis of algorithms; since it is fundamental for understanding the rest of the course, we will spend about two weeks on that chapter. Chapters 3 through 10 are organized around different algorithmic patterns, such as exhaustive search, divide-and-conquer, and dynamic programming. Each chapter covers several specific algorithms that use the technique covered in that chapter. Chapters 10 and 11 are concerned with the limitations on algorithmic processing, including the important topic of NP-complete problems.

Homework and Presentations

I will assign homework every week. Homework will include both programming assignments and written exercises. Programming assignments will ask you to implement algorithms that are discussed in class or, in some cases, to design and implement your own algorithms. Written assignments will, for the most part, be taken from the exercises at the end of each section in the textbook. Some of the exercises will ask you for mathematical analyses of algorithms, and some might even ask you for a "proof." However, we won't be doing deeply theoretical or rigorous mathematics or proofs.

For the most part, it will be acceptable for people to work together to find solutions for the written assignments, as long as each person writes up their own solution in their own words. Programming assignments will, for the most part, be individual work, although some programs might be pair or group assignments.

In addition to the regular assignments, I would like everyone in the class to give several short, 5-to-15 minute, presentations. I am hoping for three presentations from each student in the class, but if we are running short of time, we might stop at two. You will choose the topic for each presentation, in consultation with me. You might want to discuss one of the algorithms from the textbook that I don't cover in class. You might want to do one of the exercises that I don't assign. You might want to talk about some aspect of data structures or algorithms that you read about in a newspaper or on the Web. Some of the exercises in the text are designated as "puzzles." It might be particularly fun to pick one of those exercises for one of your presentations. If people don't start volunteering for presentations pretty quickly, I will start assigning topics -- and you probably don't want me to do that! It would be nice to have everyone in the course do a presentation before the first in-class test.

Computer Science Colloquia

The Department of Mathematics and Computer Science sponsors several colloquium talks every semester. They are usually scheduled at 4:00 or 4:30 PM. This semester, a number of talks will be about computer science, including a few by job candidates for a computer science faculty position. As part of your homework grade for this course, you are required to attend at least two of these talks. If that is impossible, let me know, and we can arrange some substitute work such as extra class presentations.

Talks will be announced in class and by email. If you attend a talk, be sure to let me know that you are there!

Tests and Final Exam

There will be two in-class tests in addition to a final exam. For each exam and test, there will be both an in-class component and a take-home component. The in-class part will cover mainly definitions, concepts, and basic examples, while the take-home part will consist of longer problems and perhaps some programming.

The in-class parts of the tests will be given on Wednesday, February 27 and Friday, April 12. The take-home part will take place at about the same time. We will discuss the exact timing.

The in-class part of the final exam will take place in the officially scheduled exam time for the course, which is Tuesday, May 14, at 8:30 AM. The take-home part will be due at the same time. (Since senior grades are due on the day of the exam, there might have to be some adjustments for seniors.)

Grading

Your numerical grade for the course will be determined as follows:

             First Test:                  20%
             Second Test:                 20%
             Final Exam:                  25%
             Homework and presentations:  35%

Letter grades are assigned as follows: 90-100: A; 80-89: B; 65-79: C; 55-64: D; 0-54: F. Grades near a cutoff get a + or -.

Attendance, Etc.

I assume that you understand the importance of attending class. While I do not take attendance in every class, I expect you to be present unless circumstances make that impossible.

If you miss a test or final exam without an extremely good excuse, you will receive a grade of zero. If you think you have an excuse for missing a test, please discuss it with me, in advance if possible. If I judge that your excuse is reasonable, I will -- depending on the circumstances -- either give you a make-up quiz or test, or I will average your other grades so that the missing grade does not count against you.

Although it should not need to be said, I expect you to maintain a reasonable level of decorum in class. This means that there is usually no eating or drinking in class. Cell phones are turned off. There is no walking in late or walking in and out of the room during lecture.

Disability Statement from the CTL

Disability Accommodations: If you are a student with a disability for which you may need accommodations, you should self-identify and register for services with the Coordinator of Disability Services at the Center for Teaching and Learning (CTL), and provide documentation of your disability. Disability related accommodations and services generally will not be provided until the registration and documentation process is complete. The guidelines for documenting disabilities can be found at the following website: http://www.hws.edu/disabilities

Please direct questions about this process or Disability Services at HWS to David Silver, Coordinator of Disability Services, at silver@hws.edu or 315-781-3351.

Office Hours, E-mail, WWW

My office is room 313 in Lansing Hall. My office phone extension is 3398. I am on campus most days, and you are welcome to come in anytime you can find me there. I will announce office hours and post them on my office door and on the course web page as soon as my schedule is determined, but note that your office visits are certainly not restricted to my regular office hours!

My e-mail address is eck@hws.edu. E-mail is good way to communicate with me, since I usually answer messages within a day of receiving them.

The home page for this course on the World Wide Web is located at http://math.hws.edu/eck/cs327/index_s13.html. This page will contain a weekly guide to the course, including assignments. You will want to bookmark this page. This courses does not use Blackboard.

Tentative Schedule

Here is a very tentative schedule for this course. We will try to cover some material from every chapter of the textbook, but we will not cover every topic. This means that we will be covering about one chapter every week, and we will do as much from each chapter as we have time for.