| June 2020 | ||||||
|---|---|---|---|---|---|---|
| U | M | T | W | R | F | S |
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | ||||
|
CS 15-122: Principles of Imperative Computation
(Summer 2020) |
|
|
|
CS 15-122: Principles of Imperative Computation
(Summer 2020) |
|
| Lectures: | MTWRF, | 10:30-11:50am EDT | (Zoom) |
|---|---|---|---|
| Practice sessions: | MTWRF, | 3:00-4:20pm EDT | (Zoom) |
Click on a class day to go to that particular lecture or recitation. Due dates for homeworks are set in bold. The due date of the next homework blinks.
| Test Percentage learn. obj | Wr1 1.3% 1-3,11 | Pg1 2.5% 1,12 | Wr2 1.3% 1-3 | Pg2 2.5% 12,15,16 | Wr3 1.3% 1,2,4,12 | Pg3 2.5% 1,12-16 | Wr4 1.3% 1-4,21,27 | Pg4 2.5% 1,18,17 | Wr5 1.1% 6-10,15-17 | Midterm1 12.5% 1-8 | Pg5 2.5% 5,12,27 | Wr6 1.3% 6-8,12,17 | Pg6 1.6% 10 | Wr7 1.3% 9,17,24,27 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Posted | 29 Jun | 29 Jun | 1 Jul | 2 Jul | 3 Jul | 4 Jul | 6 Jul | 8 Jul | 10 Jul | Tue 14 Jul | 11 Jul | 13 Jul | 15 Jul | 17 Jul |
| Due | Wed 1 Jul | Thu 2 Jul | Fri 3 Jul | Sat 4 Jul | Mon 6 Jul | Wed 8 Jul | Fri 10 Jul | Sat 11 Jul | Mon 13 Jul | Wed 15 Jul | Fri 17 Jul | Sat 18 Jul | Mon 20 Jul |
| Test Percentage learn. obj | Pg7 3.4% 1,12-18 | Wr8 1.3% 12,24,27 | Pg8 2.5% 8,10-18 | Wr9 1.1% 9,10,25-27 | Midterm2 12.5% 1-8 | Pg9 2.5% 9,12-18 | Wr10 1.3% 2,13,25,27 | Pg10 2.5% 10,15-20 | Wr11 1.3% 18-20 | Pg11 2.5% 5,15-20 | Wr12 1.1% 18-20 | Pg12 2.5% 5,15-20 | Final 25% 1-27 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Posted | 15 Jul | 20 Jul | 22 Jul | 24 Jul | Tue 28 Jul | 25 Jul | 27 Jul | 29 Jul | 31 Jul | 1 Aug | 3 Aug | 1 Aug | Fri 7 Aug (N/A) |
| Due | Wed 22 Jul | Fri 24 Jul | Sat 25 Jul | Mon 27 Jul | Wed 29 Jul | Fri 31 Jul | Sat 1 Aug | Mon 3 Aug | Tue 4 Aug | Thu 6 Aug | Fri 7 Aug |
| 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Fall | F'19 | F'18 | F'17 | F'16 | F'15 | F'14 | F'13 | F'12 | F'11 | F'10 | |
| Summer | N'20 | N'19 | N'18 | N'17 | N'16 | M'15 | M'14 | M'13 | M'12 | S'11 | |
| Spring | S'20 | S'19 | S'18 | S'17 | S'16 | S'15 | S'14 | S'13 | S'12 | S'11 |
| Unix | Emacs | Vim |
|---|---|---|
|
We strongly advise students not to use late days in the first half of the course. Later assignments are more challenging and many courses have lots of deliverables towards the end of the semester. The second half of the semester is where late days are most needed. Note that the constraints of the semester timing mean that no late days can be used on the last programming assignment.
Nearly all situations that make you run late on an assignment homework can be avoided with proper planning — often just starting early. Here are some examples:
All regrade requests must be received within 3 days of the work being handed back on Gradescope or Autolab, which we will announce in a Diderot post.
What follows is a rough guide to how course grades will be established, not a precise formula — we will fine-tune cutoffs and other details as we see fit after the end of the course. This is meant to help you set expectations and take action if your trajectory in the class does not take you to the grade you are hoping for (see also the Grades tab on this page). So, here's a rough, very rough heuristics about the correlation between final grades and total scores:
The value of your degree depends on the academic integrity of yourself and your peers in each of your classes. It is expected that, unless otherwise instructed, the work you submit as your own is your own work and not someone else’s work or a collaboration between yourself and other(s).
Homework assignments, both written and programming, are strictly individual. You may not brainstorm on approaches, develop code or solutions, or check your work with anybody other than the course staff or other explicitly approved parties. In particular, discussing due homework with current and former students in person or electronically is prohibited.
We will be using the MOSS system to detect software plagiarism. Whenever a programming assignment is similar to a homework from a previous course edition, we will running MOSS on all submissions of that edition as well.
Please read the University Policy on Academic Integrity carefully to understand the penalties associated with academic dishonesty at Carnegie Mellon. In this class, cheating/copying/plagiarism means copying all or part of a program or homework solution from another student or unauthorized source such as the Internet, having someone else do a homework or take an exam for you, knowingly giving such information to another student, reusing answers or solutions from previous editions of the course, or giving or receiving unauthorized information during an examination. In general, each solution you submit (written assignment, programming assignment, midterm or final exam) must be your own work. In the event that you use information written by others in your solution, you must cite the source of this information (and receive prior permission if unsure whether this is permitted). It is considered cheating to compare complete or partial answers, copy or adapt others' solutions, or sit near another person who is taking (or has taken) the same course and complete the assignment together. Working on code together, showing code to another student and looking at another student's code are considered cheating. If you need help debugging, go to office hours or make a post on Diderot. It is also considered cheating for a repeating student to reuse one's solutions from a previous semester, or any instructor-provided sample solution. It is a violation of this policy to hand in work for other students.
Your course instructor reserves the right to determine an appropriate penalty based on the violation of academic dishonesty that occurs. Penalties are severe: a typical violation of the university policy results in the student failing this course, but may go all the way to expulsion from Carnegie Mellon University. If you have any questions about this policy and any work you are doing in the course, please feel free to contact the instructors for help.
It is not considered cheating to give help or receive help in using the computer systems, compilers, debuggers, profilers, or other facilities, but you must refrain from looking at other students' code while you are getting or receiving help for these tools. It is not cheating to review graded assignments or exams with students in the same class as you, but it is considered unauthorized assistance to share these materials between different iterations of the course. Do not post code from this course publicly (e.g., to Bitbucket or GitHub).
For this course, we are conducting research on student learning. This research will involve your coursework. You will not be asked to do anything above or beyond the normal learning activities and assignments that are part of this course. You are free not to participate in this research, and your participation will have no influence on your grade for this course or your academic career at CMU. If you choose not to participate in the research, you must still complete all required coursework, but your data will not be included in the research analyses. Participants will not receive any compensation. The data collected as part of this research will include student grades. All analyses of data from participants' coursework will be conducted after the course is over and final grades are submitted. The Eberly Center may provide support on this research project regarding data analysis and interpretation. To minimize the risk of breach of confidentiality, the Eberly Center will never have access to data from this course containing your personal identifiers. All data will be analyzed in de-identified form and presented in the aggregate, without any personal identifiers. Please contact Dr. Chad Hershock (hershock@cmu.edu) or us if you have questions or concerns about your participation.
Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.
All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often helpful.
If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit their website. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.
If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night:
 Marcie Baker  GHC 6006 |
 Nikita Basu Office hours:
