|
|
Here is what the ORC has to say about COSC 8:
Motivated by applications in the arts, sciences, social sciences, and computer systems, this course develops skills in solving problems computationally. Topics covered include representation (how to capture computationally the objects and processes of a problem), abstraction (how to build high-level, multi-purpose toolkits for manipulating representations), recursion and modularity (how to break problems into subproblems and combine the solutions), reasoning (how to understand what a computation is doing), and concurrency (how to deal with multiple simultaneous processes). These concepts are taught within a functional programming language that supports them well; they are applied in a series of programming labs solving fun application problems.
Prerequisite: Computer Science 5, or placement in
Computer Science 8 via Advanced Placement or departmental exam.
Dist: TLA.
Now that you've got some programming experience, let's use it to do some fun stuff! We'll construct animations, analyze biological sequences, search social networks, play games, parse and manipulate HTML, identify clusters in data sets, solve puzzles like Sudoku, simulate electronic circuits, and more. And, while we're doing that, we'll also develop expertise in core programming techniques useful throughout computer science. We'll use a language called Haskell, which makes it easy to quickly and incrementally develop solutions to these problems, while really making clear (and enforcing) the underlying core concepts.
You know how to program in one paradigm, which is an object-oriented procedural paradigm. Assignment statements, loops, and the ideas of sequential processing are basic building blocks. In the functional paradigm the emphasis is different. Recursion and functions come to the fore, especially higher-order functions (functions that take functions as arguments). At first this approach may seem weird, but as you get into the course you should come to appreciate its power to allow you to abstract and to think about and express your programs at a higher level. The programs that you write in Haskell will usually be much shorter than equivalent programs in Java. We will often be able to do in a line or two what would take half a page or so in a procedural language.
This is not, however, a course about the Haskell language! Haskell just happens to be the notation that we have chosen for writing programs. The major goals of the course are to develop your skills and vocabulary for reasoning clearly about programs and programming, and to provide a toolbox of modern programming techniques that will be applicable in almost any language.
| # | Date | Topic | Readings |
|---|---|---|---|
| 1 | Mon. Jan 7 | Introduction and Administrivia Examples: introExamples.hs Handouts: UnixGuide.pdf |
SOE Preface, Chap. 1 (pg. xiii-xviii and 1-20) |
| 2 | Tue. Jan 8 | Recursive Functions and Pattern Matching Examples: recursiveExamples.hs, dna2proteins.hs, wordLength.hs |
|
| 3 | Wed. Jan 9 | Continuation of Recursive Functions and Pattern Matching | |
| 4 | Fri. Jan 11 | Representing Shapes and Simple IO Examples: Shape.hs, lhs2hs.hs |
SOE Chap. 2, begin Chap 3 |
| 5 | Mon. Jan 14 | Graphics and Drawing Shapes Examples: SimpleGraphics.hs, SierpinskiAlt.hs, Draw.hs |
Chap. 4 |
| 6 | Wed. Jan 16 | Polymorphic and Higher-Order Functions Examples: hof.hs |
Chap. 5 |
| 7 | Fri. Jan 18 | Currying, Sections, Anonymous Functions Examples: appendReverse.hs |
Chap. 9 |
| Mon. Jan 21 | MLK day - class moved to x-hour | ||
| 8 | Wed. Jan 23 | Composition, Motifs Examples: moreHOF.hs, Motifs.hs |
Chap. 6 |
| 9 | Fri. Jan 25 | `Finish Motifs, Trees Examples: Trees.hs |
Chap. 7 |
| 10 | Mon. Jan 28 | ADTS, Map ADT, List implementation Examples: ListMap.hs |
Chap. 7 |
| 11 | Wed. Jan 30 | Binary Search Trees, Set ADT, Priority Queue, more ADTs Examples: DigraphMap.hs, ListPriorityQueue.hs, PQDriver.hs, BSTMap.hs |
Chap. 23 |
| 12 | Fri. Feb 1 | Proof by Induction | Chap. 11 |
| 13 | Mon. Feb 4 | Backtracking and Sudoku Examples: Sudoku.lhs, TestPJ.hs |
|
| 14 | Tue. Feb 5 | Breadth First Search, Queues, Stacks Examples: Stack.hs, Queue1.hs, Queue.hs |
|
| 15 | Wed. Feb 6 | Databases Examples: Database.hs |
|
| Fri. Feb 8 | Winter Carnival - classes moved to x-hour | ||
| 16 | Mon. Feb 11 | Finish Databases Examples: Database.hs |
|
| 17 | Wed. Feb 13 | Parsing Examples: Parser.hs |
|
| 18 | Fri. Feb 15 | More Parsing Examples: Expressions.hs, NestedSquaresRead.hs |
|
| 19 | Mon. Feb 18 | Parsing Expressions, Region Module Examples: Expressions.hs, Region.hs |
Chapter 8 |
| 20 | Wed. Feb 20 | Drawing Regions and User Coordinates Examples: Picture.hs, DrawX.hs, ShapeX.hs |
Chapter 10, Chapter 13 through 13.3 only |
| 21 | Fri. Feb 22 | Tetris Framework and Type Classes Examples: RegionEX.hs, PictureEX.hs, TetrisFramework.hs, Qualified-types.hs, Class-tour.hs |
Chapter 12, and skim Chapter 24 |
| 22 | Mon. Feb 25 | Streams Examples: streams.hs |
Chapter 14 |
| 23 | Wed. Feb 27 | Streams Examples: streams.hs, digitalLogic.hs |
Chapter 14 |
| 24 | Fri. Feb 29 | Spelling Corrector Examples: spelling.hs, EditDistance.hs, big.txt |
|
| 25 | Mon. Mar 3 | Introduction to Monads Examples: Sheep.hs |
Chapter 18 |
| 26 | Wed. Mar 5 | More Monads Examples: QueensM.hs, ParserM.hs |
Chapter 18 |
| 27 | Fri. Mar 7 | State Monads Examples: State.hs, MemoS.hs, EditDistanceM.hs, Fib.hs, StateT.hs, ParserST.hs, Fibonacci.hs, SimpleMemo.hs, EditDistanceSM.hs, Main.hs |
Chapter 18 |
The professor and graduate TA hold regular office hours. There will also be a course staff member present in Room 005 Sudikoff four evenings a week throughout the term. There is also a mailing address that goes to the entire course staff, and the first one to see it will try to answer your question.
There is one required textbook for this course:
The Haskell School of Expression:
Learning Functional Programming Through Multimedia,
by Paul Hudak.
ISBN 0-521-64408-9, published by Cambridge University Press.
This text should be available both at The Dartmouth Bookstore and at Wheelock Books; it can also be ordered online.
Unfortunately, this book has a number of typos, some of which can be quite confusing. Fortuantely, there is an errata page. I strongly urge going to erata.htm and making the corrections in your book. It will reduce confusion later.
There will also be course handouts and lecture notes, available online. The final, definitive version of all course materials is the course web site. You are responsible for checking the web site for updates and corrections.
The Haskell compiler that we will be using is the Glasgow Haskell Compiler (GHC), developed by a team of programmers at the University of Glasgow. Versions of GHC are available for Macintosh, Windows, and Unix systems, so you can use the compiler on whatever kind of machine you happen to possess. We will generally be using it in its interactive interpreter mode (GCHI), but it is also possible to use it to compile stand-alone applications.
On top of GCH, we will be using the SOE Graphics package developed for our textbook. (It is a stable subset of a larger graphics package for Haskell.)
Students are responsible for all material in the assigned readings, as well as material covered in lectures. There will be about seven problem sets (homework assignments), ten or so short assignments, a midterm exam, and a final examination. In the past problem sets included drawing a fractal snowflake, doing time-series analyis of stock data, solving the n-Queens problem, playing the "Kevin Bacon" game using a database of movie and actor information, parsing and manipulating HTML, and writing a Tetris program. Each problem set may include written exercises as well as a programming assignment.
Course grades will be based on:
Problem sets are detailed programming assignments that challenge you to use the ideas we study in lecture to solve new problems. You will generally have a week or more to complete a problem set, and the results are graded on a percentage scale based on both correctness and style.
Correctness describes the degree to which your solution correctly solves the assigned problems, and convincingly demonstrated that your solution is correct. Style measures the organization and readability of your code, the appropriate use of Haskell features, the clarity of your documentation, and the efficiency of your algorithms.
Short assignments are designed to provide practice and feedback to aid your understanding of the course material. The possible grades for a short assignment are 0, 1, or 2. A grade of 2 means your solution is correct and good. A 1 indicates that your solution needs work. A 0 is given if nothing of substance is turned in.
If you receive a 1 on a short assignment, you may, at your option, re-work your solution and resubmit it to be re-graded. If your resubmitted short assignment receives a 2, that grade replaces your 1. You may only resubmit once for a given short assignment, and resubmissions must be received no later than the first regular class period after the original result was handed back to the class, whether or not you attended class on the day the result was handed back. Please attach the original graded assignment to the resubmitted version.
Only short assignments may be resubmitted in this way. Regular problem sets and exams will only be graded once. Note, however, that this policy does not apply to errors in grading. If you suspect we have made a mistake in the grading of any assignment or examination, you may (and should) bring it to our attention promptly -- fixing grading errors does not count as resubmission!
Throughout the term, there may be opportunities to earn points of extra credit. For instance, some problem sets have specific extra-credit problems. Furthermore, any exceptionally clever, creative, or insightful work may be awarded extra credit points.
As its name suggests, extra credit is always optional, and you should never feel that you have to do extra credit problems. Extra credit points are recorded separately from other grades. When assigning grades at the end of the term, some people are on the borderline between two grades. If you are in such a situation, extra credit work is a good reason for giving you the higher grade. Extra credit can also lead to a citation.
Extra credit points can only help, never hurt, your final grade, regardless how much or how little extra credit you or your classmates choose to do.
You should not view extra credit as a substitute for doing good and thorough work on your assignments! Extra credit is no substitute for keeping up with the main work of the course. On the other hand, for those who become excited by some of the new ideas we'll explore in this course, and wish to explore beyond the boundaries, I intend extra credit to serve as a means to recognize your exceptional effort.
Much of the learning in this course comes from doing the programming exercises. On some problem sets, you may work jointly with one (1) other person, if so stated. No more than two people may work together on a given problem set. If you choose to work with someone else, the following rules apply:
On short assignments, you must work alone unless otherwise stated in the assignment.
Under no circumstances may you hand in work done with (or by) someone else under your own name. If you have any doubt, credit any person(s) from whom you got help. Your code should never be shared with anyone, other than your partner (if you are working in a pair).
Any hard-copy or electronic sources used must be properly cited and acknowledged. The only exceptions to this rule are as follows:
However, you may not consult any solutions from previous terms' CS 8 assignments or CS 18 assignments, whether they are from faculty or other students. (CS 18 is an earlier version of CS 8.) Furthermore, any software or assistance provided to you by other sources must be properly cited and acknowledged. You may not look at exams from previous offerings of CS 8 or CS 18, except for ones that we distribute as sample exams.
We take the Honor Code very seriously, so please, if you are unclear on any matter regarding this policy, do not hesitate to see me in office hours, and I will be more than happy to answer your questions. It is always best to provide proper citations. Please ask first, if you are unsure!
Dartmouth provides public Macintosh, Linux, and PC facilities. You may use your own personal computer, or the public ones, at your option. Since the course software is available for a wide variety of operating system and hardware combinations, it doesn't really matter which platform you use. The computer science department provides computer facilities in Sudikoff for this course:
To get access to the laboratories, see Kelly Clark in Rm. 101 Sudikoff between the hours of 8:30 AM and 12:00 noon or 1:00-4:00 PM, weekdays, to fill out an access agreement. Be sure to bring your Dartmouth ID card with you! Your access may not be activated until the following business day, so please plan ahead!
You are entitled to use the computer laboratories in rooms 001 (Linux), 003 (Windows), or 005 (Macintosh) in Sudikoff. All three will have the course software loaded on them.
You can make use of any of these machines for the course. We will not be teaching you how to use Unix in this course, apart from the basics needed to get around on the lab machines and Terminal window.
In order to use the Windows and Linux machines in Sudikoff, you will need a login account. We will tell you who to email to get accounts.
Keep in mind that it might take a day to get your account created, so please don't leave this 'til the night before a problem set is due, if you intend to use the lab machines! Macintoshes do not require logins.
CS 8 was developed at Dartmouth College by Scot Drysdale and Chris Bailey-Kellogg, with substantial assistance from Michael J. Fromberger in the summer and fall of 2007. It replaces CS 18, a similar course using Scheme that was based on 6.001, developed by Gerry Sussman and Hal Abelson in the EECS Department at Massachusetts Institute of Technology (MIT). Bruce Donald developed CS 18 at Dartmouth.
The course web site is built on one written by Michael J. Fromberger using only 100% recycled fair-trade nonrecombinant organically home-grown binary digits, with help from Linux and Mac OS X.