CPSC 327:
Data Structures and Algorithms
Department of Mathematics and Computer Science Hobart and William Smith Colleges Spring 2018. Instructor: David J. Eck. Monday, Wednesday, Friday, 12:20–1:15. Room Gulick 2001.
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 The Algorithm Design Manual, by Steven Skiena, 2nd edition paperback, ISBN 978-1849967204. This book takes a generally practical approach to algorithms, with less emphasis on mathematical rigor and proof, and more on the basic knowledge that any practicing computer scientist should have. The first ten chapters of the book form the core of a typical course in data structures and algorithm, and they provide more than enough material for a one semester course. We will spend most of the semester covering selected topics from these chapters. The remainder of the book is a kind of catalog of important and well-known data structures and algorithms. We will occasionally consult the catalog, but it is mostly meant as a reference that can be useful to you throughout your career.
Assignments
There will be both written assignments and programming assignments in this course, with at least one assignment due in almost every week. 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.
Tests
This course has a mid-term exam and a final exam. Both exams will have a take-home part as well as an in-class part. The take-home part of an exam differs from a regular assignment in that the work on a take-home exam must be strictly your own.
The in-class part of the mid-term exam will be given on Wednesday, March 7. The in-class part of the final exam will be given in the final exam period scheduled by the Registrar, on Sunday, May 6, at 1:30 PM.
Grading
Your numerical grade for the course will be computed as follows:
Mid-term exam, in-class part: 15%
Mid-term exam, take-home part: 10%
Final exam, in-class part: 15%
Final exam, take-home part: 10%
Assignments: 50%
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 68–79%, D to 55–67%, 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, Q Fellows support you in courses that require math, 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/index_s18.html. I will post weekly readings and assignments on that page.
Tentative Schedule
We will cover topics in Chapters 1 through 10 of the textbook, with occasional excursions into other material from later in the book and from other sources. The following tentative schedule will give you an idea of the pace at which we will cover this material. We will try to follow this schedule in a general way, but the selection of specific topics and examples will depend on how the course develops. You should consult the weekly posting on the course web page for more specific information.
| Dates | Topics | Readings From |
|---|---|---|
| Jan. 17, 19 | Introduction | Chapter 1 |
| Jan. 22, 24, 26 | Analysis of Algorithms | Chapter 2 |
| Jan. 29, 31; Feb. 2 | Data Structures | Chapter 3 |
| Feb. 5, 7, 9 |
Sorting and Searching |
Chapter 4 |
| Feb. 12, 14, 16 | Divide and Conquer; Recurrence Relations | Chapter 4 |
| Feb. 19, 21, 23 | Graphs and Graph Traversal | Chapters 5 |
| Feb. 26, 28; Mar. 2 | Graph Algorithms | Chapters 5 and 6 |
| Mar. 5, 7, 9 |
Graph Algorithms, continued Midterm Exam, Wednesday, March 7 |
Chapter 6 |
| Mar. 13, 14, 15 | Search; Search-tree Pruning | Chapter 7 |
| Spring Break, March 17–25 | ||
| Mar. 26, 28, 30 | Heuristic Search Methods | Chapter 7 |
| Apr. 2, 4, 6 | Dynamic Programming | Chapter 8 |
| Apr. 9, 11, 13 | Dynamic Programming, continued | Chapter 8 |
| Apr. 16, 18, 20 | Problem reduction; NP problems | Chapter 9 |
| Apr. 23, 25, 27 | NP Completeness; Approximation Algorithms | Chapter 9 |
| Apr. 30 | Wrap-up and Review. | Chapter 10 |
| May 6 | Final Exam: Sunday, May 6, 1:30–4:30 PM | |
