$(6$ points$)$ Binary data can represent different type of information, the purpose of this

question is to help you clarify the difference between different representation of information.

For this question, explain what does the hexadecimal value $93($i$.$e$.{93}_{16})$ represent in each

case:

$($a$)(2$ points$)$ The decimal value if it is an unsigned number.

$($b$)(2$ points$)$ The decimal value if it is a signed number given in $2\text{'}$s complement repre$-$

sentation

$($c$)(2$ points$)$ An ASCII character. Hint: you need to consult the extended ASCII ta$-$

ble which require searching the internet for such table, make sure to give appropriate

reference on the table used $($i$.$e$.$ website link$)$ and a copy of it with your submission

Assignment # $1$

Due Oct $3^{rd},2024$

Upload your solution on Moodle

Q$1.[5$ pts$]$ Consider the problem of adding two n$-$bit binary integers, stored in two n$-$element

arrays A and $B.$ The sum of the two integers should be stored in binary form in an $(n+1)$

element array C$.$ State the problem formally and write an algorithm for adding the two

integers.

Calclulate the time complexity of your algorithm

Q$2.[10$ pts$]$ Write an algorithm that reverses an array in place. Define a loop

invariant for your algorithm and prove its correctness using the steps of initialization,

maintenance, and termination.

What is the time complexity of your algorithm?

Q$3[5$pts$]$ Write a recursive algorithm that takes a string as input and returns the

reversed string.

Calculate the time complexity of your algorithm

Q$4[5$ pts$]$ For each of the following recurrences, give an expression for the runtime $T(n)$ if

the recurrence can be solved with the Master Theorem. Otherwise, indicate that the Master

Theorem does not apply.

$T(n)=3T(\frac{n}{2})+n^2$

$T(n)=4T(\frac{n}{2})+n^2$

$T(n)=T(\frac{n}{2})+2^n$

$T(n)=2nT(\frac{n}{2})+n^n$

$T(n)=16T(\frac{n}{4})+n$