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.
This course teaches imperative programming in a C-like language and
methods for ensuring the correctness of imperative programs. It is
intended for students who are familiar with elementary programming
concepts such as variables, expressions, loops, arrays, and
functions. Given these building blocks, students will learn the
process and techniques needed to go from high-level descriptions of
algorithms to correct imperative implementations, with specific
applications to basic data structures and algorithms. Much of the
course will be conducted in a subset of C amenable to verification,
with a transition to full C near the end.
This will be accomplished along three dimensions:
The main skill you will get out of this course is the ability to
write code that is correct by design and accounts for the needs of
its application context. You will learn about deliberate
programming as a way to write high quality code, about assessing the
performance of a program, and about comparing solutions to satisfy
As you do so, you will gain exposure to fundamental concepts in
Computer Science — as opposed to programming — such as
abstraction, correctness, complexity, and modularity. This will
also give you a vocabulary to communicate effectively and precisely
with other computer scientists.
Our vehicle for achieving these objectives will initially be C0, a
safe variant of C, and later C itself. Using them, you will gain
exposure to a number of data structures and algorithms that are used
pervasively in computer science. C is the language of choice for
system-level applications, and both are representative of the popular
imperative programming paradigm.
After completing 15-122, you will be able to
(Introduction to Computer
(Parallel and Sequential Data Structures and Algorithms
(Principles of Software System Construction
prerequisites or restrictions may apply.
You must have gotten a 5 on
Computer Science A exam
(Fundamentals of Programming
) or equivalent. You may also
get permission from an advisor if you performed very high on the CS
Assessment on Canvas.
It is strongly
advised that you either have taken or take at
the same time
(Concepts of Mathematics
(Mathematical Foundations of Computer Science
students who did not do so ended up learning less, spending
considerably more time on the course and earning one letter grade
lower than their peers who did, on average.
How to do Well in this Course
Our goals are for you to succeed in this course and to teach you
skills and concepts that will contribute to your success in life. To
this end, we are providing you with lots of resources and the
knowledge that comes from years of experience. Talking to some of the
thousands of students who took this course before you, here's some
advice that they found particularly useful:
Do not stress over grades: your goal is to learn new and
exciting things. Good grades follow naturally from deep learning
(but not necessarily vice versa). ...and employers care about what
you know not what grade you got.
Participate: you will get a lot more from this class if you
ask questions and engage with the course staff than if you are a fly
on the wall — and it will be more fun.
Manage your time wisely: allocate sufficient time for
homework and learning. Little adjustments can save you a whole lot
of time later and have a huge impact on your performance. In
particular, use class time to learn, review the material presented
in lecture the same day, and schedule time for homework
Start homework early: racing against a deadline is so
stressful! Starting early will remove that stress, lead to deeper
learning and give you time to improve your solution if you feel like
Get all the help you need: we provide plenty of resources
to help you succeed in this course
— office hours every
day, online help 24-7,
and friendly staff when you need them.
Take advantage of them: they are there for you! The only thing we
ask is that you plan a bit ahead: helping students takes time and
there are not enough of us if everybody waits up to the deadline.
Make time for fun: take a break from studying at least once
a day — meet with friends, go for a walk, play sports,
whatever gets you to reset your mind.
It is our goal to make this course successful, stimulating and
enjoyable. If at any time you feel that the course is not meeting
your expectations or you want to provide feedback on how the course is
progressing for you, please contact
. If we are not aware about a problem, we won't know to
fix it. If you would like to provide anonymous comments, please
use the feedback form on the course home page
There is no textbook for this course. Lecture notes and other
resources are provided through
tab of this page and
. We do not require
students to read lecture notes before lecture, but those who are
interested in reading ahead can certainly do so.
The C0 Language
For most of the course, we
, a safe subset of C
augmented with contracts. This language has been specifically
designed to support the learning objectives in this
. It provides garbage collection (freeing students from
dealing with low-level details of explicit memory management), fixed
range modular integer arithmetic (avoiding complexities of floating
point arithmetic and multiple data sizes), an unambiguous language
definition (guarding against undefined behavior), and contracts
(making code expectations explicit and localizing reasoning).
The C Language
Towards the end, the course transitions to C in preparation for
subsequent systems courses. Emphasis is on transferring positive
habits developed with the use of C0, and on practical advice for
avoiding the pitfalls and understanding the idiosyncrasies of C. We
use the valgrind
test proper memory management.
You are welcome to use any programming environment that suits you to
write your programming assignments. However, all programming homework
will be graded by running them on a Unix system
— you may want to
make sure they work
. Popular environment choices
, but you should
use what works for you: an environment that allows you to write code
quickly and efficiently. Here are some useful links:
This is a 10 unit
Tasks and Percentages
- 25 homework assignments: 45%
To encourage good work and integrity, the instructors may invite students to their offices to explain their solutions. Should this happen, the students' explanations will become part of their grades for that homework.
- 12 weekly written assignments: 15% (due
on Gradescope at 3pm EDT Monday
and Fridays, see calendar for exceptions)
- 12 weekly programming assignments: 30% (due
on Autolab at 9pm EDT Wednesday and
Saturday, see calendar for exceptions)
- Assignments are individual unless explicitly instructed.
- 2 midterm exams: 12.5% each, in class on and
- Final exam: 25%, 3 hours on
- Practice sessions and in-class exercises: 5%
Each practice session is graded on a 0-2.5 point scale, assigned as follows:
Each in-class exercise you complete will give you 0.5 points.
- 2.5 points for completing bonus exercises
- 2 points for completing standard exercises
- 1 point for attending and working on exercises, but not making it to the 2-point cutoff
- 0 points for not attending or not working on exercises
All you need to earn the 5% grade for this portion of the course
is to accumulate 50 points
overall. There are many more points than that for grabs, so no
sweat if you miss a practice session or two. Do the math: the course has
- 25 graded practice sessions
- Daily in-class participation exercises (with a few exceptions)
We are aiming to have homework and exams graded within two days of submission.
Accessing and Monitoring your Grades
Posted grades are accessible by clicking on the Grades
tab of this page. After authenticating, you will be able to see your
current grades and a projection of where you are headed given your
past performance in the class. Use this application to take action if
the trajectory does not lead to the grade you are hoping for.
Your assignments and exams are evaluated on the basis of:
Correctness: Your arguments should make sense, your proofs
should be valid, and your program should work in the reference
Elegance: Written material should be of the same quality as
what a professional would write. No typos, no bad grammar, clarity
is paramount. You are also expected to write code with good
programming style. See these notes
about what constitutes good style.
For a small subset of assignments, the course staff will review all
final submissions by hand. If there are significant style issues,
they may give a non-passing grade on style, accompanied by a “FIX
STYLE” annotations in their notes. Students who are told to fix
their style must address these issues and discuss their revisions
with a TA within 3 days of the homework grades being
posted. Any TA or instructor can do style re-grading at
any office hour; you do not have to go
to the TA that assigned the grade.
This is a fast-paced course. The late policy has the purpose to help
students from falling behind.
Aside from this, there will be no extensions on assignments in
general. If you think you really really
need an extension on
a particular assignment, contact the
as soon as possible and before the deadline.
Please be aware that extensions are entirely discretionary and will be
granted only in exceptional circumstances outside of your control
(e.g., due to severe illness or major personal/family emergencies, but
not for competitions, club-related events or interviews). The
instructors will require confirmation from University Health Services
or your academic advisor, as appropriate.
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:
I have so many deadlines this week: you know your deadlines
ahead of time — plan accordingly.
It's a minute before the deadline and the network is down:
you always have multiple submissions — it's foolish to wait
for the deadline for your first submission.
My computer crashed and I lost everything: Use Dropbox or
similar to do real-time backup — recover your files onto AFS
and finish your homework from a cluster machine.
My fraternity/sorority/club has that big event that is taking
all my time: Schedule your extra-curricular activities around
your classes, not vice versa.
We make mistakes too!
After each exam and homework assignment is graded, you will be able to
access your score by clicking on the
tab of this
page. We will make the utmost effort to be fair and consistent in our
grading. If you notice any grading mistakes, proceed as follows:
Blatant grading mistakes (e.g., the rubric says X, and you wrote X
exactly) can be corrected by any TA
in office hours.
For any other grading issues, you must request a regrade:
Write an email to explaining
where and why you think there was a mistake in grading. Make sure
to specify which homework or exam this appeal is for. Write at
most 3 lines for each response you are disputing.
Verbal or handwritten requests will not be accepted. Please do
not make regrade requests on
All regrade requests must be received within 3 days of the work
being handed back on Gradescope
or Autolab, which we will announce in
This class is not curved. However, to ensure consistency across
semesters, we set our grading standards in such a way as to compensate
for the relative difficulty of exams.
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:
- A: above 90%
- B: 80-90%
- C: 70-80%
- D: 60-70%
This assumes that the makeup of a student’s grade is not wildly
anomalous: exceptionally low overall scores on exams, programming
assignments, or written assignments will be treated on a case-by-case
basis. In particular, students who are unable to demonstrate a basic
proficiency with the C language in the last few programming
assignments will receive a D in the class (this is because 15-122 is a
prerequisite to 15-213, a very C-intensive course).
For reference, almost a quarter of the students who received a B in
Fall 2014 had a 90-100% average on programming assignments, an 80-90%
average on written homeworks, and a 70-80% average on exams.
Precise grade cutoffs will not be discussed at any point during or
after the semester. For students very close to grade boundaries,
instructors may, at their discretion, consider participation in
lecture and practice sessions, exam performance and overall grade
trends when assigning the final grade.
You are expected to comply with the University Policy on Academic Integrity
(see also The Word
and Understanding Academic Integrity
The university policies and procedures on academic integrity will be
applied rigorously. All students are required to fill out
as part of their first assignment
indicating that they understand and accept this policy.
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
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
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.
Penalties and Specifics
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 . 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
What is Allowed
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
If you took this course in full or in part in a past semester, we ask
that you delete your previous work so you won't look at it. In
particular, copying one's own solutions from an earlier semester is a
violation of the academic integrity policy and will be handled as
such. Doing so may save time close to a deadline but it will not have
the effect of learning the material, which will be a serious handicap
Class presence and participation
Active participation by you and other students will ensure that
everyone has the best learning experience in this class. We may take
participation in lecture and practice sessions into account when
setting final grades.
Students with disabilities
If you wish to request an accommodation due to a documented
disability, please inform your instructor and
as soon as possible
(). Once your accommodation has been approved, you
will be able to request extra-time for each exam separately
by filling this
a week in advance.
Research to Improve the Course
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
() or us if you
have questions or concerns about your participation.
Take care of yourself.
Do your best to maintain a healthy lifestyle this semester by eating
well, exercising, avoiding drugs and
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:
- CaPS: 412-268-2922
- Re:solve Crisis Network: 888-796-8226
- If the situation is life threatening, call the police:
- On campus (CMU Police): 412-268-2323
- Off campus: 911
If you have questions about this or your coursework, please let us know
For assistance with the written or oral communication assignments in
this class, visit the Global Communication Center (GCC). GCC tutors
can provide instruction on a range of communication topics and can
help you improve your papers and presentations. The GCC is a free
service, open to all students, and located in Hunt library. You can
make tutoring appointments directly on the GCC
You may also visit the GCC website to find out about communication
workshops offered throughout the academic year.
External Academic Support
The Office of Academic
is providing various services aimed at helping
students master the contents of this course. These optional
services are free and voluntary. They are led by trained
leaders who have successfully completed the course. Leaders are not
members of the course staff. These services are are designed to supplement
— not replace — class lectures and practice sessions. They do
not cover homework.
- Supplemental Instruction (SI)
- is a weekly session in which the leader prepares review material
based on the current course content, but adapts the focus of the
session based on the attendees' questions and requests.
- EXCEL groups
- are formalized, small group study sessions that meet once a
week. They consist of approximately nine students and are
interactive and geared specifically to the group members. Therefore,
only pre-registered students will be allowed to attend. If a group
is full, you will be wait-listed until a spot becomes available or
another group is formed. In order to establish and maintain a
cohesive group, each EXCEL group member must consistently attend and
actively participate in the sessions of his or her assigned
- Peer Tutoring
- Students can drop in between 8:30pm and 11:00pm Sundays through
Thursdays at select residence halls and other campus locations. No
appointment is necessary, just walk-in.
We ask that students do not seek help from upperclassmates
have successfully completed the course. Doing so often leads to
violations of the academic integrity policy of the
. In particular, upper-classmates found to violate this
policy will be reported and will incur a grade penalty.
Students who complete this course should be able to explain
abstraction and other key computer science concepts, apply these
fundamental concepts as problem-solving tools, and wield contracts as
a tool for reasoning about the safety and correctness of programs. In
particular, we expect students to be able to:
- develop contracts (preconditions, postconditions, assertions, and loop invariants) that establish the safety and correctness of imperative programs.
- develop and evaluate proofs of the safety and correctness of code with contracts.
- develop and evaluate informal termination arguments for programs with loops and recursion.
- evaluate claims of both asymptotic complexity and practical efficiency of programs by running tests on different problem sizes.
- define the concept of programs as data, and write programs that use the concept.
- defend the use of abstractions and interfaces in the presentation of algorithms and data structures.
- identify the difference between specification and implementation.
- compare different implementations of a given specification and different specifications that can be applied to a single implementation.
- explain data structure manipulations using data structure invariants.
- identify and evaluate the use of fundamental concepts in computer science as problem-solving tools:
- order (sorted or indexed data),
- asymptotic worst case, average case, and amortized analysis,
- randomness and (pseudo-)random number generation, and
- divide-and-conquer strategies.
Students who complete this course should be able to read and write
code for imperative algorithms and data structures. In particular, we
expect students to be able to:
- trace the operational behavior of small imperative programs.
- identify, describe, and effectively use basic features of C0 and C:
- integers as signed modular arithmetic,
- integers as fixed-length bit vectors,
- characters and strings,
- Boolean operations with short-circuiting evaluation,
- loops (while and for),
- recursive and mutually recursive functions,
- void pointers and casts between pointer types,
- generic data structures using void and function pointers,
- contracts (in C0), and
- casts between different numeric types (in C).
- translate between high-level algorithms and correct imperative code.
- translate between high-level loop invariants and data structure invariants and correct contracts.
- write code using external libraries when given a library interface.
- develop, test, rewrite, and refine code that meets a given specification or interface.
- develop and refine small interfaces.
- document code with comments and contracts.
- identify undefined and implementation-defined behaviors in C.
- write, compile, and test C programs in a Unix-based environment
using make, gcc, and valgrind.
Algorithms and Data Structures
Students who complete this course should be able to describe the
implementation of a number of basic algorithms and data structures,
effectively employ those algorithms and data structures, and explain
and interpret worst-case asymptotic complexity arguments. In
particular, we expect students to be able to:
- determine the big-O complexity of common code patterns.
- compare common complexity classes like O(1), O(log n), O(n), O(n log n), O(n2), and O(2n).
- explain the structure of basic amortized analysis proofs that use potential functions.
- apply principles of asymptotic analysis and amortized analysis to new algorithms and data structures.
- recognize properties of simple self-adjusting data structures.
- recognize algorithms and data structures using divide-and-conquer.
- describe and employ a number of basic algorithms and data structures:
- integer algorithms,
- linear search,
- binary search,
- sub-quadratic complexity sorting (mergesort and quicksort),
- stacks and queues,
- pseudo-random number generators,
- hash tables,
- priority queues,
- balanced binary search trees,
- disjoint-set data structures (union/find), and
- simple graph algorithms.