CS 8 Course Materials, Fall 2009

Handouts

Guide to Basic Unix Commands
Class notes prepared by Nicole Yunger Halpern, a former CS 8 student
Mathematics of Fractal Dimension (a sidebar to PS-1)
Haskell Quick Reference. Summarizes a number of common Haskell functions. Provided for exams.
Haskell Cheat Sheet. Explanations of the way that language constructs work. It is useful for getting the nitty-gritty details once you have a basic idea of what the construct does. Written by Justin Bailey.
Guide to Parser Functions

Links to Haskell Information

It's Time to Get Good at Functional Programming - an article from Dr. Dobb's Portal explaining why companies like Ericsson are using functional languages to write programs for multi-core processors.
Learn Haskell in 10 Minutes - A short tutorial with useful information.
Yet Another Haskell Tutorial - A tutorial covering all of Haskell (including parts we won't discuss). A good reference.
Real World Haskell - An alternate text. As the title suggests, it has a number of real-world examples.
Haskell.org's Wiki - Contains links to anything that you might want to know about Haskell (and lots that you don't!).
Haskell 98 Language and Libraries - The full language description. Part II (Libraries) is useful. Part I is very formal and can be hard to decipher.
The Glasgow Haskell Compiler - Information on the compiler that we will be using. The link to "Documentation" gets you to a User's Guide. The section on GHCi is useful.
zvon.org - Another nice reference for Haskell. In general, zvon provides several nice references and tutorials for various programming languages.

Problem Sets

Number	Description	Issued	Due
PS-1	Snowflake Fractal	Wed. Sep. 30, 2009	Wed. Oct. 7, 2009
PS-2	Graphs & Finite Automata	Wed. Oct. 7, 2009	Wed. Oct. 14, 2009
PS-3	Clustering Time Series	Wed. Oct. 14, 2009	Wed. Oct. 28, 2009
PS-4	Backtracking and n-Queens	Mon. Oct. 19, 2009	Wed. Nov. 4, 2009
PS-5	Kevin Bacon Game	Wed. Oct. 28, 2009	Wed. Nov. 11, 2009
PS-6	Parsing HTML	Wed. Nov. 4, 2009	Wed. Nov. 18, 2009
PS-7	Tetris	Wed. Nov. 11, 2009	Wed. Dec. 2, 2009

Short Assignments

Number	Description	Issued	Due
SA-1	Simple Haskell Functions	Wed. Sep. 23, 2009	Mon. Sep. 28, 2009
SA-2	Alternate Area Function	Mon. Sep. 28, 2009	Wed. Sep. 30, 2009
SA-3	Drawing Nested Squares	Wed. Sep. 30, 2009	Fri. Oct. 2, 2009
SA-4	Principal Types	Fri. Oct. 2, 2009	Mon. Oct. 5, 2009
SA-5	Currying & Composition	Wed. Oct. 7, 2009	Fri. Oct. 9, 2009
SA-6	Implementing MapPriorityQueue	Wed. Oct. 14, 2009	Fri. Oct. 16, 2009
SA-7	Inductive Proofs	Mon. Oct. 19, 2009	Wed. Oct. 21, 2009
SA-8	Parsing	Wed. Nov. 2, 2009	Fri. Nov. 6, 2009
SA-9	Dropping Tetris Pieces	Mon. Nov. 9, 2009	Fri. Nov. 13, 2009
SA-10	Type classes	Wed. Nov. 11, 2009	Mon. Nov. 16, 2009
SA-11	Polynomials represented as streams	Wed. Nov. 18, 2009	Fri. Nov. 20, 2009

Sample Solutions

SA-1: sa1.hs
SA-2: sa2.hs
SA-3: sa3.hs
SA-4: sa4.txt
PS-1: Snowflake.hs , SnowflakeComp.hs
SA-5: sa5.hs
PS-2: Digraph.hs , FA.hs
SA-6: MapPriorityQueue.hs
SA-7: My solution, Michael Fromberger's solution (with EC)
PS-3: Clusters.hs , ClustersSD.hs ClusterDriver.hs
PS-4: Queens.hs SudokuEC.lhs
SA-8: ParserX.hs
PS-5: BFS.hs BaconGame.hs
PS-6: HTML.hs
SA-9: TetrisSA9.hs
SA-10: Rat.hs
SA-11: poly.hs
PS-7: Tetris.hs

Lecture Notes