|  Ben Cagan Office hours:
| |||||||
 Elizabeth Carney Office hours:
|  Olivia Corrodi Office hours:
| |||||||
 Samuel Delatore Office hours:
|  Eric Gan Office hours:
| |||||||
 Mansi Gandhi Office hours:
|  Ben Kwabi-Addo Office hours:
| |||||||
 Brian Lee Office hours:
|  Mei Leng Office hours:
| |||||||
 Alex Lin Office hours:
|  Cooper Pierce Office hours:
| |||||||
 Triss Ren Office hours:
|  Leah Restad Office hours:
| |||||||
 Evan Tipping Office hours:
|  Kavya Tummalapalli Office hours:
| |||||||
 Sophie Wang Office hours:
|  Brent Xiao Office hours:
| |||||||
 Hesper Yin Office hours:
|  Rachel Yuan Office hours:
| |||||||
 Brian Zhang Office hours:
| ||||||||
 Lora Zhou Office hours:
|
 Mon 29 Jun Lecture 0 |
Welcome and Course Introduction
We outline the course, its goals, and talk about various administrative
issues.
Readings:
A mysterious function ...
We examine a program we know nothing about, making hypotheses about
what it is supposed to do. We notice that this function has no
meaningful output for some inputs, which leads us to restricting its
valid inputs using preconditions. We use a similar mechanism,
postconditions, to describe the value it returns. Along the way, we
get acquainted to C0 and its support for checking pre- and
post-conditions. We then notice that this function doesn't return
the expected outputs even for some valid inputs ...
Concepts:
Readings:
|
| Mon 29 Jun Practice 1 |
Setup
This lab practices using Linux and running the C0 interpreter and compiler.
|
| Tue 30 Jun Lecture 1 |
Contracts
Contracts are program annotations that spell out what the code is
supposed to do. They are the key to connecting algorithmic ideas to
their implementation as a program. In this lecture, we illustrate
the use of contracts by means of a simple C0 program. As we do so,
we learn to verify loop invariants — an important type of
contract, we see how contracts can help us write correct code, and
we get acquainted with C0's automated support to validating contracts.
Concepts:
|
| Tue 30 Jun Practice 2 |
C0 Basics
This recitation reviews elementary C0 constructs and practices
reasoning about code.
|
| Wed 1 Jul Lecture 2 |
Arrays
In this lecture, we examine arrays as our first composite data
structure, i.e., a data construction designed to hold multiple
values, together with operations to access them. Accessing an array
element outside of its range is undefined — it is a safety
violation — and we see how to use contracts, in particular
loop invariants, to ensure the safety of array accesses in a
program. Arrays are stored in memory, which means that they are
manipulated through an address. This raises the possibility of
aliasing, a notorious source of bugs in carelessly written programs.
|
| Wed 1 Jul Practice 3 |
A Bit about Bytes
This recitation practices base conversion and writing code
that manipulates bits.
|
| Thu 2 Jul Lecture 3 |
Searching Arrays
We practice reasoning about arrays by implementing a function that
searches whether an array contains a given value — this is the
gateway to a whole class of useful operations. We notice that this
function returns its result more quickly when the array is sorted.
We write a specialized variant that assumes that the array is
sorted, and show that it works correctly by reasoning about array
bounds. The first (simpler but less efficient) version acts as a
specification for the the second (slightly more complex but often
faster). Using the specification in the contract for the
implementation is a standard technique to help writing correct code.
|
| Thu 2 Jul Practice 4 |
TA Training
This lab practices testing code.
|
| Fri 3 Jul |
No class (Independence Day)
|
| Mon 6 Jul Lecture 4 |
Big-O
We examine big-O notation as a mathematical tool to describe the
running time of algorithms, especially for the purpose of comparing
two algorithms that solve the same problem. As a case study, we use
the problem of sorting an array, and for now a single sorting
algorithm, selection sort. As we implement selection sort, we see
that starting with contracts gives us high confidence that the
resulting code will work correctly. Along the way, we develop a
useful library of functions about sorted arrays to be used in
contracts.
|
| Mon 6 Jul Practice 5 |
Function Family Reunion
This recitation practices understanding and using big-O notation.
|
| Tue 7 Jul Lecture 5 |
Binary search
When searching for a value in a sorted array, examining the middle
element allows us to discard half of the array in the worst case.
The resulting algorithm, binary search, has logarithmic complexity
which is much better than linear search (which is linear).
Achieving a correct imperative implementation can be tricky however,
and we use once more contracts as a mechanism to reach this goal.
|
| Tue 7 Jul Practice 6 |
A Strange Sort of Proof
This recitation reviews proving the correctness of functions.
|
| Wed 8 Jul Lecture 6 |
Quicksort
We use the key idea underlying binary search to implement two sorting
algorithms with better complexity than selection sort. We examine
one of them, quicksort, in detail, again using contracts to achieve
a correct implementation, this time a recursive implementation. We
observe that the asymptotic complexity of quicksort depends on the
the value of a quantity the algorithm use (the pivot) and discuss
ways to reduce the chances of making a bad choice for it. We
conclude by examining another sorting algorithm, mergesort, which is
immune from this issue.
|
| Wed 8 Jul Practice 7 |
Fibonacci has Bad Internet
This lab practices working with algorithms with radically different
complexity for the same problem.
|
| Thu 9 Jul Lecture 7 |
Data structures
Arrays are homogeneous collections, where all components have the
same type. structs enable building heterogeneous
collections, that allow combining components of different types.
They are key to building pervasively used data structures. In C0,
a struct resides in allocated memory and is accessed
through an address, which brings up a new form of safety violation:
the NULL pointer violation. We extend the language of
contracts to reason about pointers.
Now that we have a two ways to build complex collections, we start exploring the idea of segregating the definition of a data structure and the operations that manipulate it into a library. Code that uses this data structure only needs to be aware of the type, operations and invariants of the data structure, not the way they are implemented. This is the basis of a form of modular programming called abstract data types, in which client code uses a data structure exclusively through an interface without being aware of the underlying implementation.
|
| Thu 9 Jul Practice 8 |
Misclaculation
This lab practices understanding postfix notation and stack-based machines.
|
| Fri 10 Jul Lecture 8 |
Stacks and Queues
In this lecture, we examine the interface of two fundamental data
structures, stacks and queues. We practice using the exported
functions to write client code that implements operations of stacks
and queues that are not provided by the interface. By relying only
of the interface functions and their contracts, we can write code
that is correct for any implementation of stacks and queues.
|
| Fri 10 Jul Practice 9 |
A queue_t Interface
This recitation practices programming against an interface.
|
| Mon 13 Jul Lecture 9 |
Linked Lists
We observe that we can implement array-like collections using
a struct that packages each element with a pointer to the
next element. This idea underlies linked lists, a data structure
pervasively used in computer science. Writing correct code about
linked lists is however tricky as we often rely on stricter
invariants than natively supported, in particular the absence of
cycles. We develop code to be used in contracts to check for common
such properties. We then use linked lists to write code that
implements the stack interface, and similarly for queues. We could
have given an array-based implementation, and we note the advantages
and drawbacks of each choice.
|
| Mon 13 Jul Practice 10 |
List(en) Up!
This lab practices working with linked lists.
|
| Tue 14 Jul Midterm 1 |
Midterm 1
|
| Wed 15 Jul Lecture 10 |
Unbounded Arrays
When implementing a data structure for a homogeneous collection,
using an array has the advantage that each element can be accessed
in constant time, but the drawback that we must fix the number of
elements a priori. Linked lists can have arbitrarily length but
access takes linear time. Can we have the best of both worlds?
Unbounded arrays rely on an array to store the data, but double it
when we run out of place for new elements. The effect is that
adding an element can be either very cheap or very expensive
depending on how full the array is. However, a series of insertions
will appear as if each one of them takes constant time in average.
Showing that this is the case requires a technique called amortized
analysis, which we explore at length in this lecture.
|
| Wed 15 Jul Practice 11 |
Link it All Together
This recitation practices working with linked lists.
|
| Thu 16 Jul Lecture 11 |
Hash Tables
Associative arrays are data structures that allow efficiently
retrieving a value on the basis of a key: arrays are the special
case where valid indices into the array are the only possible keys.
One popular way to implement associative arrays is to use hash
tables, which computes an array index out of each key and uses that
index to find the associated value. However, multiple keys can map
to the same index, something called a collision. We discuss several
approaches to dealing with collisions, focusing on one called separate
chaining. The cost of access depends on the contents of the hash
table. While a worst case analysis is useful, it is not typically
representative of normal usage. We compute the average case
complexity of an access relative to as few simple parameters of the
hash table.
|
| Thu 16 Jul Practice 12 |
Hash This!
This lab practices understanding collisions in hash functions.
|
| Fri 17 Jul Lecture 12 |
Hash Dictionaries
In this lecture, we look at the interface of modular code at greater
depth, using hash functions as a case study. In this and many
example, it is useful for the client to fill in some parameters used
by the library code so that it delivers the functionalities needed
by the client. One such parameter is the type of some quantities
the library acts upon, keys in our case. It is also often the case
that the client wants to provide some of the operations used by the
library, here how to hash a key and how to compare elements. This
is a first step towards making libraries generic, so that they
implement the general functionalities of a data structure but let
the client choose specific details.
|
| Fri 17 Jul Practice 13 |
Array Disarray
This recitation practices coding to achieve amortized cost.
|
| Mon 27 Jul Lecture 18 |
Data Structures in C
With this lecture, we are moving from the safety of C0 to the more
open-ended world of C. We introduce some basic concepts of C, in
particular the C preprocessor and how macros written in this
language can simulate some of the effects of C0's contracts. We
also see how to compile C programs and discuss separate compilation.
We conclude with C's primitives to manage memory, in particular the
need to free allocated memory to prevent memory leaks.
|
| Mon 27 Jul Practice 19 |
From C1 to Shining C
This recitation practices the main novelties of C.
|
| Tue 28 Jul Midterm 2 |
Midterm 2
|
| Wed 29 Jul Lecture 19 |
C's Memory Model
C provides a very flexible view of memory, which allows writing
potentially dangerous code unless one is fully aware of the
consequences of one's decision. This lecture is about building this
awareness. We see that, while C overlays an organization on the
monolithic block of memory the operating systems assigns to a
running program, it also provides primitives that allow violating
this organization. We focus on two such primitives, pointer
arithmetic and address-of. While some uses are legitimate, others
are not. C's approach to many non-legitimate operations is to
declare them undefined, which means that what happens when a program
engages in them is decided by the specific implementation of the C
compiler in use.
|
| Wed 29 Jul Practice 20 |
Once you C1 you C them all
This lab practices using translating C0 code to C and managing
memory leaks.
|
| Thu 30 Jul Lecture 20 |
Types in C
In this lecture, we examine how C implements basic types, and what
we as programmers need to be aware of as we use them. We begin with
strings, that in C are just arrays of characters with
the null character playing a special role. A variety of
number types are available in C, but some of their characteristics
are not defined by the language, most notably their size and what
happens in case of overflow. As a consequence, different compilers
make different choices, which complicates writing code that will
work on generic hardware.
|
| Thu 30 Jul Practice 21 |
C-ing is Believing
This recitation practices advanced C constructions.
|
| Fri 31 Jul Lecture 21 |
Virtual Machines
Getting a program written in a high-level language to run onto the
machine hardware can be achieved in a number of ways, with
compilation to machine code and interpretation of the source
language as the two extremes. We assess the benefits and drawbacks
of each and introduce virtual machines as a modern trade-off. We
explore this possibility through the C0VM, a virtual machine for C0.
A compilation phase takes C0 code as input and outputs bytecode that
can be run by the C0VM. We examine in depth the organization of the
C0VM itself, understanding how its instructions are executed through
a description called an operational semantics. We also describe
some of the data structures needed to implement the C0VM itself.
|
| Fri 31 Jul Practice 22 |
All sorts of sorts
This lab practices working with pointers in C.
|
| 2020 Iliano Cervesato |
