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
Table of Contents
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.
- 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.
- 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.
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.
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.
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.
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.
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.
Different components of the required work will contribute as follows
to the final grade.
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.
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 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 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.
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.