#	Date	Topic	Readings
1	Wed. Sep 23	Introduction and Administrivia Examples: introExamples.hs Handouts: UnixGuide.pdf	SOE Preface, Chap. 1 (pg. xiii-xviii and 1-20)
2	Thu. Sep 24	Higher Order Functions Examples: introExamples.hs
3	Fri. Sep 25	Recursive Functions and Pattern Matching Examples: recursiveExamples.hs, dna2proteins.hs, wordLength.hs
4	Mon. Sep 28	Representing Shapes Examples: Shape.hs, lhs2hs.hs	SOE Chap. 2, begin Chap 3
5	Wed. Sep 30	Simple IO, Graphics, and Drawing Shapes Examples: SimpleGraphics.hs, SierpinskiAlt.hs, Draw.hs	Chap. 4
6	Fri. Oct 2	Polymorphic and Higher-Order Functions Examples: hof.hs	Chap. 5
7	Mon. Oct 5	Currying, Sections, Anonymous Functions Examples: appendReverse.hs, moreHOF.hs	Chap. 9
8	Wed. Oct 7	Composition, Motifs Examples: moreHOF.hs, Motifs.hs	Chap. 6
9	Fri. Oct 9	Finish Motifs, Trees Examples: Trees.hs	Chap. 7
10	Mon. Oct 12	ADTS, Map ADT, List implementation Examples: ListMap.hs	Chap. 7
11	Wed. Oct 14	Binary Search Trees, Set ADT, Priority Queue, more ADTs Examples: ListPriorityQueue.hs, PQDriver.hs, BSTMap.hs	Chap. 23
12	Fri. Oct 16	Proof by Induction Examples: DigraphMap.hs, Induction.hs	Chap. 11
13	Mon. Oct 19	Finish proof by induction
14	Wed. Oct 21	Backtracking and Sudoku Examples: Sudoku.lhs, TestPJ.hs
14x	Thu. Oct 22	Balanced Binary Trees (optional x-hour)
15	Fri. Oct 23	Breadth First Search, Queues, Stacks Examples: Stack.hs, Queue1.hs, Queue.hs
16	Mon. Oct 26	Databases Examples: Database.hs
17	Wed. Oct 28	Finish Databases Examples: Database.hs, NestedSquaresRead.hs
	Thu. Oct 29	Review for Midterm in x-hour, exam 7-10 pm
18	Fri. Oct 30	Parsing Examples: Parser.hs
19	Mon. Nov 2	More Parsing Examples: Expressions.hs
20	Wed. Nov 4	Parsing Expressions, Region Module Examples: Expressions.hs, Region.hs	Chapter 8
21	Fri. Nov 6	Drawing Regions using Picture Module Examples: Picture.hs	Chapter 10, Chapter 13 through 13.3 only
22	Mon. Nov 9	User Coordinates and Tetris Framework Examples: DrawX.hs, ShapeX.hs, RegionEX.hs, PictureEX.hs, TetrisFramework.hs
23	Wed. Nov 11	Type Classes Examples: Qualified-types.hs, Class-tour.hs	Chapter 12, and skim Chapter 24
	Fri. Nov 13	No Class
24	Mon. Nov 16	Streams Examples: streams.hs	Chapter 14
25	Wed. Nov 18	Streams Continued Examples: streams.hs, digitalLogic.hs	Chapter 14
26	Fri. Nov 20	Spelling Corrector Examples: spelling.hs, EditDistance.hs, big.txt
27	Mon. Nov 23	Introduction to Monads Examples: Monads.hs, Sheep.hs	Chapter 18
28	Mon. Nov 30	More Monads Examples: QueensM.hs, ParserM.hs	Chapter 18
29	Wed. Dec 2	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
	Fri. Dec 4	Review for Final Exam, 10-12

Practice Examinations

Approximately a week prior to each examination, a set of practice problems will be posted here. These problems are intended to give you examples of the type and scope of questions that are likely to be on the actual examination, to be used as a study aid. The Quick Reference linked below will be distributed at the exam. You are also allowed an 8.5 x 11 sheet of paper with your own notes on it. It should be handwritten or typeset in 10 point or larger font.

Practice Midterm Exam. [PDF].
Sample solution to Practice Midterm [PDF]
Midterm Exam F2008. [PDF]
Sample solution to Midterm F2008 [PDF]
Induction problem from final F2008 [TEXT]
Sample solution to Midterm F2008 [TEXT]
Quick Reference to be distributed at exams [PDF]
Practice Final Exam [PDF]
Sample solutions to Practice Final [PDF]
Final Examination F2007 [PDF]
Sample solutions to Final Exam F2007 [PDF]
Final Examination W2008 [PDF]
Sample solutions to Final Exam W2008 [PDF]
Parser guide to be distributed at the final [TEXT]

The final average will be computed based upon homework (problem sets), short assignments, and exams, weighted approximately as follows:

Problem Sets: 50%
Short Assignments: 10%
Exams: 40% (20% each)

Department of Computer Science, Dartmouth College, Hanover, New Hampshire, USA

Last modified: 04-December-2009