The syllabus below is provisional and provided for informational purposes only. It will be updated throughout the semester. See Moodle for binding deadlines.

Assignments

CS-214 timeline

Week 1

TODOs / Deadlines

  • Lab 1 (find) released.

New syntax, APIs, and tools

Scala

Tools

Monday  ✅

Intro to Functional Programming

Concepts

  • Functional programming
  • Recursion
  • Evaluation strategies

Learning objectives

  • Contrast functional and imperative styles.
  • Write simple recursive functions in Scala.
  • Reason about code execution using the substitution method.

Wednesday  🛠️

Version control

Concepts

  • Changesets / Commits / Revisions
  • History / Log
  • Patches
  • Blame

Learning objectives

  • Describe the value of version control systems for individual & collaborative projects.
  • Track and explore software history using Git.

Lab

Find

Concepts

  • APIs
  • Tree traversals
  • Tests & Mocking

Goal

Implement a simpler version of the Unix find command (traverse a file system and print entries matching a rule).

Most important exercises

Callback

No callbacks until week 3!

Week 2

TODOs / Deadlines

  • SE Exercises 1 (git-1) released.

New syntax, APIs, and tools

Monday 

No class on Monday!
(Federal holiday)

What better time to learn Git?

Wednesday  ✅ 🧩

Functions

Concepts

  • Higher-order functions (HOFs)
  • Currying
  • Data abstraction

Learning objectives

  • Modularize code by abstracting over repeated patterns.
  • Convert between curried and multi-argument functions.
  • Solve data-processing problems using higher-order functions.

Lab

Boids

Concepts

  • HOFs
  • Modeling
  • Collections
  • Immutability
  • Integration tests

Goal

Explore emergent behaviors in bird-flight patterns by implementing a discrete-time artificial-life simulation.

Most important exercises

HOFs

Git

Callback

No callbacks until week 3!

Week 3

TODOs / Deadlines

New syntax, APIs, and tools

Monday  🧩

Class hierarchies

Concepts

  • Class hierarchies
  • Dynamic dispatch
  • Functions as objects
  • Pattern matching

Learning objectives

  • Modularize code by abstracting over implementation details.
  • Model pure data using case classes and enums.
  • Contrast object-oriented decomposition and pattern-matching.

Wednesday  ✅ 🛠️

How to diagnose (almost) anything

Concepts

  • Bug triage
  • Issue reports
  • Minimization
  • Modeling
  • The experimental method

Learning objectives

  • Identify and describe unwanted behaviors.
  • Produce useful and complete defect reports.
  • Pinpoint the root cause of an issue.
  • Identify and avoid common debugging pitfalls.

Lab

Calculator

Concepts

  • Pure data
  • Pattern matching
  • Structural recursion
  • Tree traversals
  • Debugging

Goal

Implement a mini-programming language for arithmetic expressions, complete with an interpreter (evaluator), an optimizer (simplifier), and tests.

Most important exercises

Pattern matching

Debugging

Callback

Find with HOFs

This week’s assignments include the first of three callbacks: a mini-lab in which you revisit and improve the implementation of a previous assignment.

In find-hof, you’ll refactor find to remove redundant code and simplify the implementation. This sort of refactoring task is a common aspect of any software-engineering job.

Week 4

TODOs / Deadlines

New syntax, APIs, and tools

Scala

Tools

  • CS-214 Proof Checker
  • MUnit: FunSuite, test("..."), assertEquals

Monday  🧩

Polymorphism

Concepts

  • Generics
  • Equational reasoning
  • Structural induction
  • Higher-order list functions

Learning objectives

  • Modularize code by abstracting over types.
  • Express complex list manipulations using the List API.
  • Prove properties of programs using induction and equational proofs.
  • Use an automated proof checker to validate proofs.

Wednesday  ✅ 🛠️

From tests to proofs I

Concepts

  • Instrumentation
  • Regressions
  • Unit tests
  • Integration tests
  • System tests
  • Acceptance tests
  • Preconditions and postconditions
  • Monitoring

Learning objectives

  • Understand code execution by inserting tracing statements.
  • Design tests to express requirements, find bugs, and prevent regressions.
  • Capture expected run-time behavior using dynamic checks (monitoring).

Lab

Huffman coding

Concepts

  • Parametric polymorphism
  • Specifications
  • Algorithms
  • Computational complexity

Goal

Implement a file compression and decompression utility using Huffman coding.

Most important exercises

Recursion

Equational reasoning

Tests

Callback

No callback this week! But you can already start thinking about your own unguided callback.

Week 5

TODOs / Deadlines

New syntax, APIs, and tools

Monday  🧩

Collections and comprehensions

Concepts

  • Type bounds
  • Variance
  • Generic collections
  • Combinatorial search and for comprehensions

Learning objectives

  • Modularize code by abstracting over container types.
  • Identify co- and contravariant positions and justify variance rules.
  • Solve enumeration problems via backtracking search.
  • Compare and contrast collection datastructures.

