AMCAT coupon code --> AF01 (Upto 150 off)

AMCAT Complexity Theory Questions 2019 – Computer Programming

AMCAT Computer Programming module 2019: 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.

Contents

AMCAT Complexity Theory Questions 2019 – Computer Programming 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

Most Employability Test 2019

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.

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
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
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)

Question 4
Which of the following has the quickest average time complexity?
A. Quick
C. Bubble
D. Heap
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
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
Explanation:
Null case does not exist in complexity Theory.

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