Skip to main content

PROBLEM SOLVING AND PYTHON PROGRAMMING QUIZ

1) What is the first step in problem-solving? A) Writing code B) Debugging C) Understanding the problem D) Optimizing the solution Answer: C 2) Which of these is not a step in the problem-solving process? A) Algorithm development B) Problem analysis C) Random guessing D) Testing and debugging Answer: C 3) What is an algorithm? A) A high-level programming language B) A step-by-step procedure to solve a problem C) A flowchart D) A data structure Answer: B 4) Which of these is the simplest data structure for representing a sequence of elements? A) Dictionary B) List C) Set D) Tuple Answer: B 5) What does a flowchart represent? A) Errors in a program B) A graphical representation of an algorithm C) The final solution to a problem D) A set of Python modules Answer: B 6) What is pseudocode? A) Code written in Python B) Fake code written for fun C) An informal high-level description of an algorithm D) A tool for testing code Answer: C 7) Which of the following tools is NOT commonly used in pr...

Omega, Theta notation

OMEGA NOTATION (Ω)
The Omega notation provides a tight lower bound for f(n). This means that the function can never do better than the specified value but it may do worse. 
Ω notation is simply written as, f(n) ∈ Ω(g(n)), where n is the problem size and 
Ω(g(n)) = {h(n): ∃ positive constants c > 0, n0  such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n0}.
Hence, we can say that Ω(g(n)) comprises a set of all the functions h(n) that are greater than or equal to cg(n) for all values of n ≥ n0.
If cg(n) ≤ f(n), c > O, ∀ n ≥ nO, then f(n) ∈ Ω(g(n)) and g(n) is an asymptotically tight 
lower bound for f(n).
Examples of functions in Ω(n2) include: n2, n2.9, n3+ n2, n3
Examples of functions not in Ω(n3) include: n, n2.9, n2
To summarize, 
• Best case Ω describes a lower bound for all combinations of input. This implies that the function can never get any better than the specified value. For example, when sorting an array the best case is when the array is already correctly sorted.
• Worst case Ω describes a lower bound for worst case input combinations. It is possibly greater than best case. For example, when sorting an array the worst case is when the array is sorted 
in reverse order.
• If we simply write Ω, it means same as best case Ω.

THETA NOTATION (Θ)
Theta notation provides an asymptotically tight bound for f(n). Θ notation is simply written as, 
f(n) ∈ Θ(g(n)), where n is the problem size and Θ(g(n)) = {h(n): ∃ positive constants c1, c2, and n0
 such that 0 ≤ c1g(n) ≤ h(n) ≤ c2
g(n), ∀ n ≥ n0}. 
Hence, we can say that Θ(g(n)) comprises a set of all the functions h(n) that are between c1g(n)and c2g(n) for all values of n ≥ n0.
If f(n) is between c1g(n) and c2g(n), ∀ n ≥ n0,then f(n) ∈ Θ(g(n)) and g(n) is an asymptotically tight bound for f(n) and f(n) is amongst h(n) in the set.
To summarize, 
• The best case in Θ notation is not used.
• Worst case Θ describes asymptotic bounds for worst case combination of input values. 
• If we simply write Θ, it means same as worst case Θ.

OTHER USEFUL NOTATIONS
There are other notations like little o notation and little ω notation which have been discussed below.
Little o Notation
This notation provides a non asymptotically tight upper bound for f(n). To express a function using this notation, we write 
f(n) ∈ o(g(n)) where
o(g(n)) = {h(n) : ∃ positive constants c, n0
 such that for any c > 0, n0 > 0, and 0 ≤ h(n) ≤ cg(n), ∀ n ≥ n0}.
This is unlike the Big O notation where we say for some c > 0 (not any). For example, 5n3 = O(n3) is asymptotically tight upper bound but 5n2 = o(n3) is non-asymptotically tight bound for f(n).
Examples of functions in o(n3) include: n2.9, n3 / log n, 2n2
Examples of functions not in o(n3) include: 3n3, n3, n3 / 1000