Wednesday  ✅ 🛠️

From tests to proofs II

Concepts

  • User stories
  • Requirements
  • Specifications
  • Formal specifications

Learning objectives

  • Translate informal specifications into pre- and post-conditions.
  • Formulate high-level properties as logical predicates.
  • Reason about the completeness of specifications.

Lab

Anagrams

Concepts

  • Combinatorics
  • Comprehensions
  • Puzzling
  • Backtracking
  • Trees
  • Maps

Goal

Copmute agnarams of idnviudial wrods and setnneces.

Most important exercises

Comprehensions

Variance

Specs

Callback

No callback this week! But you can already start thinking about your own unguided callback.

Week 6

TODOs / Deadlines

New syntax, APIs, and tools

Monday  ✅

Principles of parallelism

Concepts

  • Parallelism
  • Threads, cores, processes
  • Dependencies
  • Race conditions
  • Divide and conquer
  • Associative operations
  • Map-reduce

Learning objectives

  • Contrast sequential and parallel algorithms.
  • Identify opportunities to parallelize computations.
  • Speed up programs using data parallelism and the parallel collections library.
  • Express associative sequential computations as a combination of map and reduce.

Wednesday  ✅

Wednesday.par

Concepts

  • Algebraic properties of pure computations
  • Work and depth

Learning objectives

  • Use algebraic reasoning to identify computations that can be performed in parallel.
  • Reason about equalities modulo associativity and commutativity.
  • Analyze the computational complexity of parallel programs in terms of work and depth.

Lab

Scalashop

Concepts

  • Inheritance
  • Arrays
  • Data locality
  • Parallel collections

Goal

Implement common image filters, using parallelism to speed up computations.

Most important exercises

Callback

Unguided callback

Develop your independence, project-planning abilities, and code-reviewing skills by designing and implementing your own callback.

Week 7

TODOs / Deadlines

  • Midterm!

New syntax, APIs, and tools

Monday  🧩

Laziness

Concepts

  • Lazy lists
  • Lazy evaluation
  • Infinite data

Learning objectives

  • Modularize code by abstracting over control flow.
  • Apply the substitution method to evaluate code using delayed execution.
  • Contrast lazy and eager evaluation.
  • Reason about termination of lazy programs.

Wednesday  🛠️

Purely functional data structures

Concepts

  • Path copying
  • Sharing
  • Logarithmic depth

Learning objectives

  • Reason about the performance and memory usage of purely functional code.
  • Formulate and check data-structure invariants.

Lab

No new lab this week! Focus on preparing for the midterm.

Most important exercises

Laziness

Callback

No new callback this week!

Week 8

TODOs / Deadlines

New syntax, APIs, and tools

Monday  🛠️ 💻

Practical engineering I: Signal processing with lazy lists

Concepts

  • APIs
  • Quantization
  • Software engineering
  • Infinite streams

Learning objectives

  • Model infinite processes using lazy data.
  • Use collection methods to create and combine lazy lists.

Wednesday  ✅ 🧩 🛠️

Midterm!

In scope for the midterm: everything up to and including Wed, Oct 16 (weeks 1 to 6), including the ScalaShop lab.

Study guide

Lab

Path finder

Concepts

  • Graphs
  • Laziness
  • Breadth-first search (BFS)

Goal

Use breadth-first search to solve puzzles by encoding move sequences as paths in a graph.

Most important exercises

Callback

find-lazy callback canceled!

Week 9

TODOs / Deadlines

  • SE Exercises 6 (webapps) released.

New syntax, APIs, and tools

Scala

Tools

  • git init, clone, checkout, reset, status, add, commit, format-patch, show, log, shortlog, blame, am, cherry-pick, rebase, branch, merge, switch
  • sbt new
  • Cask

Monday  🛠️ 💻

Practical engineering II: Webapps

Concepts

  • Transition systems
  • Distributed systems
  • Client-server architectures
  • Sequential consistency
  • Information flow control

Learning objectives

  • Decompose multi-user applications into states, views, and events.
  • Implement interactive interfaces using webpages and terminal-based displays.
  • Test complex sequences of events with integration tests.

Wednesday  🛠️

Distributed version control

Concepts

  • Commit graphs
  • Branching
  • Merging
  • Conflict resolution
  • Diff of diff

Learning objectives

  • Describe fundamental distributed version-control concepts.
  • Follow the evolution of long-lived software.
  • Understand and reconcile conflicting software changes.

Lab

Webapp

Concepts

  • State machines
  • Serialization
  • Distributed apps

Goal

Implement the logic of a distributed web application, and get familiar with the architecture of the unguided lab.

Most important exercises

Webapps

Version control

Callback

No more callbacks this year!

Week 10

TODOs / Deadlines

New syntax, APIs, and tools

Scala

Monday  ✅

Imperative programming

Concepts

  • Imperative code
  • Effects
  • Mutation
  • Loops
  • State machines
  • Hoare triples

