Lecture # 8: Recurrence

  Substitution Method:1. Guess (unique each time)2. Check and prove using induction Statement 1: $latex T(n) = 2T( \frac{n}{2}) + n $        T (1) = 1Explaining:$latex T(n) = O(n^2)$It means that $latex T(n) \leq c n^2 $ $latex \forall n > n_o $  f(n) = Ω(g(n))f(n) =O(g(n))f(n) = Θ (g(n))  Now we will make guess …

Quiz 2 Solution

Q1. Which value of $latex d$ satisfies $latex T(n) \leq d n \log n$ for the recurrence: $latex T(n) = n + 10c \frac{n}{5} + T(\frac{3n}{10}) + T(\frac{7n}{10})$ Since we are given that $latex T(n) \leq dn \log n$, by induction we plug in this value in all the recursive terms: $latex T(n) \leq n …

Lecture # 7: Introduction to Graph Theory

Graphs: A pictorial representation of objects (Nodes) connected by links (Edges) is called a graph. A graph is a set of Nodes and Edges. A node is an object linked to other objects by edges. Edges are the connection or links between the Nodes. Edges can be single directional or bi-directional, single directional edges are shown …

Homework 3

Describe an algorithm that, given $latex n$ integers in the range $latex 0 $ to $latex k$, preprocesses its input and then answers any query about how many of the $latex n$ integers fall into a range $latex [a..b]$ in $latex O(1)$ time. Your algorithm should use Θ $latex (n+k) $ preprocessing time. Show how to sort $latex n $ integers …

Lecture 6: Probabilistic Analysis for Randomized Algorithm

Probabilistic Analysis:  Probabilistic Analysis is the use of probability in the analysis of problems. Most commonly, we use probabilistic analysis to analyze the running time of a randomized algorithm. Randomized Algorithms: Randomized Algorithms are those algorithms that either contain a random input or probability is used in the algorithm. Goal:  Our goal in these types of …

Lec#5 Counting Sort and Bucket Sort

Counting’ Sort:             Assume that we are given an array A=[a1,a2,a3,……..an], where k ≥ ai ≥ 0 and K is the max number in this array. The main fact about this sort that there is no comparison in it. Algorithm: 1.      Make a new array of size k, which is the max number in that array. Let new array is …

Homework 2

Show that in a binary tree the maximum number of nodes on level $latex i $ is $latex 2^{i}$. (Hint: Use Induction) Compute the following recurrences: (To solve recurrences, learn about master theorem, recursive tree and substitution method)  $latex T(n) = 2 T(n-5)$  $latex T(n) = n + T(1) + T(n-1)$ $latex T(n) = n  …

Lecture 4: Types of heaps,heap sort and decision trees

There are four main functions associated with heapsort 1.Fix function: In the fix function, compare that node with its children. If in a min-heap, swap the parent and the smallest child considering that the child is smaller than the parent itself. Continue if the parent is smaller than both children, else terminate the function.In a …

Lecture 3: Divide and Conquer Continued

Questions about rank problemQ1: In our rank problem, we made chunks of size 5. What if we have a chunk (usually the last one) which has less than 5 elements? Will this effects our solution?Ans: There are two approaches to this problem1: place dummy element of huge size in the last chunk so that all …

Quiz 1 Solution

Q1. We saw an an algorithm for finding $latex k$th smallest number with linear time complexity in class. We used chunks of size 5 and bounded the size of the partitioned arrays $latex S $ and $latex L $ to at most $latex \frac{7n}{10}$. What are the bounds on the size of $latex S $ …