ICS $311$: Algorithms Spring $2024$

Problem Set $1$

Prof. Nodari Sitchinava Due: Friday, January $12,2023$ at $4$pm

You may discuss the problems with your classmates, however you must write up the solutions on your

own and list the names of every person with whom you discussed each problem.

Start every problem on a separate page, with the exception that Problems $2$ can start on the same page

as Problem $1($Peer credit assignment$).$

$1$ Peer Credit Assignment $(1$ point extra credit for replying$)$

Please list the names of the other members of your peer group for this week and the number of extra credit

points you think they deserve for their participation in group work.

$$ You have a total of $60$ points to allocate across all of your peers.

$$ You can distribute the points equally, give them all to one person, or do something in between.

$$ You need not allocate all the points available to you.

$$ You cannot allocate any points to yourself $!$ Points allocated to yourself will not be recorded.

$2$ Catenable Stack $(30$ pts$)$

In this problem you will design a data structure that implements Stack ADT using singly$-$linked list instead

of an array. In addition your stack will have the following additional operation:

public catenate$($Stack s$)$; $//$ appends the contents of Stack s to the current stack

The new operation will have the following properties:

Let n $=$ s$1.$size$(),$ m $=$ s$2.$size$().$ Then executing s$1.$catenate$($s$2)$ results in the following:

$1.$ The new size of s$1$ is the sum of the size of s$2$ and the original size of s$1,$ i$.$e$.,$ the following evaluates

to true: s$1.$size$()==$ n $+$ m

$2.$ Top n elements of s$1$ after the call s$1.$catenate$($s$2)$ are the same as the elements of s$1$ before the call.

The bottom m elements of s$1$ after the call s$1.$catenate$($s$2)$ are the same as the elements of s$2$ before

the call.

$($a$)$ The implementation described in the book, lecture notes and screencasts uses an array to implement

Stack ADT. Can you implement catenate$($Stack s$)$ operation that runs in O$(1)$ time for such imple$-$

mentation? If yes, write down the algorithm that achieves that and demonstrate that it runs in O$(1)$

time. If not, describe what goes wrong.

$($b$)$ Write down algorithms that implement the original Stack ADT using a singly$-$linked list instead of

the array. That is$,$ write down pseudocode for implementing each operation of Stack ADT: Stack$(),$

push$($Object o$),$ pop$(),$ size$(),$ isEmpty$(),$ top$().$ Make sure that each of the above opera$-$

tions takes at most O$(1)$ time in your implementation.

$($c$)$ Design an algorithm that implements catenate$($Stack s$)$ operation in O$(1)$ time. Write down the

algorithm and demonstrate that it runs in O$(1)$ time.

$1$

$3$ Relative Growth Rates of Functions $(30$ pts$)$

Continuing in the style of in$-$class exercises, ll in the table for these pairs of functions with Yes" or No$"$ in

each empty box. Then for each row, justify your choice, preferably by showing mathematical relationships

$($e$.$g$.,$ transforming one expression into another, or into expressions that are more easily compared$).$

f $($n$)$ g$($n$)$ O$?$ o$?\backslash$Omega $?\backslash$omega $?\backslash$Theta $?$

e$.2$log n log$2$ n

f$.$n ncos n

g$.8$n$24$log n

$4$ Fun with Induction $(40$ pts$)$

Prove the following statements using strong induction:

$($a$)(20$ pts$)$ n$$

i$=0$

ri $=1$rn$+1$

$1$r for every non$-$negative integer n and every real number r $6=1.$

$($b$)(20$ pts$)$ Suppose that a store oers gift certicates in denominations of $$3$ and $$5.$ Then any item

priced at an integer number of dollars of value at least $$8$ can be paid for with these gift certicates

without a need to use any other form of currency. For example, an item priced $$16$ can be paid with

two $$3$ gift certicates and two $$5$ gift certicates.

$2$

$5$ Fun with Logarithms $($OPTIONAL $-0$ pts$)$

$($a$)$ Prove the following identity:

n $1$

log n $=2$

$($b$)$ Simplify the following expressions. Show your work.

$$ nlog$39$

$$ nlog $8$

$$ n$(1/$ log$3$ n$)$

$$ n$/(3$log$9$ n$)$

$($c$)$ Order the expressions in part $($b$)$ according to their asymptotic growth, from the lowest to the highest.

Justify your answers.

$6$ Tiling with L$-$shaped Tiles $($OPTIONAL $-0$ pts$)$

A construction company is given a contract to tile bathrooms in a new apartment building in Kakaako.

However, because of the customer's demands, the company is a bit stumped and hired you as a consultant

to help them out.

The oor of every bathroom to be tiled is square$-$shaped, but bathrooms in dierent apartments are of

dierent sizes. All you know is that each bathroom is of size $2$n $\backslash$times $2$n inches for various integers n$.$ For

example, one bathroom might be of size $256\backslash$times $256$ inches, another one might be $128\backslash$times $128$ inches, and so on$.$

The whole bathroom oor must be tiled, except for a square$-$shaped drain on the oor of size $1\backslash$times $1$ inches.

However, due to the unique design of the apartments, dierent bathrooms have the drain in dierent loca$-$

tions on the oor: some have them in a corner, others in the center, yet others a few inches away from the

wall. All you know is that in each case, the drain will be some integer inches away from the walls. Moreover,

the construction company must tile the oor using special tiles. Ea