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
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
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 ]
>
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
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([])
[]
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
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([])
[]
>
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
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([])
[]
>
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)
[]
>
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(' ')
{}
>
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(' ')
[]
>
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);
}
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.
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
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.