Comp 110 Set Utilities

In this problem set you will implement a series of utility functions for working with Lists of values as if they were mathematical Sets.

Learning Objectives

After completing this problem set, you should:

  1. Understand common Set theory concepts: 
    1. subset
    2. superset
    3. strict subset
    4. equality
    5. union
    6. intersection
    7. subtraction
  2. Be able to write recursive functions that process two lists
  3. Be able to write generic functions that work for parameters of any type

Part 0. Starting the Dev Environment

As with in lecture, begin by opening up VSCode, ensuring your project is still open, and then running the following two commands in the VSCode Integrated Terminal:

  1. npm run pull
  2. npm start

The first command "pulls" the latest files needed for COMP110 into your repo, if any. The second command starts the development environment and will open your web browser to the local server. 

Part 1. Setting up an App

In the same directory used in lecture:

  1. Right click on the "src" folder
  2. Select "New Folder"
  3. Name the new folder: ps03-set-utils
    1. Note: capitalization and punctuation are important!
  4. Right click on the folder you just created
  5. Select "New File"
  6. Name the new file: set-utils-app.ts
    1. Note: capitalization and punctuation are important!

Part 2. Starting your Code

2.0 Honor Code Header

All problem sets begin with an Honor Code pledge. Notice this header is contained within block comment tags discussed in Lecture 1. You can copy paste the pledge below and fill in your name and ONYEN.

/**
 * Author:
 *
 * ONYEN:
 *
 * UNC Honor Pledge: I certify that no unauthorized assistance has been received
 * or given in the completion of this work. I certify that I understand and
 * could now rewrite on my own, without assistance from course staff,
 * the problem set code I am submitting.
 */

2.1 Imports

The next step after ensuring the honor code header is to import the functions we'll use from the introcs library (i.e. printimage, and so on) and its List library. The first line of code to add to your app is the following:

import { print, csvToList } from "introcs";
import { List, cons, first, rest, listify } from "introcs/list";

2.2 The main Function

Add a main function to your program and call it from the outside so that you can add test cases for each of the utility functions needed below.

In order to receive help in office hours on any given function below, you must have test cases demonstrating the function being called and its output in your code. If you do not have a test case for a question you come to office hours with, the UTAs will help you come up with test cases in one session but are prohibited from talking about implementation specifics until the next session.

Helper Function

1.1 includes - Declare and export a generic function named includes. Given a List of any type T, and a value of type T, return true when the List contains the value and false when it does not. 

Test by calling this function from the main function and printing its results. Here are a few example test cases:

let numbers: List<number> = listify(1, 2, 3);
print(includes(numbers, 2)); // true
let letters: List<string> = listify("a", "b", "c");
print(includes(letters, "d")); // false

Set Properties

Khan Introduction to subset, superset, and strict subset

2.1 isSet - Declare and export a generic function named isSet. Given a List of any type T, return true when the List is a Set, false otherwise. A Set is either:

  1. empty, or,
  2. a List of values where no value is repeated

Test your implementation by calling this function from the main function and printing its results:

print(isSet(null)); // true, because a set can be empty
print(isSet(listify("a", "b"))); // true, because there are no duplicates
print(isSet(listify(1, 2))); // true, because there are no duplicates
print(isSet(listify("a", "b", "a"))); // false, because "a" appears twice
print(isSet(listify(2, 2, 3))); // false, because 2 appears twice

Hint #1: Consider making use of your includes function.

Hint #2: Considering only the first element of a List, how can you tell if it appears again in the List?

2.2 isSubset - Declare and export a generic function named isSubset. Given two lists of type T, named a and b, return true when a is a subset of b, false otherwise. Note: this is not testing for a strict subset. The set a will be a subset of b if and only if:

  1. a is the empty Set
  2. every element in a is also an element of b

Test your implementation by calling this function from the main function and printing its results:

let x: List<number> = listify(1, 2, 3);
let y: List<number> = listify(2, 3, 4);
let z: List<number> = listify(0, 3, 2, 1, 4);
print(isSubset(x, y)); // false, because y does not contain 1
print(isSubset(z, x)); // false, because x does not contain 0 or 4
print(isSubset(x, null)); // false, empty set does not contain 1, 2, or 3
print(isSubset(null, null)); // true
print(isSubset(null, x)); // true
print(isSubset(x, x)); // true
print(isSubset(x, z)); // true

