CPSC 327:
Data Structures and Algorithms

   
   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Spring 2019.

   Instructor:  David J. Eck.

   Monday, Wednesday, Friday, 12:20–1:15.
       Room Gulick 2000.

About This 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. And near the end of the course, we will encounter some examples of "NP-complete" problems, for which no efficient solution is known.

The textbook for the course is Analysis of Algorithms, 3rd Edition, by Thomas Cormen and others (ISBN 9780262033848). A copy will be on reserve in the library. You do not need to bring the textbook to class. This is a standard, comprehensive algorithms textbook. It contains much more material than we will be able to cover, and it is a good book to keep around for reference in the rest of your computer science career. It is a lot more mathematically rigorous than we need for this course, and we will avoid the more mathematical sections. Nevertheless, some math is unavoidable. I will try to be clear about what you really need to know.

Tentative Schedule

I do not have a detailed week-by-week schedule for this course. Here is a list of the topics that I hope to cover, with the approximate amount of time to be spent on each section of the course and the source of the reading for each topic. Although I hope to cover all of these topics, this list is tentative; I might add or subtract topics, depending on how the course goes.

Assignments

There will be both written assignments and programming assignments in this course, with at least one assignment due in most weeks. Some, but not all, of the assignments will come from the textbook.

For written assignments, you will usually be allowed and even encouraged to work together on the problems, but you will always be expected to write up your own answers in your own words, and you must always be sure to fully understand any work that you turn in. All answers must be supported by work and reasoning that you present.

Some programming assignments will be individual work and some will be team projects. In general, any program that you turn in should be purely your own work or your team's; any exception to this policy will be clearly noted in the assignment.

I reserve the right in all cases to ask you to come to my office hours to explain your work or re-do it on my board.

Term Project

You are required to complete a term project at some point during the semester. You can do the project at any point during the term. The project can be a research paper or a program or perhaps some combination of the two. The project will count for 10% of your grade in the course. You will get 8 points for an "acceptable" project and 9 points for a "good" project, and you get one additional point if you give a short presentation to the class about your project. Presentations will be given during regular class periods.

Before you start work on your project, you must meet with me to choose a topic and get approval for it. For possible topics, you might look at parts of the textbook that we are not covering. You might be inspired to work on unassigned exercises from the textbook. You might look through the list of algorithms at https://en.wikipedia.org/wiki/List_of_algorithms. You might work on an algorithm or an application of algorithms that is used in some other discipline.

I encourage you to avoid putting the project off until the last minute! Come it and talk to me about ideas!

Tests

This course will have two in-class tests, which will be given on Monday, March 4 and on Monday, April 29.

There will also be a take-home mid-term exam. It will probably be handed out on March 25 and due a week later, but we will discuss the timing.

There is no final exam for this course. The scheduled final exam period for this course is Monday, May 13, at 7:00 PM. The last assignment for the course will be due at or before that final exam period. I will have a final class during the exam period, but attendance will not be required. (If anyone shows up, maybe we can order pizza.)

Grading

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

        First in-class test:     15% 
        Second in-class test:    15% 
        Take-home midterm exam:  15%
        Term project:            10%
        Assignments:             45%

I reserve the right to adjust your grade for the course downwards if you miss more than a couple of classes without a good excuse. In my grading scale for this course, an A corresponds to 90–100%, B to 80–89%, C to 67–79%, D to 55–66%, and F to 0–54%. Grades near the endpoints of a range get a plus or minus.

Statements from the Center for Teaching and Learning

At Hobart and William Smith Colleges, we encourage you to learn collaboratively and to seek the resources that will enable you to succeed. The Center for Teaching and Learning (CTL) is one of those resources: CTL programs and staff help you engage with your learning, accomplish the tasks before you, enhance your thinking and skills, and empower you to do your best. Resources at CTL are many: Teaching Fellows provide content support in 12 departments, Study Mentors help you manage your time and responsibilities, Writing Fellows help you think well on paper, and professional staff help you assess academic needs.

Disability Accommodations: If you are a student with a disability for which you may need accommodations, you should self-identify, provide appropriate documentation of your disability, and register for services with Disability Services at the Center for Teaching and Learning (CTL). 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/academics/ctl/disability_services.aspx. Please direct questions about this process or Disability Services at HWS to Christen Davis, Coordinator of Disability Services, at ctl@hws.edu or x 3351.

No Technology During Lecture

I ask that you refrain from using any technology (beyond pen/pencil and paper) in lecture, unless you have a verified need to take notes on computer. This includes laptops, tablets, and cell phones.

There is substantial research showing that taking notes on paper can improve retention of the material, compared to note-taking on computer. My real advice is to take notes in outline form, noting down important ideas and examples, and to make a more formal copy of the notes after class, filling in any missing details. There is also research showing that the multitasking that you are likely to engage in if you have a computer open in front of you is detrimental to learning.

Office Hours, E-mail, and Web

My office is room 313 in Lansing Hall. You are welcome to stop by my office anytime you can find me there. My regular office hours, when I am almost certain to be in my office, will be announced later.

My e-mail address is eck@hws.edu.

There is a Web page for this course at http://math.hws.edu/eck/cs327. I will post weekly readings and assignments on that page. This course does not use Canvas.

https://xkcd.com/1831/