index.php

Main navigation | Main content

4 Credits

Lecture: MWF 1:25-2:15, Anderson 370

Labs:

Section 14: T 1:25-2:15, Keller 1-250

Section 15: T 2:30-3:20, Keller 1-250

Section 11: T 3:35-4:25, Keller 1-250

Section 12: T 4:40-5:30, Keller 1-250

Nick Hopper

Keller 4-211

hoppernj AT umn edu

Office hours are shown on the course google calendar - note that there may be some changes from week to week, so check that you are looking at the current week:

If you want to speak with one of us about the course and can't make one of the scheduled times, please send an email and we'll schedule a different meeting.

Textbooks:

There is no required textbook for the course; however, the course schedule will include links to required online readings and notes. Many of the readings come from the unpublished manuscript "Introduction to Objective Caml," by Jason Hickey, which is available at no cost online; another free online reference that students might find helpful is "Developing Applications with Objective Caml" by Chailloux, Manoury and Pagano.

The course is roughly divided into three units:

- Functional Programming in OCaml:
We'll learn the basics of structuring a program as a series of
(possibly) recursive expressions to be evaluated, examine the
relationship between general recursion, tail recursion, and iteration;
discuss using OCaml's strong static type system to build types that
match the data while abstracting away the representation of these data;
examine parametric polymorphism and higher-order types, and learn about
higher-order functions and their applications in programming.

- Analysis and Manipulation of
Programs We'll discuss the role of induction in reasoning about
recursion and iteration, both to analyze correctness and efficiency of
programs; further examine computation as expression evaluation; explore
the use of lazy evaluation to compute with cyclic and infinite data
objects; and explore programmatic representation and manipulation of
programs.

- Advanced Program Structures We'll learn about modularity in programming and OCaml's rich module system; techniques to express programs as units to be evaluated concurrently and in parallel; Side effects, type-safe references and iterative computation structures; and automated memory management in OCaml - how objects are laid out, created and collected when no longer needed.

Students who complete this course should be able to:

- Write OCaml expressions for common programming tasks involving iteration and recursion
- Understand common OCaml type errors and explain what they mean
- Develop simple abstract data types in OCaml
- Apply common higher-order functions to solve tasks involving iteration
- Prove the correctness of simple recursive OCaml programs using inductive data types
- Reason about and write programs that evaluate and transform program expressions
- Explain and use OCaml modules
- Explain side effects, references, and simple memory management concepts

You may not have realized this before, but proofs are programs. This is true in many senses: metaphorically, in that a proof is just a list of steps to convert an input (a set of assumptions) into an output, i.e., the conclusion; literally, in that many of the proofs in this class involve reasoning about programs; and in a very technical sense, a branch of logic known as constructive type theory actually establishes a one-to-one mapping between each program and the proof of some theorem. So if you learned to write good programs, you can learn to write proofs well. Ask yourself this: were you always good at writing programs? Probably not. How did you get better? By practicing, and seeing lots of examples of good programming. In this class, you will practice writing proofs; the textbook and lecture notes for the class will feature many examples of proofs.

The prerequisites for this course are CSci 1913/1933 and CSci 2011. From CSci 11X3 and 19X3 you will need to understand programming concepts like procedural abstraction, iteration and data abstraction. From CSci 2011 you will need to understand concepts like sets, relations, functions, and mathematical induction.

The course website includes a schedule of lectures for this course. The schedule includes the readings related to each class. Students are responsible for reading the appropriate materials for each lecture; we may not cover all of the reading material in the lecture but it may still be required for exams or homework. Lecture slides will usually be linked from the homepage before class, but always within one day following the corresponding lecture.

Grading for the class will be based on five components:

- 7 Homeworks (25%): we
will have seven homeworks, all of which will be due on Wednesdays.
The submission of any homework should be completed by 11:59pm on the Wednesday that it is due.

Due dates for all assignments are strict: all homeworks must be pushed at or before the specified time in order to receive full credit. Late homeworks turned in within 24 hours of the due date will be considered for 50% credit, and after that, a homework is worth 0 points, with no exceptions. More information about the protocol for submitting the homework and grade assignments will be included in each homework. Note that if you have not correctly followed the submission instructions on a given homework by the time it is due, this will count as a late homework, and if you have not correctly submitted a homework by the late submission cutoff, then you will receive 0 points for the homework.

Homework grading is performed by the TAs. If you have a question about homework grades, address it to the TAs. Only if something wholely unreasonable has occurred will the instructor intervene. Furthermore, there is a limit of seven days from the date that an assignment is graded for grading problems to be dealt with. After that period, such will not be considered.

Because everyone can have a bad week, each student's six highest homework scores will be used.

- 15 Labs (15%):
Lab work will be graded on attendance and participation, and must be
submitted by 11:59pm on the Thursday following each lab section.

- 15 Weekly Exercise Sets (10%):
Each week we will have a list of "exercise" questions similar to
problems in the lectures. Solutions must be submitted by
11:59am on Monday to receive full credit for the week's exercises.

- 12 Weekly Quizzes (25%
total): We will have a 20-minute quiz at the end of lecture each
Monday, with two exceptions noted on the class schedule. Each quiz can
cover any material up to the end of lecture on the preceding Friday. To
account for travel, illness, traffic and life's other difficulties that
might occur during the semester, each student's ten highest quiz scores
will be used.

- Final exam (25%): The course will have a cumulative, 2-hour final exam on Monday, December 18 at 8am.. The exam is closed-book, closed-notes, and no electronic devices may be used. However, each student may bring a one-sided single-page "cheat sheet" for use during the exam.

92
- 100 |
A |

90
- 92 |
A- |

86
- 90 |
B+ |

82
- 86 |
B |

80
- 82 |
B- |

76
- 80 |
C+ |

70
- 76 |
C |

66
- 70 |
C- |

63
- 66 |
D+ |

59
- 63 |
D |

0
- 59 |
F |

Every student is expected to turn in his or her own work for all assignments and exams in this class. This is not meant to block general discussion of HOW to approach homework problems: you are encouraged to discuss questions that clarify what the problems on the homework are asking, ask about possible errors in the problem descriptions, clarify what is expected of your solutions, and what resources you can use (for example) on the class forum. However, it is important that you do not proceed to discuss solutions to the problems and it is certain that sharing or copying another student's solution, (or from another source such as the Internet) whether on an exam or homework, is prohibited. Note that while it might be tempting to think that you can take another person's code, modify it a little and turn in a solution that does not look like the original, there are several tools that can detect when this has been done and we will be using such tools in this class. If we determine that you have submitted such code, we will treat this as an instance of scholastic dishonesty.

The University Student Conduct Code defines scholastic dishonesty as: submission of false records of academic achievement; cheating on assignments or examinations; plagiarizing; altering, forging, or misusing a University academic record; taking, acquiring, or using test materials without faculty permission; acting alone or in cooperation with another to falsify records or to obtain dishonestly grades, honors, awards, or professional endorsement. In this course, a student responsible for scholastic dishonesty will be assigned a penalty of an "F" or "N" for the course. If you have any questions regarding the expectations for a specific assignment or exam, or are unsure about posting a particular answer to the class forum, please ask us first.

- Students who have, or think they may have, a disability (e.g. mental health, attentional, learning, vision, hearing, physical or systemic), should contact DRC to arrange a confidential discussion at 612-626-1333 (V/TTY) or ds@umn.edu.
- Students registered with DRC and who have a letter requesting accommodations, are encouraged to talk to me early in the semester to discuss accommodations outlined in the letter.