Instructor	Textbooks	Course Work	Academic Honesty	Possible Class Formats	Schedule And Assignments
Deadlines	Collaboration	Cell Phones	Accommodations	Grading	Student Comments on Readings

Overview

CSC 301 examines the design, implementation, and efficiency of algorithms, extending the study begun in CSC 151 and continued in CSC 161, CSC 207, and CSC/MAT 208 or MAT 218. The course has four main foci:

• Alternative strategies in the design of algorithms,
• Relationships between algorithms and data structures:
  • Some algorithms (e.g., numerical methods) solve problems with little need for extensive data structures,
  • Some algorithms evolve to support abstract data types (e.g., dictionaries) and their underlying data structures (e.g., arrays and linked lists), and
  • Some algorithms require careful record keeping, requiring the design and use of their own internal data structures (e.g., residual networks in network-flow problems).
• Careful analysis of the efficiency of these algorithms, regarding both run-time performance and resource use.
• Techniques for establishing algorithm correctness.

Goals

More specifically, CSC 301 has these high-level goals:

• to gain proficiency in the use of a variety of strategies for algorithm development
• to understand and apply fundamental algorithms to a range of problems
• to learn representative algorithms that are largely independent of data structures, algorithms that support abstract data types and data structures, and algorithms that utilize their own data structures for record keeping
• to learn techniques for analyzing algorithms, such as instruction counts, recurrence relations, probability theory
• to understand and apply methods for showing the correctness of algorithms to solve sample problems

Objectives

The objectives of CSC 301 include these capabilities:

• Students should be able to identify and explain several strategies for algorithm development and provide at least one example illustrating each strategy.
• Students should be able to explain, implement, and analyze fundamental algorithms from several application domains, such as trees, graphs, strings, and dictionaries.
• When several different algorithms are available for a task, students should be able to apply careful analysis to determine conditions under which one algorithm is better or worse than another.
• Since algorithms are normally designed to help solve problems, students should be able to provide formal arguments establishing that proposed algorithms meet their respective specifications.

Henry M. Walker

Office: Science 3811
Telephone: extension 4208
E-mail: walker@cs.grinnell.edu

Office hours are posted weekly on the bulletin board outside Science 3811, with additional hours possible by appointment. You may reserve a half hour meeting by signing up on the weekly schedule, but please sign up at least a day in advance.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Third Edition, Cambridge, Massachusetts: The MIT Press, 2009; ISBN 978-0-262-00384-8.

Additional Notes:

• Java programs for algorithmic analysis
• Henry M. Walker, Notes on Hashing
• RB-insert-insert-fixup and RB-insert-delete-fixup from Cormen et al
• Alternative computations for the Fibonacci sequence
• Notes on Optimal Binary Search Trees

While the schedule for this course is expected to evolve, a Tentative Class Schedule is available in .dvi , pdf, and postscript formats.

Course Work will involve a combination of the following activities.

• Written Assignments: Exercises will be assigned regularly throughout the course. These assignments may be done individually (allowed) or in groups of 2 (preferred). (But each student will need to notify the instructor by Friday about their preference for the following week. If the preference is not communicated by 5:00 pm on Friday, it will be assumed the student wants to participate in a group for the following week.)

• Daily Summaries/Questions: In preparation for at least 25 class meetings (except tests), each student is expected to read the assigned materials and use Blackboard on Pioneer Web to complete the following form:

  • Summarize a main idea underlying the reading (in 3-6 sentences), or
  • Ask one or more question on material that is not clear or requires additional discussion.

  Daily summaries/questions are due by 5:00 pm the day before class; materials submitted after 5:00 pm will not be counted or considered. If Blackboard is down for any reason, students should email the instructor by the 5:00 pm deadline.

  For material not covered by questions, students should be prepared to join class discussions by helping to answer questions.

• Small-group Presentations: For two assignments, groups of students will present material on an assigned topic to the class. Before break, presentations will involve groups 3 students (labeled A, B, C, ... on the daily schedule), and after break, presentations will involve groups of 2 students (labeled 0, 1, 2, ... on the daily schedule).

• Programming Assignments: There will be several programming assignments to highlight specific algorithms and provide a framework for an experimental investigation of algorithm efficiency.

• Tests: Two tests are tentatively scheduled for Friday, 27 September, and Friday, 8 November. Although initial course planning has scheduled these tests to be in class, discussions with the students may change one or more of tests to be take-home assignments.