2.3 isSuperset - Declare and export a generic function named isSuperset. Given two lists of type T, named a and b, return true when a is a superset of bfalse otherwise. The set a will be a superset of b if and only if:

  1. b is the empty Set
  2. every element in b is also an element of a

Test your implementation by calling this function from the main function and printing its results:

let x: List<number> = listify(1, 2, 3);
let y: List<number> = listify(2, 3, 4);
let z: List<number> = listify(0, 3, 2, 1, 4);
print(isSuperset(y, x)); // false, because y does not contain 1
print(isSuperset(x, z)); // false, because x does not contain 0 or 4
print(isSuperset(null, x)); // false, empty set does not contain 1, 2, or 3
print(isSuperset(null, null)); // true
print(isSuperset(x, null)); // true
print(isSuperset(x, x)); // true
print(isSuperset(z, x)); // true

Hint: In set theory, when a is a superset of b, it follows b is a subset of a. How can you make use of the isSubset function you've already written to implement isSuperset?

2.4 isStrictSubset - Declare and export a generic function named isStrictSubset. Given two lists of type T, named a and b, return true when a is a strict subset of bfalse otherwise. The set a will be a strict subset of b if and only if:

  1. a is the empty Set and b is not
  2. every element in a is also an element of bbut not vice-versa

Test your implementation by calling this function from the main function and printing its results:

let x: List<number> = listify(1, 2, 3);
let y: List<number> = listify(2, 3, 4);
let z: List<number> = listify(0, 3, 2, 1, 4);
print(isStrictSubset(null, null)); // false
print(isStrictSubset(x, x)); // false
print(isStrictSubset(null, x)); // true
print(isStrictSubset(x, z)); // true
print(isStrictSubset(y, z)); // true

Hint: In set theory, when a is a strict subset of b, it follows a is a subset of b, but is not a subset of a. How can you make use of the isSubset function you've already written to implement isStrictSubset?

2.5 isSetEqual - Declare and export a generic function named isSetEqual. Given two lists of type T, named a and b, return true when a is equal to set bfalse otherwise. The set a will be equal to b iff:

  1. both are empty
  2. both sets contain exactly the same elements

Test your implementation by calling this function from the main function and printing its results:

let x: List<number> = listify(1, 2, 3);
let xx: List<number> = listify(2, 3, 1);
let y: List<number> = listify(2, 3, 4);
print(isSetEqual(x, null)); // false
print(isSetEqual(x, y)); // false
print(isSetEqual(null, null)); // true
print(isSetEqual(x, x)); // true
print(isSetEqual(x, xx)); // true, note: order of set elements!

Hint: There are clever ways to test whether two sets are equal using function(s) you've already written.

Set Operations

Khan introduction to union and intersection.

3.1 union - Declare and export a generic function named union. Given two lists of type T, named a and b, return a new list of type T that contains all of the elements in set a and in set b, with no duplicates.

Test your implementation by calling this function from the main function and printing its results:

let x: List<number> = listify(3, 1, 2);
let y: List<number> = listify(2, 3, 4);
print(union(x, y)); // A set with 1, 2, 3, 4 (in any order)

3.2 intersect - Declare and export a generic function named intersect. Given two lists of type T, named a and b, return a new list of type T that contains only the elements of set a that are also elements of set b.

Test your implementation by calling this function from the main function and printing its results:

let x: List<number> = listify(3, 1, 2);
let y: List<number> = listify(2, 3, 4);
print(intersect(x, y)); // A set with 2, 3 (in any order)

3.3 subtract - Declare and export a generic function named subtract. Given two lists of type T, named a and b, return a new list of type T that contains only the elements of set a that are are not elements of set b. ("Subtract b from a.")

Test your implementation by calling this function from the main function and printing its results:

let x: List<string> = listify("c", "a", "b");
let y: List<string> = listify("b", "c", "d");
let w: List<string> = listify("a");
print(subtract(x, y)); // A set with "a" as the only value
print(subtract(y, x)); // A set with "d" as the only value
print(subtract(x, w)); // A set with "b", "c" (in any order)
print(subtract(w, x)); // empty set