| July 2023 | ||||||
|---|---|---|---|---|---|---|
| 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 | 31 | |||||
|
CS 15-122: Principles of Imperative Computation
(Summer 2023) |
|
|
|
CS 15-122: Principles of Imperative Computation
(Summer 2023) |
|
| Lectures: | MTWRF, | 9:30-10:50am EDT | (TEP 1403) |
|---|---|---|---|
| Practice sessions: | MTWRF, | 12:30-1:50pm EDT | (GHC CLSTR) |
| or | MTWRF, | 2:00-3:20pm EDT | (GHC CLSTR) |
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 | 3 Jul | 4 Jul | 5 Jul | 6 Jul | 7 Jul | 8 Jul | 10 Jul | 12 Jul | 15 Jul | Tue 18 Jul | 15 Jul | 17 Jul | 19 Jul | 21 Jul |
| Due | Wed 5 Jul | Thu 6 Jul | Fri 7 Jul | Sat 8 Jul | Mon 10 Jul | Wed 12 Jul | Fri 14 Jul | Sat 15 Jul | Mon 17 Jul | Wed 19 Jul | Fri 21 Jul | Sat 22 Jul | Mon 24 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 | 22 Jul | 24 Jul | 26 Jul | 28 Jul | Tue 1 Aug | 29 Jul | 31 Jul | 2 Aug | 4 Aug | 5 Aug | 7 Aug | 5 Aug | Fri 11 Aug (12a-3p) |
| Due | Wed 26 Jul | Fri 28 Jul | Sat 29 Jul | Mon 31 Jul | Wed 2 Aug | Fri 4 Aug | Sat 5 Aug | Mon 7 Aug | Tue 8 Aug | Thu 10 Aug | Fri 11 Aug |
Office hour rules:
| 2022 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Fall | F22 | F21 | F20 | F19 | F18 | F17 | F16 | F15 | F14 | F13 | F12 | F11 | F10 | |
| Summer | N23 | M22 | N21 | N20 | N19 | N18 | N17 | N16 | M15 | M14 | M13 | M12 | S11 | |
| Spring | S23 | S22 | S21 | S20 | S19 | S18 | S17 | S16 | S15 | S14 | S13 | S12 | S11 |
| 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 Ed 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 or something else’s work or a collaboration between yourself and other(s).
You are allowed to clarify the writeup of homework assignments with other students, but not work on a solution or brainstorm answers with them.
You are welcome to freely discuss course material (lecture notes/slides, practice exams, lab handouts, recitation handouts, blank writtens and programming writeups) as well as to review graded assignments with students taking the course in the current semester. You may give or receive help with computer systems, compilers, debuggers, profilers, or other facilities (as long as answers and/or code are never visible).
You are not allowed to refer to solutions and/or code written by past or present students, or found on the web, not even to "double-check" your own solution. You may not post code from this course publicly (e.g., to Bitbucket or GitHub).
You are not allowed to use any materials from previous iterations of the course, including your own. You may not discuss or receive any help on homework assignments with students who have previously taken the course (excluding current TAs).
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 run MOSS on all submissions from that edition as well. All solutions from the Web are also in MOSS — you should assume that if you were able to find it, we have already found it.
If you are uncertain whether your actions will violate this policy, please reach out to a member of course staff to ask beforehand.
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 obtaining 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 or by negligence 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, make a post on Ed or go to office hours. 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 instructors reserve 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.
For this class, we are conducting research on student outcomes. This research will involve your work in this course. You will not be asked to do anything above and 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 do not wish to participate or if you are under 18 years of age, please send an email to Chad Hershock (hershock@cmu.edu) with your name and course number. Participants will not receive any compensation. The data collected as part of this research may 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. The Eberly Center for Teaching Excellence & Educational Innovation is located on the CMU-Pittsburgh Campus and its mission is to support the professional development of all CMU instructors regarding teaching and learning. 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. If you have questions pertaining to your rights as a research participant, or to report concerns to this study, please contact Chad Hershock (hershock@cmu.edu).
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:
We ask that students do not seek help from upperclassmates who have successfully completed the course. Doing so often leads to violations of the academic integrity policy of the course. In particular, upper-classmates found to violate this policy will be reported and will incur a grade penalty.
 Asa Frank  |  Cooper Pierce |
 Oliver Moss GHC 6006 |
 Alex Blass |  Rishabh Cowlagi |
 Liz Chu |  Jessie Fan |
 Arthur Jakobsson |  James Kim |
 Delaynie McMillan |  Arnav Sabharwal |
 Abby Shrack |  Justin Sun |
 Tom Tang |  Gongwei (David) Wang |
 Ruiqi Wang |  Yu-Ching Wu |
 Zhaowei Zhang |  Rocky Zhou |
 Mon 3 Jul 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:
