Question $2(6$ marks$)$

Consider the following red$-$black tree containing keys $10,23,31,37,41,50,62,65,70,$

$89,$ and $95$ :

Draw the red$-$black tree that results from inserting a node with key $15$ into this tree. Show

the steps followed, i$.$e$.,$ draw the intermediary trees. Question $3(20$ marks$)$

A non$-$profit organization provides addiction recovery programs for troubled youth and

maintains information about its programs using a paper$-$based strategy. The charity is

growing rapidly and you were hired to help it move to a more efficient information

management system.

Your first task is to design a data structure that can be used to implement a data storage

solution for the new information system.

Your data structure design should allow the system to store, for each program,

information organized as a record with components $(i,n,d,c,s,o,e,r)$ where $i$ is an

integer identifying the program $($no $2$ programs can have the same identifier$),n$ is a string,

the name of the program, $d$ is a string, a description of the program, $c$ is an integer, the

weekly cost of the program, $s$ is an integer, the size of the program, i$.$e$.,$ the maximum

number of spots in the program, o is an integer, the current occupancy, i$.$e$.,$ the number

of spots currently taken by clients, e is a string, the eligibility conditions for being accepted

to the program, and $r$ is an integer, the rating of the program, a number from $1$ to $5.$

Your design can be based on any of the data structures discussed in class: you can

augment them, combine them, etc. Your data structure must support implementations of the following operations:

SEARCH$\_$l$($i$),$ searches for the program with id i$,$ and returns the record associated

with it$,$ if the program is in the data structure

SEARCH$\_$N$($n$),$ searches for the program with name n$,$ and returns the record

associated with it$,$ if the program is in the data structure

INSERT$($i$,$ n$,$ d$,$ c$,$ s$,$ o$,$ e$,$ r$),$ inserts a new record into the data structure

DELETE$($i$),$ deletes from the data structure the record corresponding to the

program with identifier $i,$ if the program is in the data structure

AVAILABLEPROGRAMS$(),$ returns the records of the programs with available

spots.

PRINT$\_$DS$(),$ prints the content of the data structure

Provide a Java implementation of your data structure as a class with methods that

implement the operations described above.

Include in your submission test data that can be used to create an instance of your class,

insert $5$ programs into this instance, delete a program and print the content of the data

structure. Question $1(14$ marks$)$ Let $G=(V,E)$ be a connected, undirected graph.

a$)[7$ marks$]$ Assume that $T1=(V,E1),T2=(V,E2)$ and $T3=(V,E3)$ are spanning

trees of $G$ and that their sets of edges meet the following conditions: $E1E2=\frac{O}{?},$

$E1E3=\frac{O}{?}$ and $E2E3=\frac{O}{?}.(\frac{O}{?}$ represents the empty set.$)$

What is the smallest number of vertices that G can have? Explain your answer

and provide an example of such a graph. Clearly describe the $3$ spanning trees in

the example you provide.

b$)[7$ marks$]$ Let $G=(V,E)$ be a graph. Provide an algorithmic strategy that can find

and output exactly two spanning trees of $G$ that do not share any edges, e$.$g$.,$

$T1=(V,E1),T2=(V,E2)$ where $T1$ and $T2$ are spanning trees of $G$ and $E1E2$

$=\frac{O}{?},$ if such two spanning trees exist.

Provide your algorithmic strategy using pseudo code or a detailed description in

natural language. Explain why your algorithmic strategy meets the requirement.