• Exam: Toward the end of the semester, the class will discuss the options of an in-class or oral final exam. If the class decides that an in-class final exam is a viable option, then those taking the in-class final will take the exam on Thursday, 19 December 2013 at 9:00 am, following the College's published schedule. If the class decides that an oral final exam is a viable option, then those taking the oral exam will be able to choose a time slot during exam week.

• Extra Credit Opportunities: Computer science is a wide-ranging discipline, and courses can cover only selected pieces. To encourage students to expand their horizons, students may earn 2 points extra credit for each Thursday Extra or other departmental talk, by attending the talk and writing a short (4-8 sentence) summary or response. Logistically, when a reasonable statement is received, the student will receive 2 points extra credit counted toward homework assignments. Additional extra credit opportunities may be announced through the semester. To receive credit, the summary should be received within two weeks of the event.

The assignment page for this course specifies whether or not collaboration is allowed for each assignment.

In particular, this means that you may work in groups of two or three on selected assignments for which collaboration is allowed. For this course, academic honesty requires the following practices:

• All academic work at Grinnell College must follow standard academic practice regarding quotation, paraphrase, and citation. Grinnell's Student Handbook provides basic guidelines.
• When working on homework, either individually or in a group, you may use any written source. However, the normal rules of citation must be followed, as described in the Student Handbook.
  • You must cite statements in the textbook, if you use them to guide your work.
  • You must use quotation marks or block quotes, if you quote outside materials directly — either from a paper, article, book, or online source. A full citation also is needed, with sufficient detail to allow easy checking of the material. (For example, just citing "www.wikipedia.org" or an organization's home page is inadequate.)
  • Although the Web can be useful for reference, you are advised that much material on the Web is of poor quality.
  • You are responsible for the quality of what you turn in, regardless of the source of the material.
• If a group of two or three people work together on an assignment, the group should turn in one written report, and all names in the group must appear at the top of the first page.
• If a student talks to someone else about on an individual problem (but this is not part of a 2-3 person group), then the assistance should be cited in a statement at the end of the problem. For example, one might write, "I talked about the solution to this problem with the Director of the Math Lab", or "Mr./Ms. ---, a tutor in the CS Open Lab, led me to Steps 3 and 4 in this solution".

Late Work will not be accepted, as it interferes with normal grading and with preparation for other parts of this course.

Although dates for labs, programming assignments, tests, and the final exam are firm, I understand that circumstances arise when you are not able to attend class.

• When circumstances are known ahead of time (e.g., academic activities, athletic events), I expect you to make arrangements with me before the activity occurs. Normally, we will identify an alternative date for the due date or test.
• When circumstances cannot be reasonably anticipated (e.g., illness, family emergencies), I expect you to notify me as soon as is reasonably possible. (Email is fine.) In the case of medical problems, I expect a written note from a medical professional or counselor that indicates that your health interfered with the course activity. (I do not need to know any details of the medical problem, but I do need to know that you sought help and that the medical professional believed meeting the deadline would likely interfere with your health.)

In addition, if an assignment involves programming or experiments involving MathLAN, then an extension of one class day is automatically granted if the department's Linux network is down for an unscheduled period of four or more hours during the preceding the assignment. Note that this exemption does not apply for assignments that can be handwritten.

Collaboration often will be allowed on some problems from the textbook and on some programming assignments. However, collaboration normally will NOT be allowed on supplemental problems, other programming assignments, and tests. To avoid confusion, the rules for collaboration on homework are included in the specification of each assignment.

Cell phones, text-messaging devices, and other social-networking connections may not be used in this class. If you bring such equipment to the classroom, it must be turned off before the class starts and stay off throughout the class period. Use of such equipment is distracting to those nearby and will not be tolerated.

If you have specific physical, psychiatric, or learning disabilities and require accommodations, please let me know early in the semester so that your learning needs may be appropriately met. You will need to provide documentation of your disability to the Directory of Academic Advising. Feel free to talk to me if you have questions or want more information.

This instructor's grading philosophy dictates that the final grade should ultimately be based upon each student's demonstration of her or his understanding of the material, not on the performance of the class as a whole nor on a strict percentile basis. The following scheme is proposed as a base for how the various assignments and tests will be counted in the final grade.

This document is available on the World Wide Web as

     http://www.walker.cs.grinnell.edu/courses/301.fa13/index.shtml

created 15 April 2011 revised 17 June 2013 presentation grading clarified 30 October 2013
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.