# CSci 2041: Advanced Programming Principles Fall 2017

### Exam Dates and Times

First Midterm Exam: Oct 6, 2017, 11:15 a.m -- 12:05 p.m., Mol Cellular Bio 3-120

Second Midterm Exam: Nov 8, 2017, 11:15 a.m -- 12:05 p.m., Mol Cellular Bio 3-120

Final Exam: Dec 20, 2017, 1:30 -- 3:30 p.m., Willey 125
Note the location for the final exam, it is different from the regular classroom.

If you want to get to the homeworks list quickly, use this link. Note that this link skips information on the protocol that you must nevertheless still be aware of.

## New Information

12/13/17
• In case you missed this in class on Monday: you can turn in hw8 by 23:59 on Thursday, Dec 14, without incurring a penalty.

• I calculated an aggregate based on assigning the following weights to the homeworks: hw1 counts for 5 points, hw2 for 7, hw3 for 6, hw4 for 5, hw5 for 6 and hw6 for 7. I also included lab participation and effort for all the labs except lab15. The specific formula I used was the following where labiP and labiE stand respectively for participation and effort in labi:
```   aggr := (lab1P + ... + lab14P)/15 * 3.75 + (lab1E + ... + lab9-10E + ... + lab14P)/14 * 3.75
+ hw1 * 5/54 + hw2 * 7/69 + hw3 * 6/43 + hw4 * 5/42 + hw5 * 7/56 + hw6 * 7/30
+ mid1/10 + mid2/10
```
The most this aggregate could have totalled to is 62.98. Looking at the scores, if I were forced to determine a grade today, the cutoff for some kind of A (i.e. A- or A) would be around 54, for some kind of B (i.e. B-, B or B+) would be around 46 and for some kind of C would be around 34.5.

• In addition to the aggregate, I should reiterate that ALL homeworks have to be submitted to pass the course. If you have missed any of the homeworks, you should make sure to talk to me about it immediately.

12/10/17

12/09/17

• Homework 8 has been posted. The due date is Dec 13, 2017.

11/19/17

• Reading assignment: Read the page on the module system in the OCaml manual.

• Reading assignment: Chapters 9 and 10 of Jason Hickey's book.

• I had forgotten to indicate the points for each question in homework 6 when I posted the homework last Monday. I have now done this, so check the homework writeup again if you need this information.

• Some sources for discussions about references and (implicit) pointers in OCaml: a tutorial entitled Pointers in OCaml and a discusson about Mutable data structures that I found on the web.

• Some places to look up for more information about printing and reading: the Pervasives, Printf and the Scanf documentation in the OCaml manual.

10/12/17

• Please use the email address csci2041_f17d-tas atsign cs.umn.edu to communicate with the instructional staff on personal matters; please replace atsign by @ in the address shown. This way, you will be able to reach all the relevant people at once, rather than relying on one person to respond. Note however that only matters that are of a kind that cannot be addressed over Forum or during office hours will be responded to. This email is, for example, not an invitation to send code that you want debugged.

• In case you missed this in class, I have posted a paper about the MapReduce framework that you might find interesting to read here.

09/01/17

• Reading assignment: Read the OCaml for the Masses paper and also start looking at the first six chapters of the Introduction to Objective Caml book by Jason Hickey. Both items are also available from the papers section of the resources for the course.

• We will use the course web page extensively, especially for communication between lectures. Make sure to look at it regularly, perhaps every day. Any new information that has not been mentioned in class will be announced briefly in this space. However, note that you have the responsibility of attending lectures regularly and keeping abreast of anything that is mentioned in the lectures concerning new content on this page.

• We will also make extensive use of Forum bulletin boards that you can reach through the link above for discussions in this course. Please read the comments on etiquette for interactions that I have posted here and get ready to use this medium as quickly as possible.

• Homeworks will typically require you to turn in OCaml code of desired functionality in files with specific names. Make sure to follow these submission instructions carefully. We will try to set up an automated mechanism that will tell you whether or not your homework submission conforms to the requirements as you check it into the github repository. If we do that, you will have some help in checking if you have followed all the requirements for the homework. However, the onus is on you to make sure your submission conforms: there will be no "makeup grading" if your code fails because you have not adhered to the instructions. We would typically have moved on to looking at the next homework and will not have time to go back and grade any homeworks that are "fixed" after the fact.

## Contact Information

• Lecture Times and Place: MWF 11:15 - 12:05, Molecular and Cellular Bio, Room 3-120.

• Lab Sessions: All take place on Tuesdays in KH Keller Hall, Room 1-250, at the times mentioned below.

• Section 2: 08:00--08:50
• Section 3: 09:05--09:55
• Section 4: 10:10--11:00
• Section 5: 11:15--12:05
• Section 6: 12:20--13:10

