# UNIVERSITY OF TEXAS AT DALLAS DEPARTMENT OF COMPUTER SCIENCE Exam 3 Instructor: Daniel Uribe Student Name: May 4, 2021 1 LINEAR HOMOGENEOUS RECURRENCE RELATIONS (20 POINTS) Solve these recurrence...

UNIVERSITY OF TEXAS AT DALLAS
DEPARTMENT OF COMPUTER SCIENCE
Exam 3
Instructor: Daniel Uribe
Student Name:
May 4, 2021
1 LINEAR HOMOGENEOUS RECURRENCE RELATIONS (20 POINTS)
Solve these recurrence relations together with the initial conditions given. Recall that the solu-
tion to a second order recurrence relation
an = c1an−1 + c2an−2
will be of the form
f (n) =α1r n1 +α2r n2 .
Where r1,r2 are roots to the characteristic equation of an and
α1 = k1 −k0r2
r1 − r2
,
α2 = k0r1 −k1
r1 − r2
with k0 = a0 and k1 = a1. Or if the roots are repeated, it will be of the form
f (n) =α1r n +α2nr n .
where α1 = a0.
1. (10 pts) Find the solution for an = 8an−1 −16an−2 for n ≥ 2 and a0 = 1, a1 = 2.
2. (10 pts) Find the solution for an = 8an−1 −16an−2 for n ≥ 2 and a0 = 5, a1 = 7. Note: This
differs from the previous problem only by its initial conditions.
1
1. (10 pts) Use the definition of an r -permutation, or the product rule to determine the
number of trifectas possible in a race with 9 horses. A trifecta is the correct ordering of
the first three horses to finish the race, i.e. an individual correctly picks the winner of
the race, the second place finisher (place), and the third place finisher (show). The result
may be left in product notation, i.e. a1 ·a2 · · · .
2. (10 pts) In a deck with 52 cards, what are the chances that five cards selected randomly
from the deck (or straight from the top of a shuffled deck) will yield a 2-6 straight flush
of hearts. That is, what is the probability that one of the first five cards dealt will be a 2
of hearts and that one of the first five cards dealt will be a 3 of hearts and XXXXXXXXXXAgain, the
result may be left in product notation.
2
3 RELATIONS (20 POINTS)
WizardId WizardName UsesWand IsDark
1001 Gandalf 0 0
1002 Saruman 0 1
1003 Hermione 1 0
1004 Albus 1 0
1005 Gellert 1 1
1006 Tom 1 1
1. (10 pts) Use the Wizards table defined above to list the tuples in the following SELECT
statement.
SELECT WizardId, WizardName
FROM Wizards
WHERE IsDark = 1
2. (10 pts) Use the Wizards table defined above to list the tuples in the following SELECT
statement.
SELECT WizardId, WizardName
FROM Wizards
WHERE IsDark = 0
AND UsesWand = 1
3
4 GRAPHS (20 POINTS)
1. (20 pts) Give the adjacency matrix for the following graph.
A
B C
D
E
F G
H
6
8
6
4
6
6
3
1
6
6
5
6
6
Use this matrix as a template for your solution.

A B C D E F G H
A
B
C
D
E
F
G
H

.
4
5 TREES (20 POINTS)
html
meta title div script
1. (10 pts) Use the tree defined above to give the subtree rooted at body.
2. (10 pts) Use the tree defined above to give the subtree rooted at head.
5
6 BONUS: CODING & PRIME NUMBERS (5 POINTS)
Use https://rextester.com to implement the sieve of Eratosthenes. Write a function which
accepts a positive integer n >= 2. When invoked the function should print all prime numbers
less than or equal to the input parameter n.
Attach the file separately with the appropriate file extension to indicate the language (e.g. sieve.js).
6
https://rextester.com
Linear Homogeneous Recurrence Relations (20 points)
Relations (20 points)
Graphs (20 points)
Trees (20 points)
Bonus: Coding & Prime Numbers (5 points)
Answered 5 days AfterMay 05, 2021

## Solution

Swapnil answered on May 07 2021

1) LINEAR HOMOGENEOUS RECURRENCE RELATIONS