|
| Mon 3 Jul Practice 1 |
Setup
This session practices using Linux and running the C0 interpreter and compiler.
|
| Tue 4 Jul |
No class (Independence Day)
|
| Wed 5 Jul 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:
|
| Wed 5 Jul Practice 2 |
C0 Basics
This session reviews elementary C0 constructs and practices
reasoning about code.
|
| Thu 6 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.
|
| Thu 6 Jul Practice 3 |
A Bit about Bytes
This session practices base conversion and writing code
that manipulates bits.
|
| Fri 7 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.
|
| Fri 7 Jul Practice 4 |
TA Training
This session practices testing code.
|
| Mon 10 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 10 Jul Practice 5 |
Function Family Reunion
This session practices understanding and using big-O notation.
|
| Tue 11 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 11 Jul Practice 6 |
Fibonacci has Bad Internet
This session practices working with algorithms with radically different
complexity for the same problem.
|
| Wed 12 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 12 Jul Practice 7 |
A Strange Sort of Proof
This session reviews proving the correctness of functions.
|
| Thu 13 Jul Lecture 7 |
Libraries
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 13 Jul Practice 8 |
Misclaculation
This session practices understanding postfix notation and stack-based machines.
|
| Fri 14 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 14 Jul Practice 9 |
A queue_t Interface
This session practices programming against an interface.
|
| Mon 17 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 17 Jul Practice 10 |
List(en) Up!
This session practices working with linked lists.
|
| Tue 18 Jul Midterm 1 |
Midterm 1
|
| Wed 19 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 arbitrary 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 on average.
Showing that this is the case requires a technique called amortized
analysis, which we explore at length in this lecture.
|
| Wed 19 Jul Practice 11 |
Link it All Together
This session practices working with linked lists.
|
| Thu 20 Jul Lecture 11 |
Hashing
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 a hash
table, 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 a few simple parameters of the
hash table.
|
| Thu 20 Jul Practice 12 |
Hash This!
This session practices understanding collisions in hash functions.
|
| Fri 21 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 21 Jul Practice 13 |
Array Disarray
This session practices coding to achieve amortized cost.
|
| Mon 24 Jul Lecture 13 |
Generic Data Structures
In large (and not-so-large) systems, it is common to make multiple
uses of the same library, each instantiated with different
parameters. This is not possible in C0, however. To achieve this
goal, we look at a richer language, called C1. C1 provides two new
features: generic pointers and function pointers. Generic
pointers, void * in C, allow a same library type to be
instantiated with different client types at once, which gives us a
way to use a hash table library with both integers and strings as
keys for example. Function pointers allow a library to be
instantiated with different client-supplied operations in the same
program.
|
| Mon 24 Jul Practice 14 |
Legacy of the void*
This session practices defining generic libraries.
|
| Tue 25 Jul Lecture 14 |
Binary Search Trees
We discuss trees as an approach to representing a collection, and
binary search trees as an effective data structure to store and
operate on sorted data. In particular, most operations on balanced
binary search trees have a logarithm cost on the number of contained
data. Binary search trees can however become unbalanced over time.
|
| Tue 25 Jul Practice 15 |
This One's a Treet
This session practices using dictionaries to avoid recomputing values.
|
| Wed 26 Jul Lecture 15 |
AVL trees
Self-balancing trees guarantee the performance advantages of binary
search trees by making sure that common operations keep the tree
roughly balanced. This assurance comes at the price of more complex
code for these operations, which rely on more complex invariants to
tame it.
|
| Wed 26 Jul Practice 16 |
Rotating Rotations
This session practices restoring height invariants in trees.
|
| Thu 27 Jul Lecture 16 |
Priority Queues
We discuss priority queues, another classical data structure. Among
the possible ways to implement priority queues, we consider
min-heaps, a tree-based strategy that provides superior
performance. We examine the data structure invariants of min-heaps
and observe that we need to violate them during operations such as
insertion. To conclude with, we see that min-heaps are amenable to
an efficient implementation based on arrays.
|
| Thu 27 Jul Practice 17 |
Mind your P's and Q's
This session practices using priority queues.
|
| Fri 28 Jul Lecture 17 |
Restoring Invariants
In this lecture, we write a library that implements min-heaps using
arrays. Of particular interest is how the temporary violation of
invariants needed to implement min-heap operations manifests at the
level of contracts. Careful pre- and post-conditions are key to
writing their code correctly.
|
| Fri 28 Jul Practice 18 |
Heaps of Fun
This session practices using priority queues.
|
| Mon 31 Jul Lecture 18 |
Introduction to 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 31 Jul Practice 19 |
From C1 to Shining C
This session practices the main novelties of C.
|
| Tue 1 Aug Midterm 2 |
Midterm 2
|
| Wed 2 Aug 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 2 Aug Practice 20 |
Once you C1 you C them all
This session practices using translating C0 code to C and managing
memory leaks.
|
| Thu 3 Aug 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 3 Aug Practice 21 |
C-ing is Believing
This session practices advanced C constructions.
|
| Fri 4 Aug 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 4 Aug Practice 22 |
All sorts of sorts
This session practices working with pointers in C.
|
| 2023 Iliano Cervesato |