• Instructor: Gopalan Nadathur (gopalan atsign cs.umn.edu), KH Keller Hall, Room 6-215, 612-626-1354.
Office Hours: MF 14:00--15:00.

• Joel Mabey (mabey004 atsign umn dot edu)
Office Hours: T 15:00--16:00.
Room: Keller Hall 2-209, 612-626-7512.
• Max Magnuson (magnu401 atsign morris dot umn dot edu)
Office Hours: Th 14:00--16:00.
Room: Keller Hall 2-209, 612-626-7512.
• Sam Marquart (marqu317 atsign umn dot edu)
Office Hours: W 08:30-09:30. Canceled 11/22
Location: Table 2, Atrium, Keller Hall.

• The undergraduate teaching assistants for the course will be holding office hours as per the following schedule:

• Mondays 8:00 -- 10:00 at Table 2, Keller Hall Atrium
• Mondays 16:30 -- 18:30 in Room 4-240 KH Keller Hall
• Tuesdays 16:00 - 18:00 at Table 2, Keller Hall Atrium
• Wednesdays 14:30 -- 17:00 at Table 1, Keller Hall Atrium
• Thursdays 9:00 -- 11:00 at Table 4, Keller Hall Atrium
• Thursdays 13:00 -- 14:00 at Table 1, Keller Hall Atrium
• Fridays 9:00 - 11:00 in Room 4-240 KH Keller Hall
• Fridays 15:30 -- 16:50 in Room 1-262 KH Keller Hall

In case you have not met them yet, the undergraduate teaching assistants are Christopher Bradshaw, Mikhaila Friske, Julia Garbuz, Charles Harper, Danyang Wang, and Tiannan Zhou.

## Course Prerequisites

The formal prerequisite for this course are CSci 1913 or 1933 and CSci 2011.

It is probably more important to understand what the prerequisites mean conceptually, and hence what will be assumed in this course.

• CSci 1913 or 1933 should have introduced you to programming through Java and/or Python. You should also have seen basic data structures like stacks, queues, trees, etc, and got a taste of recursion. The particular language you would have used or the particular kinds of computational tasks you would have seen is not extremely important. What is important is that you should feel comfortable with programming to an extent where you can start thinking about principles to analyze what you are doing and also about different and possibly better ways to organize and think about programming.

• CSci 2011 should have introduced you to mathematical principles such as sets, relations, functions, recursion, induction (as a means for reasoning about recursive definitions), logical reasoning, etc. All these are useful conceptual tools in understanding the programs we write more deeply, to analyze them precisely and thereby to design them better. This course will expect that you understand these tools well enough to start using them in the programming process.
If you have not taken the mentioned courses and/or are unsure of your preparation, please talk to me early in the term so that we can assess together what should be done.

## Course Text

There is no textbook for the course: the way we are going to study the subject matter is quite new to computer science curricula and a textbook for it has yet to be written. Don't let this intimidate you, though, and embrace the excitement of being at the cutting edge of learning.

I realize nevertheless that it is often reassuring to read material that you have seen in class from some other source. Towards this end, I will periodically put up readings from sources available on the web, I will try to write up notes from time to time, my lecture slides will be posted on the course website and all of us---the instructor and the graduate and undergraduate teaching assistants---will work with you to make the learning experience enjoyable and rewarding.

## Course Description and Objectives

This is a course to be taken by computer science majors around the end of the sophomore year. It will use a functional language to introduce a high-level approach to programming over complex data. It will emphasize a view of such data that abstracts away from their representation, using types as a vehicle for organizing them as values and for structuring computations over them. Advanced programming techniques that use ideas such as recursion, higher-order functions, lazy and eager forms of evaluation and infinite data objects will be explored. The possibility of exploiting parallelism arising from pure forms of expression evaluation will be examined. Other techniques and principles to be studied include search-based programming, modularity and concurrency. Programming projects that focus on symbolic computation will be used to impart the core ideas in the course; such projects may include writing parsers, type-checkers and interpreters for suitably circumscribed programming languages, and applications of search-based techniques.

## Course Content

Listed below are the topics that I plan to cover during the term. Don't read this as a weekly or even a linear schedule: the topics are interrelated and so we may often cover them in parallel.
• Types as a mechanism for organizing programs: Structuring data around types and structuring programs around data. Richness in typing through recursive, higher-order and polymorphic types.

• Computation as evaluation of expressions free of side-effects: Principles for structuring expressions such as binding of names, scopes, and environments. Richness in expressions through recursion, varieties of recursion. Implicit parallelism.

• Treating functions as first class objects: Embedding functions in data, passing them as arguments to other functions, returning them as results. Benefits in programming, explored via common higher-order functions such as map, filter, fold. Applications of higher-order functions in realizing parametric polymorphism and exposing control in evaluation.

