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 and methods for ensuring the correctness of programs. It is intended for students with a basic understanding of programming (variables, expressions, loops, arrays, functions). Students will learn the process and concepts 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 we do so, you will learn and build an appreciation for fundamental concepts in Computer Science, 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 it, 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 code, 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
(Parallel and Sequential Data Structures and Algorithms
) and 15-214
(Principles of Software System Construction
). Other prerequisites or restrictions may apply.
You must have gotten a 5 on the AP Computer Science A exam
or passed 15-112
(Fundamentals of Programming
) or equivalent. You may also get permission from an advisor if you performed very high on the CS Assessment on Blackboard.
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 ended up with a course grade one letter grade lower than their peers who did, in average.
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 you would like to provide anonymous comments, please use the feedback form on the course home page
or slide a note under our doors. Comments of general interest will be answered on the course discussion board
There is no textbook for this course. Lecture notes and other resources are provided through the Schedule
tab of this page. 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
In the first nine weeks, the course uses C0
, a small safe subset of C augmented with a layer to express contracts. This language has been specifically designed to support the student 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 complexities of floating point arithmetic and multiple data sizes), an unambiguous language definition (guarding against relying on undefined behavior), and contracts (making code expectations explicit and localize reasoning).
The C Language
In the last six weeks, the course transitions to C in preparation for subsequent systems courses. Emphasis is on transferring positive habits developed in 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.
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 Autolab
— you may want to make sure they work on Andrew Unix
. Popular environment choices include emacs
, 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
- 24 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.
- 14 weekly written assignments (due on Gradescope Mondays at 9pm — strict!)
- 10 mostly weekly programming assignments (due on Autolab Thursdays at 9pm — strict!)
- No joint homework unless explicitly instructed.
- 2 midterm exams: 12.5% each, in class, closed books, on and
- Final exam: 25%, 3 hours, closed books, on
- Labs, recitations and quizzes: 5%
Each lab is graded on a 0-3 point scale, assigned as follows:
Each recitation is graded on a 0-2 point scale, assigned as follows:
- 3 points for completing all exercises
- 2 points for completing sufficiently many exercises
- 1 point for completing some exercises but not quite enough to get a good practice
- 0 points for not completing any exercise, not showing up, or coming to the wrong section
Each quiz is graded based on the number of questions it asks.
- 2 points for completing sufficiently many exercises
- 0 point for completing some
exercises but not quite enough to get a good practice, or coming to
the wrong section
All you need is 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 do poorly in one quiz or miss a lab. Do the math: the course has
- 13 graded labs
- 13 recitations
- a few quizzes (done during lecture and/or recitation)
We are aiming to have homework and exams graded within two days of submission.
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 expected to write code with good programming style. See these notes about what constitutes good style.
For a small subset of assignments, TAs will review all final submissions by hand. If there are significant style issues, they may give a non-passing grade on style, accompanied by “FIX STYLE” annotations in their code. Students who are told to fix their style must address these issues and discuss their revisions with a TA within 5 days of the style 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.
: We seek to promote good time and risk management habits. You will receive an extra 2%
of the earned
grade of a homework for each 12-hour period you submit it ahead of the deadline, starting the countdown 4 days prior to the deadline.
There are no late days
. Assignments submitted past the deadline will get a grade of 0.
- Nearly all situations that lead to asking for an extension to a 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.
- I got sick: start early and make use of bonus points
- Use bonus points as your insurance policy for unforeseen situations.
We make mistakes too!
After each exam and homework assignment 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. Any TA is permitted to fix simple arithmetic errors (and, at their discretion, other blindingly obvious grading errors). For any other grading issues, you must request a regrade as follows:
- Compose a letter explaining where and why you think there was a mistake in grading. Write a short paragraph for each response you are disputing. Date and print your letter.
- Hand-deliver a signed hardcopy of this letter to in . Slide them under her door if she is not in. Verbal or email requests will not be accepted.
- All regrade requests must be recieved within 5 days of the work being handed back on Gradescope or Autolab.
This class is not curved.
What follows is a rough guide
to how final grades will be established, not a precise formula — we will fine-tune thresholds 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 between final grades and total scores:
- A: above 90%
- B: 80-90%
- C: 70-80%
- D: 60-70%
This heuristic assumes that the makeup of a student’s grade is not wildly anomalous: exceptionally low overall scores on exams, programming assignments, or written assignments may be treated on a case-by-case basis. For reference, almost a quarter of the students who recieved 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 recitation and exam performance when assigning the final grade.
You are expected to comply with the University Policy on Academic Integrity and Plagiarism
(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
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 other(s).
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, or giving or receiving unauthorized information during an examination. In general, each solution you submit (quiz, written assignment, programming assignment, midterm or final exam) must be your own work. In the event that you use information written by another person 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, discuss details of solutions, or sit near another person who is taking the same course and try to complete the assignment together. 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.
We will be using the Moss
system to detect software plagiarism.
It is not considered cheating to clarify vague points in assignments, lectures, lecture notes, or 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).
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 recitation into account when setting final grades. Therefore, please attend the lecture, lab, and recitation you are registered for.
Laptops and mobile devices
As research on learning shows, unexpected noises and movement automatically divert and capture people’s attention, which means you are affecting everyone's learning experience if your cell phone, pager, laptop, etc, makes noise or is visually distracting during class. Therefore, please silence all mobile devices during class. You may use laptops for note-taking only, but please do so from the back of the classroom. Do not work on assignments for this or any other class while attending lecture or recitation.
Students with disabilities
If you wish to request an accommodation due to a documented disability, please inform your instructor and contact Disability Resources as soon as possible (). Special accommodation for exams will be coordinated by the instructors, and must be requested for each exam separately a week in advance.
Take care of yourself.
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:
- 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 me know.
Students should leave this course 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 should leave this course 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,
- 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 should leave this course 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:
- define and describe big-O notation, both formally and informally.
- compare common complexity classes like O(1), 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.