Last updated on Saturday, January 03, 2026

Week 13 Debrief: Webapps over!

Congrats on completing your 13th week of CS-214!

We’ve had a quick look at your webapps as you submitted them. Congratulations! You can be proud of the results you’ve achieved: We’re impressed by the creativity, skill, and dedication that you have poured into your projects.

Administrivia

Webapp checkoffs

• Don’t forget to submit your bundle! The extended deadline is Sunday the 14th at 23:00. There is no penalty for using the extension, but please submit early and make sure you receive 1/1 from the Moodle auto-grader.

• Please double-check your checkoff slot and fill in your self-evaluation. Without it, you won’t be able to get a checkoff.

• Make sure you are prepared for the checkoff! We have published an unguided checkoff guide on Ed.

• Monday, December 15th, will be very crowded. If you can, move your schedule to Tuesday or Friday. If you decide to stay on Monday, please be patient as we work through everyone.

Final exam dry-run

• The final exam dry run will take place this Wednesday. It will be held under real exam conditions and will last three hours.

• Seating charts will be posted before the dry-run.

• If you intend to bring a keyboard or mouse for the final, please make sure to test bring it on Wednesday and test it.

Interesting Ed questions

• Webapps
  • What should be documented in code?
  • Handling keyboard inputs.
• Final
  • Why can’t I access the solutions to previous finals?
• Scala programming
  • Can we use vars in tests?

What if my bundle is too big?

Our grader will struggle if your bundle is too big (the threshold is around 50MB).

Most of the time, a large bundle indicates that your history contains unnecessary data: for example, you may have committed build artifacts (.bsp/, .bloop/, target/, …) that should not have been included. In that case, the fix is to clean up your history. The simplest way to do this is to download git-filter-repo, then run (replacing .bloop with the folder you want to remove):

git-filter-repo --path .bloop --invert-paths

Write on Ed if you have trouble. Include the output of git ls-files, your group number, and the bundle’s size.

Interview lecture

Here’s the programming puzzle that Prof. Pit-Claudel demonstrated during the lecture:

BST predecessor

You are given the following implementation of a binary search tree:

enum BST[+A]:
  case Empty extends BST[Nothing]
  case Node(v: A, l: BST[A], r: BST[A]) extends BST[A]

  def insert[B >: A](b: B)(using ord: Ordering[B]): BST[B] = this match
    case Empty => Node(b, Empty, Empty)
    case Node(v, l, r) if ord.lt(b, v) => Node(v, l.insert(b), r)
    case Node(v, l, r) if ord.gt(b, v) => Node(v, l, r.insert(b))
    case _ => this

  def contains[B >: A](x: B)(using ord: Ordering[B]): Boolean = this match
    case Empty => false
    case Node(v, l, r) =>
      if ord.equiv(x, v) then true
      else if ord.lt(x, v) then l.contains(x)  // Search in the left subtree
      else r.contains(x)  // Search in the right subtree

1. Write a method tree.sorted to convert a BST into a sorted vector.
2. Specify and implement a method tree.predecessor(threshold) that finds the largest value contained in the tree before threshold.
3. Use property-based testing to check the correctness of the implementation.

Solution

1. There’s nothing to sort since a BST maintains sorted order:

   extension [A](tree: BST[A])
     // Returns the elements of tree in sorted order, assuming that `tree` has the
     // BST property.
     def sorted: Vector[A] = {
       tree match
         case Empty => Vector()
         case Node(v, l, r) =>
           l.sorted ++ Vector(v) ++ r.sorted
     }
   

   2025-12-15/bstPredecessor.worksheet.sc

2. The spec reuses sorted:

   extension [A](tree: BST[A])
     def predecessor_spec(threshold: A)(using ord: Ordering[A]): Option[A] =
       tree.sorted.filter(v => ord.lt(v, threshold)).lastOption
   

   2025-12-15/bstPredecessor.worksheet.sc

   extension [A](tree: BST[A])
     def predecessor(threshold: A)(using ord: Ordering[A]): Option[A] =
       tree match
         case Empty => None
         case Node(v, l, r) =>
           if ord.lt(v, threshold) then
             r.predecessor(threshold).orElse(Some(v))
           else
             l.predecessor(threshold)
   

   2025-12-15/bstPredecessor.worksheet.sc

3. Note the use of sized to play nice with ScalaCheck’s size heuristics:

   import org.scalacheck.Prop.forAll
   import org.scalacheck.{Gen, Arbitrary}
   
   given [T](using Ordering[T])(using g: Arbitrary[T]): Arbitrary[BST[T]] = Arbitrary:
     Gen.sized: sz =>
       Gen.listOfN(sz, g.arbitrary).flatMap: ts =>
         ts.foldLeft(Empty)(_.insert(_))
   
   forAll { (tr: BST[Int], threshold: Int) =>
     tr.predecessor(threshold) == tr.predecessor_spec(threshold)
   }.check()
   

   2025-12-15/bstPredecessor.worksheet.sc

   Note that this requires the following header in the worksheet:

   //> using scala "3.7.2"
   //> using dep "org.scalacheck::scalacheck:1.19.0"
   

© 2023–2025 EPFL. All rights reserved.