Little Omega Notation (w)
This notation provides a non-asymptotically tight lower bound for f(n). It can be simply written as,f(n) ∈ ω(g(n)), whereω(g(n)) = {h(n) : ∃ positive constants c, n0 such that for any c > 0, n0 > 0, and 0 ≤ cg(n) < h(n),∀ n ≥ n0}.
This is unlike the Ω notation where we say for some c > 0 (not any). For example, 5n3 = Ω(n3) is asymptotically tight upper bound but 5n2 = ω(n3) is non-asymptotically tight bound for f(n).
Example of functions in ω(g(n)) include: n3 = ω(n2), n3.001 = ω(n3), n2
logn = ω(n2)
Example of a function not in ω(g(n)) is 5n2 ≠ ω(n2) (just as 5≠5)
An imprecise analogy between the asymptotic comparison of functions f(n) and g(n) and the relation between their values can be given as:
f(n) = Ω(g(n)) ≈ f(n) ≥ g(n) f(n) = ω(g(n)) ≈ f(n) > g(n)

Popular posts from this blog

Abbreviations

No :1 Q. ECOSOC (UN) Ans. Economic and Social Commission No: 2 Q. ECM Ans. European Comman Market No : 3 Q. ECLA (UN) Ans. Economic Commission for Latin America No: 4 Q. ECE (UN) Ans. Economic Commission of Europe No: 5 Q. ECAFE (UN)  Ans. Economic Commission for Asia and the Far East No: 6 Q. CITU Ans. Centre of Indian Trade Union No: 7 Q. CIA Ans. Central Intelligence Agency No: 8 Q. CENTO Ans. Central Treaty Organization No: 9 Q. CBI Ans. Central Bureau of Investigation No: 10 Q. ASEAN Ans. Association of South - East Asian Nations No: 11 Q. AITUC Ans. All India Trade Union Congress No: 12 Q. AICC Ans. All India Congress Committee No: 13 Q. ADB Ans. Asian Development Bank No: 14 Q. EDC Ans. European Defence Community No: 15 Q. EEC Ans. European Economic Community No: 16 Q. FAO Ans. Food and Agriculture Organization No: 17 Q. FBI Ans. Federal Bureau of Investigation No: 18 Q. GATT Ans. General Agreement on Tariff and Trade No: 19 Q. GNLF Ans. Gorkha National Liberation Front No: ...

PROBLEM SOLVING AND PYTHON PROGRAMMING QUIZ

1) What is the first step in problem-solving? A) Writing code B) Debugging C) Understanding the problem D) Optimizing the solution Answer: C 2) Which of these is not a step in the problem-solving process? A) Algorithm development B) Problem analysis C) Random guessing D) Testing and debugging Answer: C 3) What is an algorithm? A) A high-level programming language B) A step-by-step procedure to solve a problem C) A flowchart D) A data structure Answer: B 4) Which of these is the simplest data structure for representing a sequence of elements? A) Dictionary B) List C) Set D) Tuple Answer: B 5) What does a flowchart represent? A) Errors in a program B) A graphical representation of an algorithm C) The final solution to a problem D) A set of Python modules Answer: B 6) What is pseudocode? A) Code written in Python B) Fake code written for fun C) An informal high-level description of an algorithm D) A tool for testing code Answer: C 7) Which of the following tools is NOT commonly used in pr...

ELECTROMAGNETIC WAVES

Understanding Electromagnetic Waves: The Invisible Messengers of Energy Electromagnetic (EM) waves are everywhere around us, shaping the way we live and communicate, though most of the time we are unaware of their presence. From the light we see to the signals carrying our favorite songs on the radio, EM waves play a fundamental role in both nature and modern technology. In this post, we’ll explore the nature of electromagnetic waves, their types, and their significance in daily life. What Are Electromagnetic Waves? At their core, electromagnetic waves are fluctuations of electric and magnetic fields that travel through space. Unlike sound waves, which need a medium like air or water to propagate, electromagnetic waves can travel through a vacuum. This means they can traverse the vast emptiness of space, which is how sunlight reaches Earth from the Sun. The discovery of electromagnetic waves is credited to James Clerk Maxwell in the 19th century. He formulated a set of equations—now kn...