Title: Principles of Imperative Computation

Units: 12

Pre-requisites:

You must have passed 15-112 (Fundamentals of Programming) or equivalent. It is strongly advised that you either have taken or are currently taking 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.

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) and 15-210 (Parallel and Sequential Data Structures and Algorithms), among others. Other prerequisites or restrictions may apply.

---

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.

Activities

The course encompasses 23 lectures. In addition, it involves three forms of activities with varying quantities and overall weights as shown below:

1. Exams: 50%
   • 2 Midterm exams (12.5% each; in class; closed books)
   • 1 Final exam (25%; 3 hours; closed books)
2. Homework: 45%
   • 12 Written assignments due on Mondays at 9pm (strict!) and shall be submitted through Gradescope
   • 11 Programming assignments due on Thursdays and shall be submitted through Autolab
   To encourage good work and integrity, the instructor may invite students to his office to explain their solutions. Should this happen, the explanations of the students will become part of their grades for that homework.
3. Labs and Pop Quizzes: 5%

   There will be random pop quizzes alongside a lab every Tuesday. Each lab will be 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 or not showing up to the lab

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 programs 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; and clarity is paramount. You are also expected to write code with good programming style.

Late Policy

This is a fast-paced course. Below is the late policy, which has the purpose to help students from falling behind:

• There are no late days for written assignments, but written homework will be accepted until 8am the day after the deadline and eligible for 50% 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 8am 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 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:

• 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 a similar cloud solution to do real-time backup.
• My club has that big event that is taking all my time: Schedule your extra-curricular activities around your classes, not vice versa.

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. So, here's a rough, very rough heuristic about the correlation between final grades and total scores:

• A: 90% and above
• B: 80-89%
• C: 70-79%
• D: 60-69%
• R: Below 60%

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, the instructor may, at his discretion, consider participation in lecture and recitation, exam performance and overall grade trends when assigning the final grade.

For urgent communication with the professors and the course assistants, it is best to send an email. If you want to talk to any of them in person, remember that their office hours are merely nominal times upon which they guarantee that they will be in their offices. You are always welcome to visit them outside of their office hours if you need help or want to talk about any issue that pertains to the course.

We ask that you follow a few simple guidelines. The professors normally work with their office doors being open. Whenever the office doors are open, they welcome visits from students. However, if the office doors are closed, this means that they are busy with work, meetings, or phone calls; hence, prefer not to be disturbed.

We will use the course webpage as the central repository for all the course material. In particular, on the course webpage you can always:

• Obtain copies of any homework assignment and lecture slides.
• View announcements that relate to the course.
• Find links to any reference or data you need for your studying and assignments.
• Read clarifications and changes made to any assignments, schedules, or policies.

In addition, we will use Piazza for course announcements and online discussions. Use it to ask questions and to share your experience! The course staff will be happy to answer your questions in a timely manner. However, sometimes we might wait to answer in order to let others answer or for you to think about it a little more. We encourage you to answer each others' questions!

Another important issue appears while asking questions on Piazza. Please do not send your source code to ask questions. Your questions can be related to specific parts of your programs, but while others read your code they will be affected by your solutions. We need to let others find their own solutions for a better learning.

Lastly, all communication on Piazza should not include any inappropriate content or any form of expression that will be unethical or rude. Please find our 15122 Piazza page at: https://piazza.com/class/lcbsa78xhpy67w

The value of your degree depends on the academic integrity of yourself and your peers in each of your classes. Please read the University Policy on Academic Integrity (https://www.cmu.edu/policies/) carefully to understand the penalties associated with academic dishonesty at Carnegie Mellon University.

Academic integrity means that any work you submit for this course is your own. This is critical to your learning. The policy's intention is that you never hand in something you do not understand. Your understanding must be deep enough that, if necessary, you could re-do the work completely on your own. In short, do your own work.

We want you to collaborate with other students only if the collaboration improves your understanding. Therefore, you can talk about the homework assignments, but no one may take notes or record the discussion. When you write your solution, it should be yours. Go to a separate area and write your own code or answers. Do this individually so that you do not end up copying someone else's work. Your own solution, even if it is incorrect, is much better than someone else's that you do not understand.

When working on programming assignments, do not look at other students' code or show them your own. If you need that kind of help, get it from the course staff. You may discuss your code at a conceptual level; for example, "do we need a loop for this purpose or just an if statement?". You may collaborate on code at a whiteboard, but you may not take notes or photographs; the purpose of the collaboration is to develop your understanding so that you can then solve the problem yourself, on your own.

If the course staff sees similarities between your work and that of another student, we will attempt to understand what happened. Usually this involves asking you to explain your work and how you did it, and to re-create the work or solve a related problem during our meeting.

For exams, your work must be your own with no communication between you and others (except course staff), and you may use only authorized materials.

If you cannot keep up with the workload due to personal issues, please see your professor. He will help you work toward a solution and will be always happy to assist.

In this class, cheating, copying, or plagiarism means copying all or part of a program or homework solution from another student or unauthorized source, or knowingly giving such information to another student, or handing in a copy of work that you and another student did together, or giving or receiving unauthorized information during an examination. If you use information from another authoritative resource, you must cite the source of this information (and receive permission if required).

Students who violate this policy will be charged with academic dishonesty that can result in failure in this course and possible expulsion from Carnegie Mellon University. Review the official University Code for more information.

Each project or assignment must be the sole work of the student turning it in. Projects and assignments will be closely monitored, and students may be asked to explain suspicious similarities with any write-up or piece of code available. The following are guidelines on what cheating is and is not:

What is cheating?

• Sharing code or other electronic files: either by copying, retyping, looking at, or supplying a copy of a file.
• Sharing written assignments: either by re-writing, looking at, or supplying a copy of an assignment.

What is NOT cheating?

• Clarifying ambiguities or vague points in class handouts.
• Helping others use the computer systems, networks, compilers, debuggers, profilers, or other system facilities.
• Helping others with high-level design issues.
• Helping others debug their codes.

Consequently, be aware of what constitutes cheating (and what does not) when interacting with your colleague students. Same rules of cheating as above apply when collaborating with other students. In short, you cannot share written assignments, code, and/or other electronic files with other students. If you are unsure, ask the teaching staff.

Finally, be sure to store your work in protected directories. The penalty for cheating is severe, and might jeopardize your whole career as a student - cheating is not worth the trouble. By cheating in the course, you are cheating yourself; the worst outcome of cheating is missing an opportunity to learn. Besides, you will be removed from the course and assigned a failing grade. We also place a record of the incident in your permanent university profile.

Learning 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 this document.

Taking Care of Yourself

Do your best to maintain a healthy lifestyle this semester by eating well, exercising, 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-Q) is here to help: call 4454 8525 or make an appointment to see the counselor by emailing student-counselling@qatar.cmu.edu. Consider reaching out to a friend, faculty, or family member you trust for help.

If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night, at 5554-7913.

If the situation is life threatening, call 999.

Please refer to Schedule for the tentative schedule for the class. The schedule indicates the project and the assignment activities as well. Any changes will be always announced and reflected on this webpage.