CS 15-122: Principles of Imperative Computation
(Fall 2021)

About this course  [  Description  |  How to Do Well  |  Resources  |  Grading  |  Academic Integrity  |  Policies  |  Help  |  Learning Objectives  ]

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: 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) and 15-214 (Principles of Software System Construction). Other prerequisites or restrictions may apply.

Prerequisites

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 Canvas.
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

2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010
Fall F'21 F'20 F'19 F'18 F'17 F'16 F'15 F'14 F'13 F'12 F'11 F'10
Summer N'21 N'20 N'19 N'18 N'17 N'16 M'15 M'14 M'13 M'12 S'11
Spring S'21 S'20 S'19 S'18 S'17 S'16 S'15 S'14 S'13 S'12 S'11

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:

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 tab of this page and on . 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 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 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 four 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 Autolab — you may want to make sure they work on Andrew Unix. Popular environment choices include emacs, vim, VSCode, and sublime, but you should use what works for you: an environment that allows you to write code quickly and efficiently. Here are some useful links:
UnixEmacsVim

Grading

This is a 10 unit course.

Tasks and Percentages

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.

Evaluation Criteria

Your assignments and exams are evaluated on the basis of:

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 homework can be avoided with proper planning — often just starting early. Here are some examples:

Grade Appeals

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. If you notice any grading mistakes, proceed as follows: 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 Gradescope or Autolab, 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:

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 recitation, 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 else’s work or a collaboration between yourself and other(s).

The Policy (Fall'21)

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 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 them.

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 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 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, 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 for help.

Repeat Students

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 in exams.

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 recitation into account when setting final grades. Fire safety rules require that we never exceed the stated capacity of a classroom or cluster. For this reason, we require that you 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 (). Once your accommodation has been approved, you will be able to request extra-time for each exam separately by filling this form a week in advance.

Research to Improve the Course

For this class, your instructor is conducting research on student learning. This research will involve surveys and course work. 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, please send an email to Chad Hershock (). Please include your name and course number. 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. 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 ().

Getting Help

Personal Health

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 us know.

Communication

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 website. 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 Development 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 recitations. 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.
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 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.

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:
  1. develop contracts (preconditions, postconditions, assertions, and loop invariants) that establish the safety and correctness of imperative programs.
  2. develop and evaluate proofs of the safety and correctness of code with contracts.
  3. develop and evaluate informal termination arguments for programs with loops and recursion.
  4. evaluate claims of both asymptotic complexity and practical efficiency of programs by running tests on different problem sizes.
  5. define the concept of programs as data, and write programs that use the concept.
  6. defend the use of abstractions and interfaces in the presentation of algorithms and data structures.
  7. identify the difference between specification and implementation.
  8. compare different implementations of a given specification and different specifications that can be applied to a single implementation.
  9. explain data structure manipulations using data structure invariants.
  10. identify and evaluate the use of fundamental concepts in computer science as problem-solving tools:
    1. order (sorted or indexed data),
    2. asymptotic worst case, average case, and amortized analysis,
    3. randomness and (pseudo-)random number generation, and
    4. 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:
  1. trace the operational behavior of small imperative programs.
  2. identify, describe, and effectively use basic features of C0 and C:
    1. integers as signed modular arithmetic,
    2. integers as fixed-length bit vectors,
    3. characters and strings,
    4. Boolean operations with short-circuiting evaluation,
    5. arrays,
    6. loops (while and for),
    7. pointers,
    8. structs,
    9. recursive and mutually recursive functions,
    10. void pointers and casts between pointer types,
    11. generic data structures using void and function pointers,
    12. contracts (in C0), and
    13. casts between different numeric types (in C).
  3. translate between high-level algorithms and correct imperative code.
  4. translate between high-level loop invariants and data structure invariants and correct contracts.
  5. write code using external libraries when given a library interface.
  6. develop, test, rewrite, and refine code that meets a given specification or interface.
  7. develop and refine small interfaces.
  8. document code with comments and contracts.
  9. identify undefined and implementation-defined behaviors in C.
  10. 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:
  1. determine the big-O complexity of common code patterns.
  2. compare common complexity classes like O(1), O(log n), O(n), O(n log n), O(n2), and O(2n).
  3. explain the structure of basic amortized analysis proofs that use potential functions.
  4. apply principles of asymptotic analysis and amortized analysis to new algorithms and data structures.
  5. recognize properties of simple self-adjusting data structures.
  6. recognize algorithms and data structures using divide-and-conquer.
  7. describe and employ a number of basic algorithms and data structures:
    1. integer algorithms,
    2. linear search,
    3. binary search,
    4. sub-quadratic complexity sorting (mergesort and quicksort),
    5. stacks and queues,
    6. pseudo-random number generators,
    7. hash tables,
    8. priority queues,
    9. balanced binary search trees,
    10. disjoint-set data structures (union/find), and
    11. simple graph algorithms.

2021 Iliano Cervesato