• Proving properties of recursive programs: Designing functions around invariants, reasoning about invariants using induction. Types as a variety of invariants.

• Variations in evaluation strategies and their use in programming: Eager and lazy evaluation and their justification via strict and non-strict interpretation of functions. Programming techniques exploiting lazy evaluation, infinite data structures such as streams. Simulating laziness in eager languages.

• Introducing side-effects into computation: Type safe references, assignments, other side-effecting constructs, iterative control structures. Modelling effectful computation via state transforming functions, introducing side-effects into lazy languages. Object-oriented programming as combining environments with state. Circular data structures and their realization through references.

• Analyzing the complexity of programs: Estimating execution time via recurrence relations associated with recursive functions. Mutable and immutable data and their impact on programming techniques. Functional data structures.

• A glimpse of the implementation of high-level value-based programming: Mapping conceptual data objects to memory, memory usage, copying versus pointing. Garbage creation and automatic collection, memory management.

• Search-based computation: Search as a computational paradigm and its applications. Programming techniques for realizing search.

• Role of modularity in programming-in-the-large: Interface specifications, abstract data types. Language support for modular programming, interface checking as type checking. Module composition as function application.

• Concurrency. Asynchronous computation as a paradigm, coordination through communication; language mechanisms for organizing and controlling communication.

• Translation of principles into programming in mainstream, non-functional languages.
To ground our discussions, we will need to write programs in a real programming language. The language we will used is called OCaml.

Something to realize with regard to the list of topics above: these are topics that several of my colleagues and I concluded a few years ago would be great to provide you exposure to at this stage of your learning but not all of them have to be covered to make this a successful course. We will make some decisions as the semester moves along about what to focus on more sharply and, correspondingly, what to leave out to create more time for the selected topics. In making these decisions, I will take into account what absolutely must be covered and also where I sense the interests of the class to lie.

## Required Work

The different components of the work that you will have to do in this course are listed below.
• Attend all lectures and complete all assigned readings. The labs, homework assignments and exams that determine a grade will all draw on these materials. It is possible, indeed, likely, that assigned readings and the lectures will cover different aspects of a topic and you will be responsible for whatever is done in either. Remember also that lecture slides do not give the whole story so missing lectures can be detrimental.

• Attend lab sessions diligently. The labs will be structured so as to help you get comfortable with programming in OCaml in the beginning and get going on homeworks later in the term. Each of you have to turn in your individual work but we are okay with your arriving at solutions through discussions with your classmates and with getting detailed help from the instructional staff, especially if you get stuck with something. The general spirit is that we want the lab to be a friendly place that you go to to build your confidence about the material in the course that you then take into doing the homeworks (and the exams). Accordingly, we will not be grading the labs. However, we do not want you to blow away this opportunity so we will be noting attendance and also checking that you turn in something that indicates effort in each of the labs---see the grade components below.

• Participate in class and forum discussions. I will occasionally include exercises to be done in class in my lectures. Although you will not need to turn anything in, working through these exercises and volunteering solutions will impact on your confidence and also on what you learn. Participate enthusiastically in forum discussions for similar reasons.

• Do periodically assigned homeworks. You assimilate lessons better when you try to use them in actually solving problems on your own. This is especially true of programming. More importantly, you need to do every homework in this course and display reasonable effort in the process to pass the course. Note also that homeworks have to be done independently by each student. Taking help from anyone other than the instructor or a TA on any aspect of a homework that counts for grade constitutes cheating. We do often look up things in books and, nowadays, on the web. If what you have looked up is reflected substantially in your work, you must acknowledge the source in what you turn in. Not doing so is considered plagiarism, a particularly bad form of cheating. Another point that is sometimes missed: giving help to others on assigned work is also prohibited and will incur similar sanctions.

• Take the three exams during the term. Record the dates for the exams mentioned at the top of this document in your calendar. These exams will be closed book---there isn't a textbook for this course that you can open---so you should prepare accordingly. Also note that there will be no makeup exam. If you miss an exam for a university-sanctioned reason and you provide me with the needed documentation, I will conduct an oral exam to ensure you have knowledge of the content tested by the exam and then determine a grade based on the other components in the course.

Different components of the required work will contribute as follows to the final grade.
• Homeworks will constitute 45% of the grade with the following further qualifications:

The division of credit across different homeworks will be based on content, something that will be determined only in the course of the term.

• Lab attendance and participation will constitute 7.5% of the grade. To assess attendance, we will use both your physical presence in the lab and the material you turn in for each lab by 5:00 p.m. on the Friday of the week of the lab.

