CS 8 Course Materials, Winter 2009

Handouts

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. Jan. 14, 2009	Wed. Jan. 21, 2009
PS-2	Graphs & Finite Automata	Wed. Jan. 21, 2009	Wed. Jan. 28, 2009
PS-3	Clustering Time Series	Wed. Jan. 28, 2009	Wed. Feb. 4, 2009
PS-4	Backtracking and n-Queens	Wed. Feb. 4, 2009	Wed. Feb. 11, 2009
PS-5	Kevin Bacon Game	Wed. Feb. 11, 2009	Wed. Feb. 18, 2009
PS-6	Parsing HTML	Wed. Feb. 18, 2009	Wed. Feb. 25, 2009
PS-7	Tetris	Wed. Feb. 25, 2009	Mon. Mar. 9, 2009

Short Assignments

Number	Description	Issued	Due
SA-1	Simple Haskell Functions	Mon. Jan. 5, 2009	Fri. Jan. 9, 2009
SA-2	Alternate Area Function	Fri. Jan. 9, 2009	Mon. Jan. 12, 2009
SA-3	Drawing Nested Squares	Mon. Jan. 12, 2009	Wed. Jan. 14, 2009
SA-4	Principal Types	Wed. Jan. 14, 2009	Fri. Jan. 16, 2009
SA-5	Currying & Composition	Wed. Jan. 21, 2009	Fri. Jan. 23, 2009
SA-6	Implementing MapPriorityQueue	Wed. Jan. 28, 2009	Fri. Jan. 30, 2009
SA-7	Inductive Proofs	Fri. Jan. 30, 2009	Mon. Feb. 2, 2009
SA-8	Parsing	Wed. Feb. 11, 2009	Mon. Feb. 16, 2009
SA-9	Dropping Tetris Pieces	Fri. Feb. 20, 2009	Fri. Feb. 27, 2009
SA-10	Type classes	Wed. Feb. 25, 2009	Fri. Feb. 27, 2009
SA-11	Polynomials represented as streams	Fri. Feb. 27, 2009	Mon. Mar. 2, 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
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	Mon. Jan 5	Introduction and Administrivia Examples: introExamples.hs Handouts: UnixGuide.pdf	SOE Preface, Chap. 1 (pg. xiii-xviii and 1-20)
2	Tue. Jan 6	Higher Order Functions Examples: introExamples.hs
3	Wed. Jan 7	Recursive Functions and Pattern Matching Examples: recursiveExamples.hs, dna2proteins.hs, wordLength.hs
4	Fri. Jan 9	Representing Shapes and Simple IO Examples: Shape.hs, lhs2hs.hs	SOE Chap. 2, begin Chap 3
5	Mon. Jan 12	Graphics and Drawing Shapes Examples: SimpleGraphics.hs, SierpinskiAlt.hs, Draw.hs	Chap. 4
6	Wed. Jan 14	Polymorphic and Higher-Order Functions Examples: hof.hs	Chap. 5
7	Fri. Jan 16	Currying, Sections, Anonymous Functions Examples: appendReverse.hs, moreHOF.hs	Chap. 9
	Mon. Jan 19	MLK day - class moved to x-hour
8	Wed. Jan 21	Composition, Motifs Examples: moreHOF.hs, Motifs.hs	Chap. 6
9	Fri. Jan 23	Finish Motifs, Trees Examples: Trees.hs	Chap. 7
10	Mon. Jan 26	ADTS, Map ADT, List implementation Examples: ListMap.hs	Chap. 7
11	Tue. Jan 27	Binary Search Trees, Set ADT, Priority Queue, more ADTs Examples: ListPriorityQueue.hs, PQDriver.hs, BSTMap.hs	Chap. 23
12	Wed. Jan 28	Proof by Induction Examples: DigraphMap.hs	Chap. 11
13	Fri. Jan 30	Finish proof by induction
14	Mon. Feb 2	Backtracking and Sudoku Examples: Sudoku.lhs, TestPJ.hs
	Tue. Feb 3	Review for Midterm
15	Wed. Feb 4	Breadth First Search, Queues, Stacks Examples: Stack.hs, Queue1.hs, Queue.hs
16	Fri. Feb 6	Databases Examples: Database.hs
17	Mon. Feb 9	Finish Databases Examples: Database.hs, NestedSquaresRead.hs
18	Tue. Feb 10	Parsing Examples: Parser.hs
19	Wed. Feb 11	More Parsing Examples: Expressions.hs
	Fri. Feb 13	Winter Carnival - classes moved to x-hour
20	Mon. Feb 16	Parsing Expressions, Region Module Examples: Expressions.hs, Region.hs	Chapter 8
20x	Tue. Feb 17	Balanced Binary Trees (optional x-hour)
21	Wed. Feb 18	Drawing Regions using Picture Module Examples: Picture.hs	Chapter 10, Chapter 13 through 13.3 only
22	Fri. Feb 20	User Coordinates and Tetris Framework Examples: DrawX.hs, ShapeX.hs, RegionEX.hs, PictureEX.hs, TetrisFramework.hs
23	Mon. Feb 23	Type Classes Examples: Qualified-types.hs, Class-tour.hs	Chapter 12, and skim Chapter 24
24	Wed. Feb 25	Streams Examples: streams.hs	Chapter 14
25	Fri. Feb 27	Streams Continued Examples: streams.hs, digitalLogic.hs	Chapter 14
26	Mon. Mar 2	Spelling Corrector Examples: spelling.hs, EditDistance.hs, big.txt
27	Wed. Mar 4	Introduction to Monads Examples: Monads.hs, Sheep.hs	Chapter 18
28	Fri. Mar 6	More Monads Examples: QueensM.hs, ParserM.hs	Chapter 18
29	Mon. Mar 9	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

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 F2007. [PDF]
Sample solution to Midterm F2007 [PDF]
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]
Question on Parsing with Monads [PDF]
Sample solutions Parsing with Monads [PDF]

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: 18-March-2009