Front Door

Questions? Ask them on Piazzza.

Welcome to the Spring 2011 session of Grinnell College's CSC 161, Imperative Problem Solving and Data Structures. The course is described, in part, in the official blurb. From my perspective, this course serves many purposes: It teaches you a new approach to algorithm design (the imperative paradigm); it introduces a number of tools you will use in your career, including Linux, Emacs, and Make; it further grounds your study of important data structures and algorithms; it introduces an imprortant programming language, C; and it gives you a particularly hands-on perspective on computer science.

In an attempt to provide up-to-date information, and to spare a few trees, I am making this as much of a paperless course as I can. Hence, materials will be in a course web.

Warning! Computers are sentient, stupid, and malicious. When things go wrong, don't blame yourself. Ask me for help.

Goals

Very rough draft!

By the time you complete this course, you should be able to

• Implement algorithms using traditional imperative techniques (assignment, loops, functions, etc.);
• Describe and design a variety of important data structures, including lists, stacks, and queues;
• Write Unit Tests for the algorithms and structures you design and implement;
• Navigate Unix and Linux systems and take advantage of core took chains on those systems;
• Design Make files for straightforward small to medium projects;
• ...

Basics

Meets: MTuWF, 11:00-11:50, Science 3813

Instructor: Samuel A. Rebelsky (rebelsky@grinnell.edu), Science 3824. Office hours: MWF 1:15-3:00. I tend to follow an open door policy: Feel free to stop by when my door is open or to make an appointment for another time. Check my schedule for more details.

Mentor: Andrew Hirakawa. Office hours TBD.

Grading (subject to change):

• Class participation: 10%
• Questions on readings: 15%
• Examinations: 45% (three exams and one optional final)
• Weekly assignments: 30% (due at 11 p.m. on Wednesday evenings)

Late Assignments: My experience shows that students who turn in work late learn significantly less than students who turn material in on time. (I'm not sure about cause and effect.) Hence, I strongly discourage late assignments. Late assignments are penalized one letter grade (or equivalent) per day (or fraction thereof) late.

Because I am concerned about your health and well being, I will waive the late penalty if (1) you start the assignment at least three days in advance of the due date; (2) you get to sleep by midnight the night before the assignment is due; (3) you expend a reasonable amount of effort to complete the assignment by midnight; (4) you turn in a form attesting to facts (1), (2), and (3) when the assignment is due; and (5) you talk to me ASAP about any problems you've had on the assignment.

In addition, every student will be granted two grace days that can be used for any homework assignment, for any reason. A grace day is an automatic extension until the next class period. Please use your grace days wisely: you may need them more later than you do now! I would appreciate hearing in advance by email if you intend to use a grace day on a particular assignment since this makes my bookkeeping easier. However, any assignment submitted late will automatically use a grace day, if you still have one to use. (This policy applies only to homework assignments and not to examinations or readings.)

Attendance Policy: Because this is a lab-based class and because I know students benefit from the presence of their colleagues, I expect you to attend every class period. In my experience, students who do not regularly attend class cause significant difficulties not only for themselves, but also for their classmates and for me. Hence, I have a strict attendance policy: Students with more than two unexecused absences will fail the class (or will be withdrawn from the class).

Of course, I realize that there a variety of legitimate reasons that you will be unable to attend class, including, but not limited to, academic events, athletic events, illness, and family emergencies. Whenever possible, you should contact me in advance if you will be unable to attend class. Otherwise, you should notify me as soon as possible after class. If you must miss a class because of illness, I want you, rather than Health Services, to notify me.

Extra Credit: Multiple kinds of extra credit are available.

• Particularly outstanding work in class or on an assignment or examination may earn you extra credit. In most cases, that extra credit will apply directly to the assignment or examination. In other cases, I will apply the extra credit to your overall grade in the class.
• I may suggest optional assignments throughout the semester. These assignments may be used to replace a low grade on an assignment or to enhance your overall grade in the course.
• In some cases, an assignment may have an explicit extra credit component.
• Particularly good questions or answers on Piazzza are likely to earn you extra credit.
• I consider it important that you take advantage of the many academic events that happen on campus (talks, concerts, etc.), particularly those sponsored by the Computer Science Department. I will do my best to mention these events at the start of class. You receive one unit of extra credit for each event you attend, with a limit of three units. (Each unit is worth 0.5 points in the computation of your final grade.)
• Grinnell students participate in a wide variety of activities and I consider it important that you support your colleagues in their endeavors. I will provide time for you to mention your events at the start of class. Students who support their colleagues by attending events will receive one unit of extra credit for each event they attend, with a limit of three units.
• For the last two kinds of extra credit, I will provide you with a checklist at the end of the semester and you will check off the events you attended.

Warnings:

• Like CSC151, CSC161 is likely to exercise different parts of your brain than you use in other classes. And, as in CSC151, you'll find that you have to think about problem solving at both a high-level and a detailed level.
• I teach CSC161 with an immersion style approach. That is, you'll work with large chunks of the language starting with the first day, and then go back and look at more details of each chunk.
• I am an inconsistent grader. Expect to gain more from doing work than from receiving feedback on the work.
• At times I will post your work or notes about you in the course web. I tend to leave everything available for past and future generations. If you would like the references to you deleted, please notify me after the semester has ended.

Good-Faith Grade Guarantee:

Students who make a good faith effort in this class will pass the class, with at least a C. A good-faith effort includes missing no more than two classes, turning in every homework assignment and reflections on at least 90% of the readings, and spending the requisite time on each examination.

Required Books

I've tried to choose books that you'll want to keep on your bookshelf long after the class is done.

Kernighan, Brian W. & Ritchie, Dennis, M. (1988). The C Programming Language, 2nd Edition: ANSI C. Upper Saddle River, NJ: Prentice-Hall.

The classic book on C, by the designers of the language. A bit denser than most books, but has very little cruft. I particuarly appreciate that the book helps you think like a real C programmer. The book, like the course, takes an immersion approach.

Mecklenburg, Robert (2004). Managing Projects with GNU Make, Third Edition. Sebastapol, CA: O'Reilly and Associates. Also available online at http://oreilly.com/catalog/make3/book/index.csp.

Make is one of the key tools Unix programmers use. This is an excellent introduction to the tool. We will focus on introductory chapters.

Raymond, Eric S. (2003). The Art of UNIX Programming. Addison-Wesley, Professional. Also available online at http://www.faqs.org/docs/artu/.

This book has very little detail on the standard Unix commands, but helps you think about why Unix variants have continued to exist for three decades. We will probably only skim this book.

Recommended Books

Harbison III, Samuel P. & Steele Jr., Guy L. (2002). C: A Reference Manual, Fifth Edition. Upper Saddle River, NJ: Prentice-Hall.

A more formal and more comprehensive definition of the language than is available in K&R.

Plauger, P. J. (1991). The Standard C Library. Upper Saddle River, NJ: Prentice-Hall.

More information than you'll ever need about the various library commands available to you. Clearer and better than the corresponding man pages.