• Exams will constitute 45% of the grade, further subdivided as follows: the two mid-terms will count for 10% each and the final will count for 25%. All exams must be taken to pass the course, with the caveat that I will conduct an oral exam to account for an exam missed for a documented and university sanctioned reason.

• Class and forum participation will count for the remaining 2.5%. From a practical perspective, this essentially means that participation will play a role in determining borderline cases in translating aggregate scores into letter grades.
Note that the translation to a letter grade will be based on a curve. Don't read this as putting you in competition with each other. The reason why I prefer to use this method is that it makes it possible to give you interesting problems in the homeworks and exams. If these turn out to be too difficult, they will be so for your classmates too, and there will be an automatic correction.

I will put information up about possible locations of cutoffs towards the end of the term. The one helpful thing I might say right now: based on experience with other courses I have taught, you should get a C- or higher grade if your aggregate from all the work is over 55%.

Finally, make sure to track the scores on different components of the required work that we post on Moodle for accuracy. Questions about grading and errors in grade entry must be reported no more that 2 weeks after the scores have been posted and the feedback has been provided.

## Policy on Lateness

I reiterate below the points made earlier about missed exams and lateness:
• There will be no makeup-exams and homeworks submitted late will not get any credit. Note that homeworks must still be submitted, even if they are late, to pass the course.

• I will find a way to avoid a penalty if a homework or exam was missed because of a documented and university sanctioned reason as explained above.

• There will be no makeup regrading for homeworks that do not adhere to the relevant submission protocol.

At the outset, you are strongly encouraged to discuss material in the course with others in the class. Using Forum is a great way to do this. Discussions of this sort benefit everyone: they can clear up bottlenecks in understanding and explaining things to others also sharpens your own understanding. It is also possible that homeworks contain errors or ambiguities and discussions can help clear such matters up.

This being said, any work that you turn in for a grade is expected to be representative of your independent thinking. You may discuss assignments with each other to the extent that this clarifies your understanding of what is being asked, but this discussion must stop before it gets anywhere near the details of a solution. If you need help at this point, you should seek this from the instructor or the teaching assistant who are in a better position to decide what is and is not appropriate. In a similar vein, it is not acceptable to simply reproduce solutions to problems that you obtain from someone outside of class. Note in particular that copying someone else's work from the web without proper attribution constitutes plagiarism, a rather serious offense in academic work.

There will be penalties for breaches of this policy, ranging from no credit for the work in question to a failing grade in the course. To ensure fairness and in keeping with University policy, suspected breaches of the policy will be reported to the Office for Community Standards. On a more personal note, this kind of dishonesty interferes seriously with your own ability to learn and so there is no benefit to it in the long run.

Two further comments on this subject. First, in a course that involves programming, there is sometimes the temptation to make superficial changes to programs obtained from someone or somewhere else in the hope of camoflaging the source and to turn it in as one's own work. Lots of tools have been designed to detect this kind of behaviour and they really work! We will certainly be using them in this course. To keep things simple both for you and for us, resist such temptations should they arise.

Finally, For those of you who seem to be understanding the material in the course well and are enthused by this, I would like to encourage your being helpful to others. However, please be aware that there is a point beyond which such help is in breach of the academic honesty policy and can invoke all the described sanctions. More personally, note that such help can be detrimental to someone else's learning. One particular situation to be aware of is when you respond to queries on the discussion fora. Give thought to whether or not you will be letting out solutions to problems that your colleagues should have a chance to think through for themselves. The TAs amd the instructor will try to monitor this aspect towards guiding you in deciding when responses and help you provide has the danger of crossing the boundary of legitimacy, but we will need you to be cooperative and responsible as well.

Note:The department has a default set of policies regarding academic conduct that you will find here. These policies are effective for anything that is not explicitly covered above.

## The Disability Resource Center

The University of Minnesota is committed to providing all students equal access to learning opportunities. The Disability Resource Center (DRC) is the campus office that works with students who have disabilities to provide and/or arrange reasonable accommodations.

• 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.
If you feel this information is relevant to you please don't hesitate to follow up; it must be our joint goal to get the best out of every one and having the right environment to perform is important towards this end.

## Mental Health Resources

As a student you may experience a range of issues that can cause barriers to learning, such as strained relationships, increased anxiety, alcohol/drug problems, feeling down, difficulty concentrating and/or lack of motivation. These mental health concerns or stressful events may lead to diminished academic performance or reduce your ability to participate in daily activities. University of Minnesota services are available to assist you with addressing these and other concerns you may be experiencing. You can learn more about the broad range of confidential mental health services available on campus from the Student Mental Health website.

Last modified: Dec 13, 2017. Page maintained by gopalan atsign cs dot umn dot edu.

The views and opinions expressed in this page are strictly those of the page author(s). The contents of this page have not been reviewed or approved by the University of Minnesota.