15-122 Principles of Imperative Computation, Summer II 2018

Course Information, Summer II 2018

Lectures:	Monday-Friday, 10:30am-11:50am, GHC 4215
Labs and Recitations:	MTWRF (alternating days, see schedule), 3:00pm-4:20pm, GHC 5207/5208/5210
Instructor:	Hannah Gommerstadt (Office Hours MTWRF 2-3pm, 5th Floor Commons, these are meant to be conceptual office hours)
TAs:	See Staff page (Office Hours Monday-Sunday, GHC 4215)

About this course

Description

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), 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 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, on the average.

Learning Objectives

Computational Thinking

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.

Programming Skills

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,
  • arrays,
  • loops (while and for),
  • pointers,
  • structs,
  • 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.
• 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.