Algorithms, Basic Computer Science

1. In each of the following situations, indicate whether f = O(g), or f = O(g), or both (in which case f = T(g)). Briefly explain why.
(a) f(n)=10n5 +8n2,g(n)=20n4 +7n3 +300 (b) f(n) = log 8n, g(n) = log(n2)
(c) f(n)=n3logn,g(n)=13n 5
(d) f(n) = (3)n, g(n) = 6n3 2
2. We introduced in class that when analyzing algorithm complexity, we can ignore the lower-order terms and the coefficient of the leading term. For example, 3n + 5 ? n. Using the formal definition of the big-O notation, show that 3n + 5 = O(n) and n = O(3n + 5), in other words, 3n + 5 = T(n).
3. The Fibonacci numbers F0, F1, F2, . . ., are defined by the rule F0 =0,F1 =1,Fn =Fn-1 +Fn-2.
Use induction to prove that Fn = 20.5n for n = 6.
4. Write a python program to compute the Fibonacci numbers F8, F28, F48. What are the three values? What is the total number of additions needed by your program? Provide your answers as well as your source code.
Posted Date: 9/11/2012 10:02:47 PM | Location : United States







Related Discussions:- Algorithms, Assignment Help, Ask Question on Algorithms, Get Answer, Expert's Help, Algorithms Discussions

Write discussion on Algorithms
Your posts are moderated
Related Questions
How do I change file permissions? Every time I execute chmod commands it tells me permission denied.

Systems Life Cycle Approach Systems Analysis and Design follows a life cycle for development, as shown below. Brief discussion on this approach is given here: Figure

Question 1 Write a long note on the security features of Windows XP Question 2 Write a long note on computer peripherals, briefly describing some of the devices Question

Importance of Good Database Design Poor database design may have results in unwanted data redundancy Poor database design keeps errors leading to bad decisions and results Practica

Question 1 Draw a neat diagram of the organization of computer and explain about each unit Question 2 Explain batch processing system and multi-processing in brief Questi

Write an Assembly program that reads an integer (-32,768 through 32,767) in decimal and prints its equivalent in binary. The output must show all 16 bits. And you must use a loop

Looping Statement:  The purpose of a loop structure is to repeat certain tasks until some condition is satisfied. Several variations of a loop structure are available in each pro

Scores from a statistics exam are reported as deviation scores. Which of the following deviation scores indicates a higher position in the class distribution?

The following are required: Create a project in Access.  Your database must have flow and a theme. The database must be normalized.  The content m

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr