Due Date: Jun 20 before midnight.
Max Points: 100
Important Reminder: As per the course Academic Honesty Statement, cheating of any kind will minimally result in your letter grade for the entire course being reduced by one level.
To be turned in via the submission link on brightspace. For
problems 1-12, please submit a file hw1-sol.ts which can
be compiled using:
$ tsc --target es2022 hw1-sol.ts --outFile hw1-sol.js
[The provided tsconfig.json file is set up
so that simply typing tsc in the directory containing hw1-sol.ts
will compile it with the above options. A skeleton
hw1-sol.ts file is also provided.]
For the remaining questions, please submit a PDF file named
hw1-sol.pdf.
Justify all answers.
It may be the case that some questions cannot be answered as requested.
Note that some of the questions require you to show code. You may use a JavaScript implementation to verify your answers.
You are encouraged to use the web or the library but are required to cite any external sources used in your answers.
Many of the questions are meant to familiarize you with the built-in functions available in JavaScript (and many other languages) for arrays and strings.
Notes:
We use C:fn() to refer to C.prototype.fn().
Restrictions
Some of the questions specify "Subject to the above restrictions".
These restrictions are to force you to write code in a strictly
functional style without any
mutation. The
specific restrictions are:
Your code may not make any explicit use of mutation, iteration or recursion.
You code may not contain any let or var declarations.
The answer provided for a specific question may contain only a single top-level function.
What you are allowed to do:
Your code may declare const variables with an initializer.
A function may contain nested functions.
A function provided for a particular answer may call a function defined in an earlier answer.
You may also use the full power of JavaScript regular expressions for functions which manipulate text.
You may use any String, RegExp, Array, Number or Math functions which are used only for their return value and not for any side-effects. So for example, you may use Array:sort() if you are only using its return value and not for the side-effect of changing its argument. You are not allowed to use Array:push() as it is destructive, but you may use Array:concat().
Some hints for writing code subject to the above restrictions:
In the absence of assignment and iteration, the only sequence of
statements you can write are a sequence of zero-or-more const
declarations followed by a return statement, or if-then-else
statements with the bodies of the then and else subject to the
same restrictions. In some cases, if-then-else expressions using
?: may be preferable to if-then-else statements.
Use higher-order Array functions like map() and reduce() to replace the use of iteration.
Note that the functions provided to many of the Array functions
like map() and reduce() take multiple arguments including
the current index of the element being operated on and the array
being operated on.
The Array.from() factory method may be useful for setting up
initial arrays. Specifically, Array.from({length: len}) can be
used for creating an array of length len and
Array.from({length: len}).map((_, i) => i) can be used to set
up an array of indexes in [0, len).
Warning: One of the bad parts of JavaScript is that when
return'ing a value from a function, the expression representing
the returned value must start on the same line as the return
keyword. So
return
expr;
will return undefined, but
return expr;
or
return (
expr
);
will work.
To get an idea of what is expected, look at the Fibonacci function discussed in class.
Subject to the above restrictions, show code for a
function norms_2(pairs: [number, number][]) which when given a
list pairs of 2-element list of numbers, returns a list
containing the
Euclidean norm of each pair. Note that the norm of a pair \([x,
y]\) is \(\sqrt{x^2 +y^2}\).
> norms_2([ [0, 0], [4, 3], [3, 4], [12, 5], [1, 1] ])
[ 0, 5, 5, 13, 1.4142135623730951 ]
> norms_2([])
[]
> norms_2([[-3, 4], [4, -3]])
[ 5, 5 ]
>
Hint: use Math.sqrt(). 4-points
function norms_2(pairs: [[number, number]]) {
const norm = ([x, y]) => Math.sqrt(x**2 + y**2);
return pairs.map(norm);
}
Subject to the above restrictions, show code for a
function max_norms_2(pairs: [number, number][]) which when given
a non-empty list pairs of 2-element lists of numbers, returns a
number giving the maximum norm of all the pairs in the list.
Hint: Use Array::sort(). 4-points
> max_norms_2([ [0, 0], [4, 3], [3, 4], [12, 5],
[1, 1] ])
13
We use norms_2() from the previous question to compute the
norms. We then sort the norms in non-ascending order and
then return the first element of the sorted array.
function max_norms_2(pairs: [number, number][]) {
const norms = norms_2(pairs);
const sortedNorms = norms.sort((a, b) => b - a);
return sortedNorms[0];
}
Subject to the above restrictions, show code for a
function norms_3(triples: [number, number, number][]) which when
given a list triples of 3-element list of numbers, returns a
list containing the
Euclidean
norm of each triple. Note that the norm of a triple \([x, y, z]\)
is \(\sqrt{x^2 +y^2 + z^2}\). 4-points
> norms_3([[2, 1, 2], [2, 3, 6], [4, 7, 4],
[1, 1, 1], ])
[ 3, 7, 9, 1.7320508075688772 ]
>
function norms_3(triples: [[number, number, number]]) {
const norm = ([x, y, z]) => Math.sqrt(x**2 + y**2 + z**2);
return triples.map(norm);
}
Subject to the above restrictions, show code for a
function sum_of_squares(nums: number[]) which when given a list
nums of numbers, returns the sum of the squares of the numbers
in nums. If nums is empty, then it should return
0. 4-points
> sum_of_squares([3, 4])
25
> sum_of_squares([12, 4])
160
> sum_of_squares([1, 2, 3, 4, 5])
55
> sum_of_squares([12])
144
> sum_of_squares([])
0
function sum_of_squares(nums: number[]) {
return nums.reduce((acc, e) => acc + e*e, 0);
}
Subject to the above restrictions, show code for a
function norms(tuples: number[][]) which when given a list
tuples of number tuples (represented as lists), returns a list
containing the
Euclidean norm of each contained tuple. Note that the norm of a
tuple \([a_1, a_2, \ldots, a_n]\) is \(\sqrt{a_1^2 +a_2^2 + \ldots
+ a_n^2}\). The norm of the empty tuple is defined to be
0. 4-points
norms([[ 3, 4], [12, 5], [2, 3, 6], [4, 4, 7],
[36, 3, 8], [1, 1, 1], [1, 1, 1, 1]])
[ 5, 13, 7, 9, 37, 1.7320508075688772, 2 ]
> norms([[], [1, 1, 1, 1]])
[ 0, 2 ]
>
> norms([])
[]
function norms(tuples: number[][]) {
const norm = tuple => Math.sqrt(sum_of_squares(tuple));
return tuples.map(norm);
}
Subject to the above restrictions, show code for a
function max_norms(tuples: number[][]) which when given a non-empty list
tuples of lists of numbers, returns a number giving the maximum
norm of all the tuples in the list.
max_norms() must run in time linear in the size of the list
(note that sorting is not a linear-time operation).
4-points
> max_norms([[ 3, 4], [12, 5], [2, 3, 6], [4, 4, 7],
[36, 3, 8], [1, 1, 1], [1, 1, 1, 1]])
37
> max_norms([[], [1, 1, 1, 1]])
2
function max_norms(tuples: number[][]) {
const nums = norms(tuples);
return nums.reduce((acc, e) => acc > e ? acc : e);
}
Subject to the above restrictions, show code for a
function sum_partials(nums: number[]) which when given a list
nums of numbers, returns the list containing the sums of the
prefixes of nums.
The performance must be linear in the size of
nums. 4-points
> sum_partials([1, 2, 3, 4])
[ 1, 3, 6, 10 ]
> sum_partials([22, -3, 4, -5, 6 ])
[ 22, 19, 23, 18, 24 ]
> sum_partials([22])
[ 22 ]
> sum_partials([])
[]
>
function sum_partials(nums: number[]) {
return (
(nums.length === 0)
? []
: nums.slice(1).reduce((acc, e) => acc.concat(acc.slice(-1)[0] + e),
[nums[0]])
);
}
Given a series of \(n\) numbers \(a_0, a_1, \ldots a_{n-1}\), the alternating sum of the series is a sum where the terms alternate in sign.
\[ \sum_{i=0}^{n-1} -1^ia_i = a_0 -a_1 + a_2 - \ldots + -1^{n-1}a_{n-1} \] Subject to the above restrictions, show code for a
function alt_sum(nums: number[]) which when given a list nums
of numbers, returns the alternating sum of the numbers. The
result should be 0 when nums is empty. 4-points
> alt_sum([1, 2, 3, 4, 5])
3
> alt_sum([3, 3, 3, 3])
0
> alt_sum([3, 3, 3, 3, 3])
3
> alt_sum([1, -1, 1, -1])
4
> alt_sum([])
0
function alt_sum(nums: number[]) {
return nums.reduce((acc, e, i) => acc + e * (-1)**i, 0);
}
Subject to the above restrictions, show code for a
function alt_sum_partials(nums: number[]) which when given a
list nums of numbers, returns the list containing the partial
alternating sum of the prefixes of nums.
The performance must be linear in the size of
nums. 4-points
> alt_sum_partials([1, 2, 3, 4, 5, 6, 7, 8])
[
1, -1, 2, -2,
3, -3, 4, -4
]
> alt_sum_partials([23, 3, 19, 5, 4])
[ 23, 20, 39, 34, 38 ]
> alt_sum_partials([23,])
[ 23 ]
> alt_sum_partials([])
[]
>
function alt_sum_partials(nums: number[]) {
const s = (acc: number[], e: number, i: number) =>
acc.concat(acc.slice(-1)[0] + e*(-1)**(i + 1));
return (
(nums.length === 0)
? []
: nums.slice(1).reduce(s, [nums[0]])
);
}
Subject to the above restrictions, show code for a
function short_words(text: string, n: number) which when given a
string text returns a list of all the words in text having
length less than n. A word is defined (for this and
subsequent questions) to be a maximal sequence of non-whitespace
characters.
Hint: String:split() may be useful. 4-points
> short_words('We hold these truths to be self evident',
4)
[ 'We', 'to', 'be' ]
> short_words('We hold these truths to be self evident',
5)
[ 'We', 'hold', 'to', 'be', 'self' ]
> short_words(' ', 5)
[]
>
function short_words(text: string, n: number) {
return text.split(/\s+/).
filter(w => 0 < w.length && w.length < n);
}
Subject to the above restrictions, show code for a
function word_lengths(text: string) which when given a string
text returns an object mapping the words in text to their
length. Words which differ in case are considered equivalent.
The keys in the return value should be all lower-case and should
be sorted in lexicographic ascending order.
Hint: Object.fromEntries() may be useful. 5-points
> word_lengths(' Hello WORLD!!! ')
{ hello: 5, 'world!!!': 8 }
> word_lengths(` Twas brillig and the slithy toves
... Did gyre and gimble in the wabe:
... `)
{
and: 3,
brillig: 7,
did: 3,
gimble: 6,
gyre: 4,
in: 2,
slithy: 6,
the: 3,
toves: 5,
twas: 4,
'wabe:': 5
}
> word_lengths(' ')
{}
>
function word_lengths(text: string) {
const pairs = text.split(/\s+/).
filter(w => w.length > 0).
map(w => w.toLowerCase()).
sort().
map(w => [w, w.length]);
return Object.fromEntries(pairs);
}
Subject to the above restrictions, show code for a
function palindrome_words(text: string) which when given a
string text returns a list of words in text which are
palindromes. A word is a palindrome if the word spelled backwards
is the same as the word, ignoring case.
Hint: Use Array:reverse(). 5-points
> palindrome_words(' Hello Madam your mom and kayak
are on the racecar')
[ 'Madam', 'mom', 'kayak', 'racecar' ]
> palindrome_words(' The door went tattarattat
promptly at noon')o
[ 'tattarattat', 'noon' ]
> palindrome_words(' ')
[]
>
function palindrome_words(text: string) {
const reverse = (w: string) => w.split('').reverse().join('');
const is_palindrome =
(w: string) => reverse(w.toLowerCase()) === w.toLowerCase();
return text.split(/\s+/).
filter(w => w.length > 0 && is_palindrome(w));
}
Fix type errors in the following independent TypeScript code fragments: 15-points
Fix the error in the code below without changing any types:
type Result<T> =
{ok: true, val: T} |
{ok: false, err: string};
function applyFn(result: Result<number>,
fn: (v: number) => string)
: Result<string>
{
return {ok: true, val: fn(result.val) }
}
Fix the type error in the following function by only making a type change but do not change the return type:
/** return string corresponding to bit (which must be 0 or 1) */
function bitToString(bit: number) : string {
console.assert(bit === 0 || bit === 1);
switch (bit) {
case 0: return 'zero';
case 1: return 'one';
}
}
Fix the errors in the code below by changing the type
Val to a more precise declaration:
type Val = {isNum: boolean, value: string|number};
function twiceVal(val: Val) : string|number {
return val.isNum ? val.value*2 : val.value.repeat(2);
}
The answers follow:
Verify that result.ok === true before attempting to
access result.val.
type Result<T> =
{ok: true, val: T} |
{ok: false, err: string};
function applyFn(result: Result<number>,
fn: (v: number) => string)
: Result<string>
{
if (!result.ok) return result;
return {ok: true, val: fn(result.val) }
}
Make the type of the parameter more precise:
/** return string corresponding to bit. */
function bitToString(bit: 0|1) : string {
console.assert(bit === 0 || bit === 1);
switch (bit) {
case 0: return 'zero';
case 1: return 'one';
}
}
Make the type Val more precise:
type Val =
{isNum: true, value: number} |
{isNum: false, value: string};
function twiceVal(val: Val) : string|number {
return val.isNum ? val.value*2 : val.value.repeat(2);
}
Given a vocabulary \(\Sigma\) containing 2 symbols 0 and 1,
give regex's for the following: 10-points
All non-empty strings over \(\Sigma\) which have length less than 10.
All strings over \(\Sigma\) which have length less than 20 and
end with a 1.
All strings of length 4 over \(\Sigma\) which are palindromes.
All non-empty strings over \(\Sigma\) which are palindromes.
All non-empty strings over \(\Sigma\) which are even, when interpreted as a binary number.
The answers follow:
/[01]{1,9}/.
/[01]{0,18}1/.
/0000|1111|1001|0110/.
Cannot be done because regex's cannot retains the arbitary amount of state which is needed to recognize palindromes of arbitrary length.
/[01]*0/.
Note that these are abstract regex's. If actually running within
JavaScript, you would need to use the ^ and $ anchors.
An advantage of the AST representation chosen for Project 1 is that copying a formula from one cell to another can simply copy over the AST unchanged, since relative cell references are maintained as relative indexes. However, this will break if a spreadsheet allows deletion or insertion of rows and columns. How would you change the representation so as to allow deletion or insertion of rows and columns.
Hint: All problems in computer science can be solved by another level of indirection (the fundamental theorem of software engineering). 10-points
The problem with insertion and deletion of rows and columns is
that formulas which refer to other cells would need to change.
For example, if cell d3 has a relative reference to cell b3
with relative indexes [-2, 0], but then a column is inserted after
column c, then what was d3 will become e3 and the relative
reference would need to change to [-3, 0].
One solution to the problem is to provide an immutable ID to each
row and column which does not change during the lifetime of that
row or column. This ID can be anything; in the preceeding example
we could associate the original column b with some indirection
ID x12az and row 3 with indirection ID z3x4. Then the
relative reference [-2, 0] would change to an indirect reference
[x12az, z3x4]. This reference would not change even after
rows/columns are inserted or deleted.
We would need data structures mapping between these indirection ID's and regular row/column ID's. These data structures would need to be manipulated as rows and columns are inserted or deleted. Using a separate array for mapping regular row/column ID's to indirection ID's makes it possible to,
Map a regular ID to an indirection ID in constant time.
Map an indirection ID to a regular ID in time proportional to the number of rows or columns.
Handle row/column insertion/deletion in time proportional to the number of rows or columns.
This assumes that arrays are implemented as a contiguous block of memory; that may not be the case in JavaScript where arrays may be implemented as hash tables.
In order to continue having the advantage of easy copying of formulas, formulas with relative references would still be used when copying but those formulas can be synthesized on the fly as needed from the formulas which contain the indirect references.
Discuss the validity of the following statements.15-points
The for-of loop can be used for iterating over
both arrays and objects.
The for-in loop can used for iterating over both
arrays and objects.
If a JavaScript data value has been assigned to x, then
the expression x === x must be true.
The expression a?.b.c || d should be flagged as
suspicious during a code review.
The length of an array is one greater than the largest index of its contained elements.
The answers follow:
The for-of loop can only be used for iterating over
iterables but a JavaScript object is not an iterable.
Hence the statement is false.
A for-in loop can be used to iterate over the properties
of an Object. Since an array is an Object a for-in
loop can be used to iterate over an array. Hence the statement
is true.
Though a for-in loop can be used to iterate over the
properties (including the indexes) of an array, a for-of
loop is usually preferred. The problems with using for-in
for iterating over the indexes of an array include:
The indexes may not be enumerated in order.
The iteration may include non-index properties of the array object, including inherited properties.
JavaScript data values include NaN, but NaN === NaN is
always false. Hence the statement is false because
of this specific situation.
Given the expression a?.b.c || d, it is clear that the
programmer is handling a being nullish, but not for the
other properties. An expression making it clear that all
nullish checks are being done would be a?.b?.c ?? d.
It is possible that there is some kind of
program invariant which states that if a is non-nullish,
then a.b and a.b.c will both be non-nullish. But even
in that case, an expression like a?.b.c ?? d may be more
appropriate.
So the statement is definitely suspicious enough to merit flagging during a code review and the statement is true.
The length of an array is 1 greater than the largest index which was ever assigned which does not change even when the element at the largest index is deleted.
as = [] [] > as[10] = 42 42 > as.size undefined > as.length 11 > delete as[10] true > as[10] undefined > as.length 11 //still 11.
So the length is not 1 greater than that of the maximum index of its currently contained elements, but is 1 greater than the largest index ever contained. Hence the statement is false.