Welcome to CSCB63
TA name: William Granados
Tutorial: TUT06: Monday 4-5pm, HW215
Email Policy: Before emailing me, consider attending my practical or posting the question on Piazza. My email address is william.granadosmatamoros@mail.utoronto.ca. When emailing me, use your utoronto email and in the subject include "CSCB63".
Expectations: Content covered may appear on assignments or exams, so please be on time.
Monty Hall
There are 3 doors. Behind one door is the prize, behind the other two doors are empty (or goats, whatever). First you choose one door. Then the game host opens a door, but not what you choose, and not the prize door (the game host knows). The game host now offers you the choice of staying with your first choice or switching to the remaining door.
(a) What is the probability that the prize is behind your first choice?
(b) What is the probability that the prize is behind the remaining door?
The Assignment Due Date Paradox
You're taking 4 courses. All four Assignment 1's are due in week 4. Each prof independently chooses one weekday (Monday to Friday) for the due date.
(a) How many ways are there overall?
(b) How many ways are there such that all 4 assignments are due on different days, i.e., no two assignments are due on the same day? And so what is the probability that this happens?
(c) How many ways are there such that at least two assignments are due on the same day? And probability?
(d) You always have two assignments due on the same day, or two midterms on the same day. Is that conspiracy? Or just probability? :)
The ith Ball
There are 6 red balls and 9 blue balls in a bag; when you draw a ball from the bag, each ball in the bag is equally likely drawn. Randomly draw 3 balls from the bag without replacement---after a ball is drawn, do not put it back into the bag. Find the probability that the ith ball, ($1 \leq i \leq 3$), is one of the red balls.
- idea: push edges from an arbitrary on a min heap, iteratively select the smallest weighted edge which is a part of our solution.
- time complexity: $o(|e| \cdot \log(v))$ with an adjacency list and binomial heap, varies with implementation.
- fun fact the graph must be connected, otherwise will only find mst in one of the components.
- idea: sort edges by least weight, use a disjoint set data structure to iteratively select the smallest weighted edge that is a part of our solution.
- time complexity: $o(|e| \cdot \log(v))$, depending on ds implemention, can assume we use path compression and union by rank.
- fun fact: if the graph isn't connected, will generate a minimum spanning forest (a collection of trees!).
- idea: Keep track of best results seen so far when reaching a node, and ensure that we're always expanding the nodes in the cheapest way. Solves cheapest path in weighted graph.
- time complexity: $o(|e| + v \cdot \log(v))$, depending on ds implemention for finding cheapest node to expand, can use priority queue.
- BFS expands the nearest neighbours first, and can be used for shorest path problem on unicost graphs.
- BFS tree is explores per layer, and can be generally implemented with a queue data structure
- Tree generally looks complete, as it fills out layer per layer
- DFS expands and explores most recent node, and can be used for finding a path problem on any graph.
- DFS tree is created at length, and can be generally implemented with a queue data structure
- Tree generally looks longs, similar to a linked list, since it goes deep.
- Are trees with the invariant for each node: $\frac{1}{3} \leq \frac{node.left+1}{node.right +1} \leq 3$, you're keeping track of the ratio between the number of nodes in the left and right subtrees.
- Insertion begins like a normal BST, then you identify infractions for the invariant and execute one of the two rotations on a case by case basis.
- When deleting the root, you can replace it with either the successor (smallest node in right subtree) or predecessor(greatest node in left subtree), For this course always choose successor
- Quiz Solution
- Prove/disprove $\sqrt{n} \in \Omega(\log{n^{100}})$ $\sqrt{n} \in \Omega(\log{n^{100}}) \iff \exists c > 0, \exists n_0 > 0 \text{ s.t } \forall n \geq n_0 \sqrt{n} \geq c \cdot \log{n^{100}}$ $\sqrt{n} \geq c \cdot \log{n^{100}}$ $\sqrt{n} \geq c \cdot 100 \cdot \log{n}$ (log rules) Choose $n_0 = 10, c = \frac{1}{100}$, $\therefore$ statement holds and $\sqrt{n} \in \Omega(\log{n^{100}})$
- Prove/disprove $\sqrt{n} \in \Omega(\log{n^{n}})$ $\sqrt{n} \in \Omega(\log{n^{n}}) \iff \exists c > 0, \exists n_0 > 0 \text{ s.t } \forall n \geq n_0 \sqrt{n} \geq c \cdot \log{n^{n}}$ $\sqrt{n} \geq c \cdot \log{n^{n}}$ $\sqrt{n} \geq c \cdot n \cdot \log{n}$ (log rules) $ 1 \geq c \cdot \sqrt{n} \cdot \log{n}$ (divide by $\sqrt{n}$ both sides) This statement is a contradiction, because suppose we choose $n_0 > 1$, can always choose some $n > n_0$ such that the inequality doesn't hold. $\therefore \sqrt{n} \notin \Omega(\log{n^{n}})$
- Problems
- Draw a 2D table with column headers and row headers both being: ln(n), lg(n), lg(n^2), (lg n)^2, n, n*lg(n), 2^n, 2^(3n)