$0.$ Describe and analyze an efficient algorithm that determines, given a legal

arrangement of standard pieces on a standard chess board, which player will

win at chess from the given starting position if both players play perfectly.

$[$Hint: There is a trivial one$-$line solution!$]$

n$1.($a$)$ Identify $($or write$)$ a song that requires $($n$3)$ time to sing the first n verses.

$($b$)$ Identify $($or write$)$ a song that requires $($n log n$)$ time to sing the first n verses.

$($c$)$ Identify $($or write$)$ a song that requires some other weird amount of

time to sing the first n verses.