Alpingi.com

Freshers Jobs | AMCAT | Fresherworld | JEE | NEET | GATE & CAT

AMCAT coupon code --> ALP50 | Freshersworld Discount Code --> AFF1451AGI
TechMario UpdatesAMCAT Discount Code (ALP50) - get flat off TechMario UpdatesFreshersworld Coupon Code (AFF1451AGI) - - get flat 100 off TechMario UpdatesGovt Jobs- सरकारी नौकरियों के लिए यहां क्लिक करें

AMCAT Complexity Theory Questions – Computer Programming

AMCAT Computer Programming module: For AMCAT exam, Quantitative ability, Logical reasoning and English language are the mandatory modules. Apart from that, for IT job aspirants, Computer programming is an essential section. Here we will be discussing in detail about AMCAT Complexity Theory Questions.

AMCAT Complexity Theory Questions – Computer Programming

AMCAT Complexity Theory Questions

Usually 1-2 questions, come from the topic Complexity Theory. The question level varies from easy to tough. It takes an average of 40 to 50 seconds to solve the problem. Below you will get to know about what is Complexity theory and sample questions related to it.

AMCAT CSE Syllabus

About Complexity Theory

Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem.
The most common resources

  • time (how many steps it takes to solve a problem)
  • space (how much memory it takes)

Other resources, e.g.,how many parallel processors are needed to solve a problem in parallel Computability theory deals with whether a problem can be solved at all, regardless of the resources required.

Problems and instances

A single problem is an entire set of related questions, where each question is a finite-length string.
The FACTORIZE problem

  • given an integer written in binary
  • return all of the prime factors of that number

A particular question is called an instance. Instance of the FACTORIZE problem is give the factors of the number 15
Decision problems
Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always yes/no.
The IS-PRIME problem

  • given an integer written in binary
  • return whether it is a prime number or not

Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem.
Complexity classes
The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases. The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time.This class contains many problems that people would like to be able to solve effectively, including the Boolean satisfiability problem, All the problems in this class have the property that their solutions can be checked effectively. The question of whether P is the same set as NP is the most important open question in theoretical computer science.

Download Questions on AMCAT Complexity Theory 

AMCAT Complexity Theory Practice Question Download

Practice Questions on Complexity Theory

Below is a list of AMCAT Complexity Theory Questions to practice and learn:

Question 1
In case of the worst timing, which might be the worst to implement in sorting algorithm?
A. Quick
B. Merge
C. Tim
D. Heap
Answer: Option A
Explanation:
Quick sort has worse time complexity of O(n^2)

Question 2
In case of the worst timing, which might be the worst to implement in sorting algorithm?
A. Quick
B. Merge
C. Tim
D. Heap
Answer: Option C
Explanation: Quick sort has worse time complexity of O(n^2)

Question 3
There are 2 buildings and on each’s window, a flower pot is kept. Ravi’s mother tells him to add each cell/window to the other and store in a matrix? What would be time complexity if he writes a code to do so?
A. Theta(n)
B. Theta( log n)
C. Theta(n^2)
D. Theta(n log n)
Answer: Option A

Question 4
Which of the following has the quickest average time complexity?
A. Quick
B. Radix
C. Bubble
D. Heap
Answer: Option B
Explanation:
Radix sort is quickest amongst these in average time

Question 5
In regards to time complexity which will perform better ω(n^4) or O(n^3)?
A. ω(n^4)
B. O(n^3)
C. Both Equally
D. Cannot be said
Answer: Option A
Explanation:
ω(n^4) as it is omega is measured for best time complexity

Question 6
Which of the following case does not exist in complexity theory?
A. Best case
B. Worst case
C.  Average case
D. Null case
Answer: Option D
Explanation:
Null case does not exist in complexity Theory.

Hope the mock AMCAT Complexity Theory Questions helps in understanding the topic.

Download AMCAT Questions on Polymorphism

AMCAT Sample Questions on Heaps

Mock test questions on Abstraction

Leave a Reply

Your email address will not be published.

alpingi © 2018