# CSci 2041: Advanced Programming Principles Spring 2020

## Important End-of-Term Information

Some information that has already been communicated to you via email is highlighted below:
• The final exam will be conducted online via GradeScope on May 13, 2020. It will be a two hour exam that can be taken in the interval between 8:00 a.m. and 3:30 p.m. on May 13. You should use the link provided to you by email to access the exam during this time.

• You must be registered for this course under GradeScope to take the exam. Make sure to do this as soon as possible if you have not done it already.

• We have set up a collection of questions under GradeScope for you to experiment with towards get comfortable with the online exam format. To access this collection you should use the same link as that for the actual exam. We encourage you strongly to check this set up out; taking the mystery of the framework out of the equation will enable you to focus as much as possible on the intellectual content of the exam.

• Office hours for May 11 and 12 will follow a modified schedule to allow for a mix of one-on-one and group meetings. The specific schedule has been sent to you via email.

• Any outstanding issues that might impact on the grade must be discussed explicitly with the instructor by noon on May 12. Most of these issues are also expected to be resolved by that time. We expect to finalize all grades within 48 hours of the end of the final exam, so this deadline should be considered strict.

Online discussion using Piazza

## New Information

05/09/20
• I updated the aggregate to include all 13 labs, the two mid-terms and all seven homeworks. The formula I used was the following:
``` aggr := (mid1 + mid2)/10 + (lab01 + ... + lab13)*7/26 +
hw1*6/57 + hw2*8/83 + hw3*5/43 + hw4*5/54.5 + hw5*8/39 +
hw6*6/20 + hw7*7/59
```
The maximum value for the aggregate based on this calculation is 72. Based on the results I saw, if I were forced to assign a letter grade today, the cutoff for some kind of C would be around 38, for some kind of B would be around 54 and for some kind of A would be around 62. If your aggregate based on this formula is below 38 and you aren't getting at least a 75% average on the homeworks, you will have to catch up in the final exam get a passing grade.

05/03/20

04/26/20

• A discussion of the problems in hw5 and comments on their grading have now been posted on the homeworks page.

04/22/20

• Homework 7, the last homework in the course, has been posted. It is due on May 4, the last day of classes.

04/20/20

• A new handout on eager and lazy evaluation has been posted on handouts page for this course.

• Lecture slides and accompanying video-recorded lectures on the topic of ordering the evaluation of expressions have been posted.

• Lab 12, the lab for April 21, will include something on the order of expression evaluation that has been discussed in the video-recorded lecture that was posted in the morning today.

• Some code related to the lectures on expression evaluation has been posted to the public repo on github. Make sure to check this out.

04/15/20

• The statistics for the second mid-term exam are the following:

• For Section 01: the mean is 63.48, the standard deviation is 20.43, and the highest score is 98.

• For Section 10: the mean is 70.61, the standard deviation is 17.58, and the highest score is 99.50.

Useful information from the past

• Papers related to reasoning about programs and to architectural concerns for map-reduce computations have been posted on the papers page for this course.

• The email aliases for communication of personal matters are now up and running. Use csci2041s20-sec01 atsign umn dot edu if you are in the section that has lectures on MWF starting at 13:25 and csci2041s20-sec10 atsign umn dot edu if you are in the section that has lectures on MWF starting at 15:35.

• Information about the names of CSE Labs machines can be found here.

• 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 use Piazza through the link provided above as a medium for conducting class discussions. Please read the comments on etiquette for interactions that I have posted here and get ready to participate in discussions via Piazza 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.

## Teaching Personnel

• Instructor: Gopalan Nadathur (ngopalan atsign umn.edu), KH Keller Hall, Room 6-215, 612-626-1354.

• Graduate Teaching Assistants: Travis Carlson (carl4980 atsign umn.edu), Sanfer D'souza (dsouz039 atsign umn.edu), Henry Hoang (hoang159 atsign umn dot edu), Yifan Hu (huxxx988 atsign umn dot edu), and Eduardo Yap (yap00014 atsign umn dot edu).

• Undergraduate Teaching Assistants: Klarisse Andre de St Amat, Amith Bhat, Yashveer Bika, Austin Casey, Quynh Do, Henry Downey, Agnes Folga, Kalen Iommazzo, Terrance Gray, Neil Patel, Ashmita Sarma, and Owen Young.

## Relevant Locations

• Lecture Locations

• Location for Lab Sessions: All take place on Tuesdays in KH Keller Hall, Room 1-250.
Check the times for your specific section and make sure to attend only that lab session.

• Locations for office hours vary and are indicated in the table of office hours.

## 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 are 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 relatively 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 forefront 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 Piazza 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 Piazza 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.

## Grade Determination

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% 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 3%. 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, towards ensuring accuracy, make sure to track the scores on different components of the required work that we will post regularly to your github repository for the course.. 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.

## Academic Honesty

At the outset, you are strongly encouraged to discuss material in the course with others in the class. Using the Piazza discussion forums 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 assistants 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: May 9, 2020. Page maintained by ngopalan atsign 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.