Description
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
deployment constraints.
-
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
take
15-213
(
Introduction to Computer
Systems),
15-210
(
Parallel and Sequential Data Structures and Algorithms), among others.
Other prerequisites or restrictions may apply.
Prerequisites
You must have passed
passed
15-112
(
Fundamentals of Programming) or equivalent.
It is
strongly advised that you either have taken or take at
the same time
either
21-127
(
Concepts of Mathematics)
or
15-151
(
Mathematical Foundations of Computer Science): historically,
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.
Past Offerings
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
proactively.
-
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
it.
-
Get all the help you need: we provide plenty of resources
to help you succeed in this course
— office hours, 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.
Feedback
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
us. 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
or slide a note under our doors.
Resources
Course Material
There is no textbook for this course. Lecture notes and other
resources are provided through
the
Schedule
and
Handouts tabs of this page, and
on
. We do not require
students to read the course material before lecture, but those who are
interested in reading ahead can certainly do so.
The C0 Language
In the first nine weeks, the course
uses
C0, a safe subset of C
augmented with contracts. This language has been specifically
designed to support the
learning objectives in this
course. It provides garbage collection (freeing students from
dealing with low-level details of explicit memory management), fixed
range modular integer arithmetic (avoiding the 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
In the last five weeks, 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 tool to
test proper memory management.
Programming Environments
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
using — you may want to make
sure they work
on Andrew
Unix. Popular environment choices
include VSCode, emacs
and vim, but you should use what
works for you: an environment that allows you to write code quickly
and efficiently. Here are some useful links:
We require that you disable AI extensions from your programming
environment and in general that you do not use AI tools. These
tools may give a quick answer but they undermine learning and
retention. (See also Academic Integrity Policy.)
Grading
This is a
12 unit course.
Tasks and Percentages
- 25 homework assignments: 36%
- 13 weekly practice problems (due
on Wednesdays at 6pm
Qatar time — strict!)
- 12 weekly programming assignments (due on Sundays at 9pm Qatar time — strict!)
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+1 check-ins: 36% (in class, closed books,
Tuesdays at 7:00pm or 7:45pm depending on section). The "joker"
check-in is optional and may be used to
replace the grade of another check-in.
- Final exam: 25%, 3 hours, closed books, on
- Precepts and activities: 3%
Each precept is worth 2.5 points
given out based on effort and rough correctness.
There will be one activity worth 0.5
points during or after each lecture. Use
the activities page to test your
configuration and do the current activity (when there is one).
The precepts and activities grade is calculated based on the bucket
system: All you need to earn the full 3% grade for this
portion of the course is to accumulate 30
points overall. There are many more points than that
for grabs, so no sweat if you miss a precept or a lecture. Do the
math: the course has
- 12 graded precepts
- 26 lectures
We are aiming to have homework and check-ins 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.
Evaluation Criteria
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
environment.
-
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 the Guide
to Success on Coding with Style 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 5 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.
Late Policy
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
instructors 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
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.
Grade Appeals
We make mistakes too!
After each homework assignment and practice activity is graded, you
will be able to access your score by clicking on the
Grades 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:
-
Go to office hours and describe the
putative grading mistake to a TA.
-
If the TA does not resolve the matter convincingly, you may request
a regrade as follows:
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.
Email requests to the course staff will not be accepted. Please do
not make regrade requests on
.
All regrade requests must be received within 5 days of the
work being handed back on
or , which we will announce in
a post.
Final Grades
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 programming
assignments, practice problems or check-ins 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).
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 precepts, exam performance and overall grade trends when
assigning the final grade.
Academic Integrity
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
a
form 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 or something else's work or a collaboration
between yourself and others.
Many students who copy code or other work do so in the heat of the
moment and regret their actions later on, when more clear-headed.
You may contact the instructors by 2pm the day after a deadline and
ask to delete your submissions for an assignment, no questions
asked. Deleted submissions are not considered when running academic
integrity checks and receive a grade of 0. You may do so at most
once during the semester.
Contact us before we contact you.
The Policy (Spring'25)
Practice Problems
Practice problems are intended to be collaborative but
submissions are individual.
Specifically, you are welcome to work on any aspects of a practice
problem with other students. However, in order to ensure that the
work you submit reflects your learning, we insist that you adhere to
a whiteboard policy regarding these discussions: you are
not allowed to take any notes, files, pictures or other records away
from the discussion, nor shall you memorize answers. For example,
you may work on practice problems at the whiteboard with another student,
but then you must erase the whiteboard, stop discussing the problem,
wait some time (15
minutes is a safe heuristic) and write up your solution individually.
We take your ability to recreate the solution independently as proof
that you understand the work that you submit.
Programming Assignments
Programming assignments are strictly individual.
You may ask other students clarifications on the writeup
(e.g., "What does this sentence mean?", "Can you explain
this notation?") but you may not discusses approaches to solving
any aspect of the assignment (e.g., "How would you do
this?", "Can you walk me through an example?").
You are not allowed to refer to solutions and/or code written by
past or present students, ChatGPT or other AI-based tools, 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).
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.
Check-ins and the Final
Check-ins and the final exam are strictly
individual.
Studying and General Help
You are welcome to freely discuss course material (lecture
notes/slides, practice exams, precept handouts), as well as to review
graded assignments or check-ins 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 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 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.
If you are uncertain whether your actions will violate this policy,
please reach out to a member of course staff to ask beforehand.
Penalties and Specifics
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 tool, or
unauthorized source such as the Internet or AI tool, 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 (practice problem, programming assignment,
check-in 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.
For programming assignments,
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 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 go from negative points in an assignmnent
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.
Repeat Students
If you took this course in full or in part in a past semester, we
ask that you delete all your previous work so you won't look
at it. In particular, copying or referencing
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 in exams and in follow-up courses.
Other Policies
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 precepts into account when setting
final grades. Fire safety rules require that we never exceed the
stated capacity of a classroom. For this reason, we require that
you attend the lecture, check-in slot, and precept you
are registered for.
Laptops and mobile devices
Research on learning
shows that unexpected noises and visual distractions can disrupt attention
and negatively impact everyone's learning experience. To maintain a focused
environment, the use of laptops, tablets, and mobile phones is not allowed
during class, unless explicitly permitted by the instructor.
Diversity
It is my hope that students from a diversity of backgrounds and perspectives be well served by this course, that students' learning needs be addressed both in and out of class, and that the diversity students bring to this class be viewed as a resource, strength and benefit. It is my intent to present materials and activities that are respectful of diversity: gender, sexuality, disability, age, socioeconomic status, ethnicity, race, nationality, religion, and culture. Your suggestions are encouraged and appreciated. Please let me know ways to improve the effectiveness of the course for you personally or for other students or student groups.
This statement is adapted from The University of Iowa Department of Education.
Accommodations for Students with Disabilities
Carnegie Mellon University is committed to providing reasonable accommodations for all persons with disabilities. To access accommodation services you are expected to initiate the request and submit a Voluntary Disclosure of Disability Form to the office of Health & Wellness or CaPS-Q. In order to receive services/accommodations, verification of a disability is required as recommended in writing by a doctor, licensed psychologist or psycho-educational specialist. The office of Health & Wellness, CaPS-Q and Office of Disability Resources in Pittsburgh will review the information you provide. All information will be considered confidential and only released to appropriate persons on a need to know basis.
Once the accommodations have been approved, you will be issued a Summary of Accommodations Memorandum documenting the disability and describing the accommodation. You are responsible for providing the Memorandum to your professors at the beginning of each semester.
For more information on policies and procedures, please visit Assistance for Individuals with Disabilities on Scotty.
For additional information, please feel free to contact any of the following:
Wellness and Happiness
We care very much about your well-being and happiness. CMU students (and
faculty) work very hard, but we must keep our balance and always attend to our
well-being and happiness first. Achieving a better grade is almost never a
matter of putting in more time! So be sure to get
enough sleepenough sleep, eat right,
exercise regularly, and attend to your well-being and happiness.
Also, please know that we do care about you and take your well-being seriously.
We want to help you learn while minimizing stress. Meeting the learning goals of
15-112 necessitates significant effort and a fast pace, but do not fall into the
trap of working endlessly, as this will only reduce your efficiency (and more
importantly, your happiness and well-being). It is not necessary, expected, or
something to be proud of. We can help you improve your efficiency and work less,
not more. We also seek to minimize the workload as much as is possible, while
still meeting the learning goals of the course.
Finally, if you are feeling overly stressed, anxious, or unhappy about your
performance or your general experience in this course: please come talk to us.
We will listen. We are here for you and we will try to help. There are also 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, can often help your situation from getting more complicated. If you
or any of your CMUQ peers are experiencing academic stress, difficult life
events, or feelings like anxiety or depression, we strongly encourage you to
seek support.
Our Student Affairs staff are here to help:
- Dr. Dalia Rehal, Associate Dean for Student Affairs (CMB 1094), drehal@qatar.cmu.edu, 4454-8545
- Amie Rollins, Office of Health and Wellness (CMB 1103), amier@andrew.cmu.edu, 4454-8680
- Dr. Atorina Benjamin, Counseling and Psychological Services (CMB 1104), atorinab@qatar.cmu.edu, 4454-8525
You can also visit the Ilona Wyers Student Lounge and connect with anyone on the Student Affairs Team. Consider also reaching out to a friend, faculty, staff, or family member you trust for help. If you would like to speak to a trained professional for mental health support, day or night, call our ProtoCall hotline at 5554 7913, which is staffed by trained mental health care providers.
If the situation is life threatening, call 999.
Learning Objectives
Computational Thinking
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.
Programming Skills
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,
- arrays,
- loops (
while and for),
- pointers,
- structs,
- 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.
