Riemann surface
matlab

Exercise 1 (10 Points). Prove or give a counterexample for each of the following:
(a) If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.
(b) If $A \in B$ and $B \in C$, then $A \in C$.

Sorts: Quicksort, merge sort, heap sort, tree sort
Runtime: $O(n \log n)$
Explanation: Merge sort and heap sort are always $O(n \log n)$. For quicksort, we can easily choose a good pivot for randomly ordered inputs. For tree sort, the resulting tree will be fairly balanced in the average case.

Comments: You needed to use a comparison-based sort because input contains comparable objects. Bubble, insertion, and insertion sort are inefficient compared to the four listed above. Runtime should not include $k$.

Exercise 2 (10 Points). If $a(t), b(t)$, and $c(t)$ are the lengths of the three sides of a triangle $t$ in non-decreasing order (i.e. $a(t) \leq b(t) \leq c(t)$ ), we define the sets:

$X:={$ Triangle $t: a(t)=b(t)}$

$Y:={$ Triangle $t: b(t)=c(t)}$

$T:=$ the set of all triangles
Using only set operations on these three sets, define:
(a) The set of all equilateral triangles (all sides equal)
(b) The set of all isosceles triangles (at least two sides equal)
(c) The set of all scalene triangles (no two sides equal)

Solution:
(a) We require $a(t)=b(t)$ and $b(t)=c(t)$ (this obiviously implies $a(t)=c(t)$ ), so the set is $X \cap Y$
(b) An isoceles triangle $t$ can have

$a(t)=b(t)$, or

$b(t)=c(t)$, or

$a(t)=c(t)$.

Now we have assumed that $a(t), b(t)$, and $c(t)$ are in non-decreasing order, so the last condition holds if and only if both the first two do. So the required set is $X \cup Y$
(c) A scalene triangle has its two smaller sides $a(t)$ and $b(t)$ unequal (set $T \backslash X$ ) and its two larger sides $b(t)$ and $c(t)$ unequal (set $T \backslash Y$ ). Since the sides are listed in the non-decreasing order, either of the above conditions guarantess $a(t) \neq c(t)$. So the required set is $(T \backslash X) \cap(T \backslash Y)$.
An alternative argument is: A triangle is scalene if and only if it is not isosceles. So using the result of the previous part, the set of scalene triangles is $T \backslash(X \cup Y)$. It’s easy to confirm that the answers given by the two arguments are actually the same – this is an instance of a general rule called De Morgan’s Law.

E-mail: help-assignment@gmail.com  微信:shuxuejun

help-assignment™是一个服务全球中国留学生的专业代写公司