---
# System prepended metadata

title: CSC-208 Practice Problem 3

---

---
title: CSC-208 Practice Problem 3
fontsize: 10pt
---
# CSC-208 Practice Problem 3

## Counting

1. In a bowl of candies, there are A number of Skittles, B numbers of Hersheys and C number of M&Ms. Provide a combinatorial description for the number of possible ways you can pick the candies in each of the scenarios. 

    a. Pick three candies and then put them back in the bowl
&nbsp;
    b. Pick three candies without putting them back in the bowl
&nbsp;
    c. You are making a care packadge for your friend which needs 3 Skittles, 5 Hersheys and 1 M&M. 
## Complexity analysis
 ```
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
 
        mid = (high + low) // 2
 
        # If x is greater, ignore left half
        if arr[mid] < x:
            low = mid + 1
 
        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1
 
        # means x is present at mid
        else:
            return mid
 
    # If we reach here, then the element was not present
    return -1
```
2. a. Identify the relevent critical operation(hint: what oepration is performed at every step of the iteration?)
&nbsp;
b. Come up with a recurrence relation
&nbsp;
c. Guess a closed-form equation based on your recurrence relation(you can refer to the reading)
&nbsp;
## Probability
3. You have 10 upperclassmen and 10 lowerclassmen. We know that there are 6 upperclassmen and 2 lowerclassmen who are CS major.
&nbsp;
a. If we are to randomly pick a student out of that group, what's the probability of us picking a non-CS major?
&nbsp;
b. Given that we picked a upperclassman, what's the probability of them being a CS major?
&nbsp;
c. If we know that there are 2 stat concentrators among the upperclass CS majors, what's the probability of picking a stat concentrator out of all students?
&nbsp;

# Solution
1. a. $(A + B + C)^3$
   b. $(A + B + C) \times (A + B + C - 1) \times (A + B + C - 2)$
   c. $A \choose 3$ $\times$ $B \choose 5$ $\times$ $C \choose 1$

2. a. ```mid = (high + low) // 2```


    b. T(N) = T(N/2) + c for N > 1
        T(1) = c

    c.  T(N) = logN

2. a. $\frac{12}{20} = \frac{3}{5}$
    
    b. $p(cs|upper)$ = $\frac{6}{20}/\frac{10}{20} = \frac{3}{5}$
    
    c. $\frac{1}{2} * \frac{6}{10} * \frac{2}{6} = \frac{1}{10}$
