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.
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 runtime 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 runtime 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 for this course is Introduction to the Design and Analysis of Algorithms, 3rd edition, by Anany Levitin (ISBN 0132316811). 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, divideandconquer, 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 NPcomplete problems.
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, 5to15 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 inclass test.
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!
There will be two inclass tests in addition to a final exam. For each exam and test, there will be both an inclass component and a takehome component. The inclass part will cover mainly definitions, concepts, and basic examples, while the takehome part will consist of longer problems and perhaps some programming.
The inclass parts of the tests will be given on Wednesday, February 27 and Friday, April 12. The takehome part will take place at about the same time. We will discuss the exact timing.
The inclass 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 takehome 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.)
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: 90100: A; 8089: B; 6579: C; 5564: D; 054: F. Grades near a cutoff get a + or .
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 makeup 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 Accommodations: If you are a student with a disability for which you may need accommodations, you should selfidentify 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 3157813351.
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 email address is eck@hws.edu. Email 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.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.
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.
Dates  Readings, Etc.  

Jan. 23 and 25  Introduction to the course; Sections 1.1, 1.2, and 1.3. 

Jan. 28 and 30; Feb.1  Chapter 2: Mathematical framework for algorithm analysis; Sections 2.1, 2.2, and 2.3. 

Feb. 4, 6, and 8  Chapter 2 continued: Analysis of recursive algorithms; Section 2.4 and Appendix B. 

Feb. 11, 13, and 15  Chapter 3: Brute force and exhaustive search; Selections from Sections 3.1 to 3.4. 

Feb. 18, 20, and 22  Chapter 3 continued: Graph search algorithms; Section 3.5 plus extra reading on graphs. 

Feb. 25 and 27; Mar. 1  TEST on Wednesday, February 27, on Chapters 1 to 3. Selections from Chapter 4: Decrease and Conquer. 

Mar. 4, 6, and 8  Selections from Chapter 5: Divide and Conquer; For example, the closest pair and convex hull problems. 

Mar. 11, 13, and 15  Selections from Chapter 6: Transform and Conquer; For example, balanced trees, heaps, and Heapsort 

Spring Break, March 1624  
Mar. 25, 27, and 29  Selections from Chapter 7: Space and Time Tradeoffs; For example, string matching, hashing and BTrees. 

Apr. 1, 3, and 5  Selections from Chapter 8: Dynamic Programming; For example, optimal binary search trees and edit distance. 

Apr. 8, 10, and 12  TEST on Friday, April 12, on Chapters 4 through 8. Selections form Chapter 9: Greedy Techniques; For example, Kruskal's and Dijkstra's algorithms. 

Apr. 15, 17, and 19  Selections from Chapter 10: Iterative Improvement; For example, maximal flow and the stable marriage problem 

Apr. 22, 24, and 26  Selections from Chapter 11: Limitations of Algorithms; Lower bound arguments; P, NP and NPcomplete problems. 

Apr. 29; May 1 and 3  Selections from Chapter 12: Coping with Limits; For example, branchandbound and approximation algorithms. 

May 6  Last day of class; wrap up the course!  
May 14  Final Exam: Tuesday, May 14, 8:30 A M 