2022 CS-210 Midterm

def gray(n: Int): List[String] =
  require(n >= 0)
  if (n == 0) then List("")
  else
    val sub = gray(n - 1)
    val left = sub.map(x => "0" + x)
    val right = sub.reverse.map(x => "1" + x)
    left ::: right

gray(3)

2022-midterm-gray-solution.worksheet.sc

import scala.math.sqrt

// A point in 2D space
case class Point(x: Double, y: Double):
  // Euclidean distance between this and another point
  def distance(p: Point): Double =
    val dx = x - p.x
    val dy = y - p.y
    sqrt(dx * dx + dy * dy)

// A point with a label
case class LabeledPoint(point: Point, label: String)

// Computes the distance of a point p to each point in the list pts
def distances(pts: List[LabeledPoint], p: Point): List[(LabeledPoint, Double)] =
  pts.map(q => (q, p.distance(q.point)))

// --------------------------------------------------------
// Questions
// --------------------------------------------------------

// Retrieves the k nearest training points for a given point p
def kNearest(pts: List[LabeledPoint], p: Point, k: Int): List[LabeledPoint] =
  distances(pts, p).sortBy(_._2).take(k).map(_._1)

// Given a list of labeled points pts, counts the number of times each label appears
def countLabels(pts: List[LabeledPoint]): Map[String, Int] =
  pts.map(_.label).groupBy(identity).map((k, v) => (k, v.size))

// Given the label count as a Map[String, Int], returns the label with the highest count
def getMaxLabel(labelCount: Map[String, Int]): String =
  labelCount.foldLeft(("", 0))((acc, x) => if x._2 > acc._2 then x else acc)._1
  // Or just labelCount.maxBy(_._2)._1

// Given a list of labeled points, returns the majority label
def majorityLabel(pts: List[LabeledPoint]): String =
  getMaxLabel(countLabels(pts))

// k-NN function that labels a list of test points using the k nearest neighbors in the training set
def knn(
    train: List[LabeledPoint],
    test: List[Point],
    k: Int
): List[LabeledPoint] =
  test.map(p => LabeledPoint(p, majorityLabel(kNearest(train, p, k))))

// --------------------------------------------------------
// Tests
// --------------------------------------------------------

// A set of labeled points
val train = List(
  LabeledPoint(Point(1.0, 1.0), "A"),
  LabeledPoint(Point(2.0, 0.5), "A"),
  LabeledPoint(Point(1.0, 2.0), "B"),
  LabeledPoint(Point(1.5, 2.0), "B"),
  LabeledPoint(Point(3.0, 1.0), "C"),
  LabeledPoint(Point(2.5, 1.5), "C")
)

val test = List(Point(1.5, 1.5), Point(1.5, 1.0), Point(3.0, 2.0))

knn(train, test, 3)

2022-midterm-knn-solution.worksheet.sc