Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Home Assignment #3
Student: Alina Harutyunyan
ID# A09130264
1. Determine whether f(n) = O(g(n)) or (g(n)) = O(f(n)) or both and prove your claim.
(a) f(n) = 2n+3 and g(n) = 2n
(b) f(n) = 100n + log n and g(n) = n + (log n)2
(c) f(n) = sqrt(n) + log n and g(n) = log n
Answer: First of all let’s see what is the definition of big-O.
Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be O(g(x) ) , which is read as f(x) is big-oh of g(x) , if and only if there are constants C and n0 such that
| f(x) | ≤ C | g(x) | , whenever x > n0 .
C=1/8, n0=0 => f(n)=O(g(n))
2n≤ C*2n+3 for any n ≥ n0
C=2, n0=0 => g(n)=O(f(n))
So the answer is both.
C=100, n0=1 => f(n)=O(g(n))
n + (log n)2 ≤ C*(100n + logn ) for any n≥n0
C=1/100, n0=1 => g(n)=O(f(n))
C=6, n0=1 => f(n)=O(g(n))
2. Given a set S of n real numbers, design an algorithm that finds a number that is not in S. The running time of your algorithm must be O(n).
Answer: We will consider the set as a one-dimensional array S[x1 , x2, … , xn ]
Firstly we will find the minimum number of this array, then by subtracting 1 from it we will get a number which is not in S.
Int min=S[0];
For i=1 to n-1
If S[i] < min
then min = S[i]
Input: S={ x1 , x2, … , xn} , element min-1
Output: Not found.
3. Write pseudocode for the following.
(a) Design an algorithm that, given a linked list, prints its contents in reverse order using a stack as an auxiliary storage structure.
(b) Design a recursive procedure to perform the same task without making explicit use of a stack. In what form is a stack still involved in your recursive solution?
4. Give the sequence of numbers that are printed when you call the following method as myRecursion(6).
public static void myRecursion (int n) {
if (n <= 0) return;
System.out.println(n);
myRecursion(n-2);
myRecursion(n-3);
System.out.println(n);}
Answer: The sequence of numbers printed are {6, 4, 2, 2, 1, 1, 4, 3, 1, 3, 6}
5.
6. DuckDuckGo is a search engine that helps you find information on the Internet, just like Google Search. For this question, you need to do some research about the two search engines (found at www.duckduckgo.com and www.google.com) and answer the following questions:
(a) What are the basic underlying differences between the two search engines?
(b) List some advantages and disadvantages of each search engine.
(c) How does each engine rank websites? That is, when showing results for a keyword search, how does each service decide what website to list first?
(d) What are some privacy issues that might occur when using Google Search?