Principles of Imperative Computation (Spring 2024) (2024)

This course teaches imperative programming in a C-like language andmethods for ensuring the correctness of imperative programs. It isintended for students who are familiar with elementary programmingconcepts such as variables, expressions, loops, arrays, andfunctions. Given these building blocks, students will learn theprocess and techniques needed to go from high-level descriptions ofalgorithms to correct imperative implementations, with specificapplications to basic data structures and algorithms. Much of thecourse 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 totake 15-213(Introduction to Computer Systems), 15-210(Parallel and Sequential Data Structures and Algorithms)and 15-214(Principles of Software System Construction). Otherprerequisites or restrictions may apply.

Prerequisites

You must have gotten a 5 onthe AP Computer Science A exam orpassed 15-112(Fundamentals of Programming) or equivalent. You may alsoget permission from an advisor if you performed very high on the CSAssessment on Canvas.

It is strongly advised that you either have taken or take atthe same timeeither 21-127(Concepts of Mathematics)or 15-151(Mathematical Foundations of Computer Science): historically,students who did not do so ended up learning less, spendingconsiderably more time on the course and earning one letter gradelower than their peers who did, on average.

Past Offerings

Our goals are for you to succeed in this course and to teach youskills and concepts that will contribute to your success in life. Tothis end, we are providing you with lots of resources and theknowledge that comes from years of experience. Talking to some of thethousands of students who took this course before you, here's someadvice 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 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.

Feedback

It is our goal to make this course successful, stimulating andenjoyable. If at any time you feel that the course is not meetingyour expectations or you want to provide feedback on how the course isprogressing for you, please contact us. If we are not aware about a problem, we won't know tofix it. If you would like to provide anonymous comments, pleaseuse the feedback form on the course home pageor slide a note under our doors.

Course Material

There is no textbook for this course. Lecture notes and otherresources are provided throughthe Schedule tab of this page andon . We do not requirestudents to read lecture notes before lecture, but those who areinterested in reading ahead can certainly do so.

The C0 Language