Learning objectives

  • Identify pitfalls of mutation.
  • Write imperative programs in Scala.
  • Model imperative processes using state machines.
  • Reason about imperative programs using Hoare triples.

Wednesday  🧩

Contextual abstraction I

Concepts

  • Implicit parameters
  • Retroactive extension
  • Conditional instances

Learning objectives

  • Modularize code by abstracting over context.
  • Identify use cases for implicit parameters.

Lab

Welcome to the unguided webapp lab! This is the final lab of the semester, spanning four weeks.

By the end of this week, you should have:

  • A team (3 or 4 people; due last week).
  • A proposal for what app you want to build.
  • A clear division of tasks within your team.

You can start working on your app as soon as you have a team and a proposal!

Most important exercises

State

Contextual abstraction

Callback

No more callbacks this semester!

Week 11

TODOs / Deadlines

New syntax, APIs, and tools

Tools

  • GitLab
  • GitHub
  • git range-diff, send-email

Monday  ✅

Safe uses of imperative programming

Concepts

  • Referential transparency
  • Exceptions
  • Tail recursion
  • Caching
  • Memoization

Learning objectives

  • Simplify complex logic using local exceptions.
  • Convert between loops and tail-recursive functions.
  • Use caching and memoization to reduce time and memory usage.

Wednesday  🛠️

Human aspects of software engineering

Concepts

  • Software forges
  • Collaboration
  • Changelogs
  • Responsibility

Learning objectives

  • Describe challenges in large-scale decentralized software development.
  • Use online forges and collaboration platforms.
  • Write detailed and useful commit messages.
  • Be nice to others.

Lab

Unguided webapp

By the end of this week, you should have your application fully planned out:

  • A clear implementation plan (on paper) for the whole app
  • Definitions and specifications for all shared interfaces (views and events)
  • Backend: A diagram showing state transitions and their impact on your app’s state
  • Frontend: UI mock-ups (drawings, code snippets)
  • Tests: Simple integration tests capturing the expected behavior of your transition and projection functions.

Most important exercises

Safe effects

Version control

Callback

No more callbacks this semester!

Week 12

TODOs / Deadlines

  • SE Exercises 9 (pbt) released.

New syntax, APIs, and tools

Monday  🧩

Asynchronous programming with Futures

Concepts

  • Futures
  • Promises
  • Asynchronicity
  • Callbacks
  • Inversion of control

Learning objectives

  • Modularize computation by emphasizing data flow, not control flow.
  • Speed up programs using task parallelism.
  • Express Future-based computations in direct and monadic styles.
  • Compare and contrast data-parallel and task-parallel execution.

Wednesday  🛠️ ✅

Automated testing

Concepts

  • Property-based testing
  • Executable specifications
  • Fuzzing

Learning objectives

  • Formulate local and global invariants.
  • Write custom generators to enable property-based testing.
  • Compare and contrast property-based testing and fuzzing.

Lab

Unguided webapp

By the end of this week, you should have most of your application implemented:

  • Backend: All state transitions and projections
  • Frontend: Complete UI and actions triggering transitions
  • Tests: Complete unit and integration tests, based on last week’s diagrams

Most important exercises

Futures

Callback

No more callbacks this semester!

Week 13

TODOs / Deadlines

New syntax, APIs, and tools

Scala

Tools

Monday  ✅ 💻

Formal verification

Concepts

  • Correctness
  • Formal specifications
  • Deductive verification

Learning objectives

  • Contrast bug-finding and verification techniques.
  • Formulate and encode program-correctness criteria and invariants.
  • Formally prove simple properties of functional and imperative Scala programs.

Wednesday  🧩

Contextual abstraction II

Concepts

  • Type classes
  • Opaque type aliases

Learning objectives

  • Modularize code by abstracting over context.
  • Identify use cases for typeclasses.
  • Use types to guarantee high-level safety properties.

Lab

Unguided webapp

By the end of this week, your webapp should be complete:

  • Integrate all parts of the app and debug any integration issues.
  • Make sure that all tests pass; document any failures or unimplemented parts.
  • Start preparing your demo.

Most important exercises

Contextual abstraction

Callback

No more callbacks this semester!

Week 14

TODOs / Deadlines

  • Final-exam dry run (attendance mandatory)
  • Poll 4 (December) released.
  • Exercises 16 (monads) released.

New syntax, APIs, and tools

Monday  🛠️

How to find a job in CS

Concepts

  • CVs
  • Portfolios
  • Networking
  • Motivation letters
  • Reference letters
  • Interviews

Learning objectives

  • Identify the key parts of the job-search process.
  • Build a compelling CV and portfolio.
  • Structure answers to skill- and situation-based interview questions.
  • Avoid common job-search pitfalls.

Wednesday  🧩 ✅

Monads

Concepts

  • Monads
  • Containers
  • Monadic laws

Learning objectives

  • Modularize code by encapsulating effects.
  • Reason about code equivalence using monadic laws.

Lab

Lab checkoffs throughout the week. Congrats on completing your app!

Most important exercises

Callback

No more callbacks this semester!