Assignments
Week 1
TODOs / Deadlines
-
Exercises
1
(
recursion) released.
-
Lab
1
(
find) released.
-
Lab
1
(
find) due.
New syntax, APIs, and tools
Scala
def=>…(by-name){}if…then…else…val- operators:
&&,||,==,<,>,<=,>=,+,*,-,/,% - Basic types:
Int,Boolean,String - But not:
varforwhile
Tools
- SBT (builds)
- MUnit (tests)
- Git (version control)
- Command-line interfaces
- Worksheets
- The Scala REPL
Monday ✅
Intro to Functional Programming
Concepts
- Functional programming
- Recursion
- Values and definitions
- Evaluation strategies
- Conditionals
- Newton’s method
- Lexical scope
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.
-
Lab
2
(
boids) released. -
Exercises
2
(
higher-order-functions) released.
-
Lab
1
(
find) due.
-
Lab
2
(
boids) due.
New syntax, APIs, and tools
…=>…(function types)f(…)…(…)(currying)_,…=>…(anonymous functions)class,private,this,override- Auxiliary constructors
f"…$…",f"…${…}…"(string interpolation)assert,require- JSON
Monday
No class on Monday!
(Federal holiday)
What better time to learn Git?
Wednesday ✅ 🧩
Functions
Concepts
Tail recursion- Higher-order functions (HOFs)
- Currying
- Scala syntax summary
- Functions and data
- 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
-
Exercises
3
(
pattern-matching) released.
-
Lab
3
(
calculator) released. -
Callback
1
(
find-hof) released. -
SE Exercises
2
(
debugging) released.
-
Lab
2
(
boids) due.
-
Lab
3
(
calculator) due. -
Callback
1
(
find-hof) due.
New syntax, APIs, and tools
- Extension methods
- Operators, infix notation
@mainpackage,importAny,AnyRef,AnyVal,Nothing- Traits
- Abstract classes
object(singletons)- Case classes
- Enums
match…case…=>…
Monday 🧩
Class hierarchies
Concepts
- Evaluation and operators
- Class hierarchies
- Dynamic dispatch
- Classes organization
- Objects everywhere
- Functions as objects
- Decomposition
- Pattern matching
- Enums
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
-
Exercises
4
(
polymorphism) released. -
Exercises'
5
(
equational-reasoning) released.
-
Lab
3
(
calculator) due. -
Callback
1
(
find-hof) due.
-
Lab
4
(
huffman) due.
New syntax, APIs, and tools
Scala
class C[T](generic classes)def f[T](polymorphic methods)(…,…,…)(tuples)requires,ensuringOptionEither-
ListandListmethods
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
ListAPI. - 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
-
Exercises
6
(
comprehensions) released. -
Exercises'
7
(
variance) released.
-
Lab
5
(
anagrams) released. -
Callback
2
(
callback-unguided) released. -
SE Exercises
4
(
specs) released.
-
Lab
5
(
anagrams) due.
New syntax, APIs, and tools
Monday 🧩
Collections and comprehensions
Concepts
- Type bounds
- Variance
- Generic collections
- Combinatorial search and
forcomprehensions
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
-
Exercises
8
(
parallelism) released.
-
Lab
6
(
scalashop) released.
-
Lab
5
(
anagrams) due. -
Callback
2
(
callback-unguided) teams due. -
Callback
2
(
callback-unguided) proposal due.
-
Lab
6
(
scalashop) due. -
Callback
2
(
callback-unguided) due.
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
mapandreduce.
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
-
Exercises
9
(
laziness) released.
-
Poll
2
(
October) released. -
Lab
6
(
scalashop) due. -
Callback
2
(
callback-unguided) due. -
Callback
2
(
callback-unguided) checkoff registration due.
- 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
- Midterm!
-
Lab
7
(
pathfinder) released.
-
Poll
2
(
October) due.
-
Callback
2
(
callback-unguided) checkoff due.
-
Lab
7
(
pathfinder) due.
New syntax, APIs, and tools
- Java Sound API
- Unit suffixes and the
DurationAPI :,{}(block-based argument passing)
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.
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.
-
Callback
2
(
callback-unguided) checkoff due.
-
Lab
8
(
webapp-rps) released. -
SE Exercises'
7
(
git-2) released.
-
Lab
7
(
pathfinder) due. -
Lab
9
(
webapp-unguided) teams due.
-
Lab
8
(
webapp-rps) due. -
Lab
9
(
webapp-unguided) proposal due.
New syntax, APIs, and tools
Scala
Tools
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
-
Exercises
11
(
mutation-reasoning) released. -
Lab
9
(
webapp-unguided) released.
-
Exercises'
13
(
contextual-abstraction) released.
-
Lab
8
(
webapp-rps) due. -
Lab
9
(
webapp-unguided) proposal due.
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
-
Exercises
12
(
safe-effects) released.
-
Lab
9
(
webapp-unguided) checkoff registration due.
New syntax, APIs, and tools
Tools
- GitLab
- GitHub
gitrange-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:
- Detailed plans for the complete app:
- 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.
- A minimal prototype capturing the essence of your app:
- Backend: A working implementation of a very simplified state machine;
- Frontend: A simplified UI able to communicate with the basic backend.
Most important exercises
Safe effects
Version control
Callback
No more callbacks this semester!
Week 12
TODOs / Deadlines
-
Exercises
14
(
futures) released.
-
SE Exercises
9
(
pbt) released.
-
Poll
3
(
November) due. -
Lab
9
(
webapp-unguided) checkoff registration due.
-
Lab
9
(
webapp-unguided) due.
New syntax, APIs, and tools
Scala
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 a second, nearly-complete prototype 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
Property-based testing
Callback
No more callbacks this semester!
Week 13
TODOs / Deadlines
-
Exercises
15
(
stainless-verification) released. -
Exercises''
16
(
verification) released.
-
Lab
9
(
webapp-unguided) due.
-
Lab
9
(
webapp-unguided) checkoff due.
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:
- Implement any bonus features left for the end.
- 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
-
Lab
9
(
webapp-unguided) checkoff due.
-
Poll
4
(
December) due.
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!