In the first nine weeks, the courseuses C0, a safe subset of Caugmented with contracts. This language has been specificallydesigned to support the learning objectives in thiscourse. It provides garbage collection (freeing students fromdealing with low-level details of explicit memory management), fixedrange modular integer arithmetic (avoiding complexities of floatingpoint arithmetic and multiple data sizes), an unambiguous languagedefinition (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 forsubsequent systems courses. Emphasis is on transferring positivehabits developed with the use of C0, and on practical advice foravoiding the pitfalls and understanding the idiosyncrasies of C. Weuse the

tool totest proper memory management.

• From C0 to C: Basics tutorial
• C Language Libraries
  • C string library <string.h>
• POSIX library standard — Unix standard library definitions including a library search functionality

Programming Environments

You are welcome to use any programming environment that suits you towrite your programming assignments. However, all programming homeworkwill be graded by running them on a Unix systemusing Autolab — you may want tomake sure they workon Andrew Unix. Popular environment choicesinclude emacs, vim and VSCode,

but you shoulduse what works for you: an environment that allows you to write codequickly and efficiently. Here are some useful links:

This is a 12 unit course.

Tasks and Percentages

• 23 homework assignments: 45%
  • 12 weekly written assignments (due on Gradescope Mondays at 9pm Pittsburgh time — strict!)
  • 11 weekly programming assignments (due on Autolab Thursdays at 9pm Pittsburgh 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.
  • Assignments are individual unless explicitly instructed.
• 2 midterm exams: 10% and 15%, in class, closed books, on and
• Final exam: 25%, 3 hours, closed books, on
• Labs and activities: 5%
  Each lab is graded on a 0-4 point scale, assigned as follows:
  • 4 points for completing all exercises
  • 3 points for completing sufficiently many exercises
  • 1.5 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
  There will be one activity worth 1 point during or after each lecture. Use the activities page to test your configuration and do the current activity (if there is one).
  The labs and activities grade is calculated based on the bucket system: All you need to earn the full 5% grade for this portion of the course is to accumulate 50 points overall. There are many more points than that for grabs, so nosweat if you miss a lab or a lecture. Do the math: thecourse has
  • 14 graded labs
  • 24 lectures

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 Gradestab of this page. After authenticating, you will be able to see yourcurrent grades and a projection of where you are headed given yourpast performance in the class. Use this application to take action ifthe 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 on 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 helpstudents from falling behind.

• There are no late days for written assignments, but written homework will be accepted until 9am the day after the deadline and eligible for 75% of the points. Gradescope handles late submissions automatically — you don't have to email the course staff, just turn in the assignment between 1 second late and 9am the day after the deadline.
• Each student has 3 late days for programming assignments and you may use at most one late day for each individual assignment. This means that for exactly 3 programming deadlines you can turn in your assignment within 24 hours after the deadline. Autolab handles these late days automatically — you don't have to email the course staff, just turn in the assignment between 1 second late and 24 hours after the deadline. You can find how many late days you have used by clicking on "Gradebook" in Autolab. Once you have ran out of late days, Autolab will accept and grade late submissions but will assign them 0 points.

  We strongly advise students not to use late days in the first half of the course. Later assignments are more challenging and many courses have lots of deliverables towards the end of the semester. The second half of the semester is where late days are most needed.

Aside from this, there will be no extensions on assignments ingeneral. If you think you really really need an extension ona particular assignment, contact the instructors as soon as possible and before the deadline.Please be aware that extensions are entirely discretionary and will begranted only in exceptional circ*mstances outside of your control(e.g., due to severe illness or major personal/family emergencies, butnot for competitions, club-related events or interviews). Theinstructors will require confirmation from University Health Servicesor your academic advisor, as appropriate.

Nearly all situations that make you run late on an assignment homeworkcan be avoidedwith 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 exam and homework assignment is graded, you will be able toaccess your score by clicking on theGrades tab of thispage. We will make the utmost effort to be fair and consistent in ourgrading. 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 donot make regrade requests on .

All regrade requests must be received within 5 days of the workbeing handed back on Gradescopeor Autolab, which we will announce ina post.

Final Grades

This class is not curved. However, to ensure consistency acrosssemesters, we set our grading standards in such a way as to compensatefor the relative difficulty of exams.

What follows is a rough guide to how course grades will beestablished, not a precise formula — we will fine-tune cutoffsand other details as we see fit after the end of the course. This ismeant to help you set expectations and take action if your trajectoryin the class does not take you to the grade you are hoping for (seealso the Grades tab on this page). So,here's a rough, very rough heuristics about thecorrelation 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 wildlyanomalous: exceptionally low overall scores on exams, programmingassignments, or written assignments will be treated on a case-by-casebasis. In particular, students who are unable to demonstrate a basicproficiency with the C language in the last few programmingassignments will receive a D in the class (this is because 15-122 is aprerequisite to 15-213, a very C-intensive course).For reference, almost a quarter of the students who received a B inFall 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 theirdiscretion, consider participation in lecture and recitation, examperformance 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 beapplied rigorously. All students are required to fill outa form as part of their first assignmentindicating that they understand and accept this policy.

The value of your degree depends on the academic integrity of yourselfand your peers in each of your classes. It is expected that, unlessotherwise instructed, the work you submit as your own is your own workand not someone or something else’s work or a collaboration betweenyourself and other(s).

The Policy (Spring'24)

You are allowed to clarify the writeup of homework assignmentswith other students, but not work on a solution or brainstormanswers with them.

You are welcome to freely discuss course material (lecturenotes/slides, practice exams, lab handouts, recitation handouts, blankwrittens and programming writeups) as well as to review gradedassignments 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/orcode are never visible).

You are not allowed to refer to solutions and/or code written by pastor present students, ChatGPT or other AI-based tools, or found on theweb, not even to "double-check" your own solution. You may not postcode from this course publicly (e.g., to Bitbucket or GitHub).

You are not allowed to use any materials from previous iterations of thecourse, including your own. You may not discuss or receive any help onhomework assignments with students who have previously taken thecourse (excluding current TAs).

We will be using the MOSS system to detect software plagiarism. Whenever a programming assignment is similar to a homework from a previous course edition, we will run MOSS on all submissions from that edition as well. All solutions from the Web are also in MOSS — you should assume that if you were able to find it, we have already found it.

If you are uncertain whether your actions will violate this policy, please reach out to a member of course staff to ask beforehand.

Penalties and Specifics

Please readthe UniversityPolicy on Academic Integrity carefully to understand the penaltiesassociated with academic dishonesty at Carnegie Mellon. In this class,cheating/copying/plagiarism means obtaining all or part of a programor homework solution from another student or tool, or unauthorizedsource such as the Internet, having someone else do a homework or takean exam for you, knowingly or by negligence giving such information toanother student, reusing answers or solutions from previous editionsof the course, or giving or receiving unauthorized information duringan examination. In general, each solution you submit (writtenassignment, programming assignment, midterm or final exam) must beyour own work. In the event that you use information written by othersin your solution, you must cite the source of this information (andreceive prior permission if unsure whether this is permitted). It isconsidered cheating to compare complete or partial answers, copy oradapt others' solutions, or sit near another person who is taking (orhas taken) the same course and complete the assignment together.Working on code together, showing code to another student and lookingat another student's code are considered cheating. If you need helpdebugging, make a post on or goto office hours. It is also consideredcheating for a repeating student to reuse one's solutions from aprevious semester, or any instructor-provided sample solution. It isa violation of this policy to hand in work for other students.

Your course instructors reserve the right to determine an appropriatepenalty based on the violation of academic dishonesty that occurs.Penalties are severe: a typical violation of the university policyresults in the student failing this course, but may go all the way toexpulsion from Carnegie Mellon University. If you have any questionsabout this policy and any work you are doing in the course, pleasefeel free to contact the instructorsfor help.

Repeat Students

If you took this course in full or in part in a past semester, we askthat you delete your previous work so you won't look at it. Inparticular, copying one's own solutions from an earlier semester is aviolation of the academic integrity policy and will be handled assuch. Doing so may save time close to a deadline but it will not havethe effect of learning the material, which will be a serious handicapin exams.

Class presence and participation

Active participation by you and other students will ensure thateveryone has the best learning experience in this class. We may takeparticipation in lecture and recitation into account when settingfinal grades. Fire safety rules require that we never exceed thestated capacity of a classroom or cluster. For this reason, werequire that you attend the lecture, lab, and recitation you are registered for.

Laptops and mobile devices

As research on learning shows, unexpected noises and movementautomatically divert and capture people's attention, which means youare affecting everyone's learning experience if your cell phone,pager, laptop, etc, makes noise or is visually distracting duringclass. Therefore, please silence all mobile devices during class. Youmay use laptops for note-taking only, but please do so from the backof the classroom. Do not work on assignments for this or any otherclass while attending lecture or recitation.

Students with disabilities

If you wish to request an accommodation due to a documenteddisability, please inform your instructor andcontact Disability Resources as soon as possible(). Once your accommodation has been approved, youwill be able to request extra-time for each exam separatelyby filling this form a week in advance.

Research to Improve the Course

For this class, we are conducting research on student outcomes. Thisresearch will involve your work in this course. You will not be askedto do anything above and beyond the normal learning activities andassignments that are part of this course. You are free not toparticipate in this research, and your participation will have noinfluence on your grade for this course or your academic career atCMU. If you do not wish to participate or if you are under 18 years ofa*ge, please send an email to Chad Hershock() with your name and course number. Participantswill not receive any compensation. The data collected as part of thisresearch may include student grades. All analyses of data fromparticipants’ coursework will be conducted after the course is overand final grades aresubmitted. The Eberly Centermay provide support on this research project regarding data analysisand interpretation. The Eberly Center for Teaching Excellence &Educational Innovation is located on the CMU-Pittsburgh Campus and itsmission is to support the professional development of all CMUinstructors regarding teaching and learning. To minimize the risk ofbreach of confidentiality, the Eberly Center will never have access todata from this course containing your personal identifiers. All datawill be analyzed in de-identified form and presented in the aggregate,without any personal identifiers. If you have questions pertaining toyour rights as a research participant, or to report concerns to thisstudy, please contact Chad Hershock().

Personal Health

Take care of yourself.

Do your best to maintain a healthy lifestyle this semester by eatingwell, exercising, avoiding drugs andalcohol, getting enough sleep and taking some time to relax. This will help youachieve your goals and cope with stress.

All of us benefit from support during times of struggle. You are notalone. There are many helpful resources available on campus and animportant part of the college experience is learning how to ask forhelp. Asking for support sooner rather than later is often helpful.

If you or anyone you know experiences any academic stress, difficultlife events, or feelings like anxiety or depression, we stronglyencourage you to seek support. Counseling and Psychological Services(CaPS) is here to help: call 412-268-2922 and visittheir website. Considerreaching out to a friend, faculty or family member you trust for helpgetting connected to the support that can help.

If you or someone you know is feeling suicidal or in danger ofself-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 inthis class, visit the Global Communication Center (GCC). GCC tutorscan provide instruction on a range of communication topics and canhelp you improve your papers and presentations. The GCC is a freeservice, open to all students, and located in Hunt library. You canmake tutoring appointments directly on the GCCwebsite.You may also visit the GCC website to find out about communicationworkshops offered throughout the academic year.

External Academic Support

The Office of Academic Development is providing various services aimed at helpingstudents master the contents of this course. These optionalservices are free and voluntary. They are led by trainedleaders who have successfully completed the course. Leaders are notmembers of the course staff. These services are are designed to supplement— not replace — class lectures and recitations. They donot 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.

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

One-on-one Tutoring

Students can book an appointment for a virtual tutoring session.

We ask that students do not seek help from upperclassmates whohave successfully completed the course. Doing so often leads toviolations of the academic integrity policy of the course. In particular, upper-classmates found to violate thispolicy will be reported and will incur a grade penalty.

Computational Thinking

Students who complete this course should be able to explainabstraction and other key computer science concepts, apply thesefundamental concepts as problem-solving tools, and wield contracts asa tool for reasoning about the safety and correctness of programs. Inparticular, 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 writecode for imperative algorithms and data structures. In particular, weexpect 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 environmentusing make, gcc, and valgrind.

Algorithms and Data Structures

Students who complete this course should be able to describe theimplementation of a number of basic algorithms and data structures,effectively employ those algorithms and data structures, and explainand interpret worst-case asymptotic complexity arguments. Inparticular, 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.