Time complexities and asymptotic notation

Searching

Algorithm	Data Structure	Time Complexity		Space Complexity
		Average	Worst	Worst
Depth First Search (DFS)	Graph of |V| vertices and |E| edges	-	O(|E| + |V|)	O(|V|)
Breadth First Search (BFS)	Graph of |V| vertices and |E| edges	-	O(|E| + |V|)	O(|V|)
Binary search	Sorted array of n elements	O(log(n))	O(log(n))	O(1)
Linear (Brute Force)	Array	O(n)	O(n)	O(1)
Shortest path by Dijkstra, using a Min-heap as priority queue	Graph with |V| vertices and |E| edges	O((|V| + |E|) log |V|)	O((|V| + |E|) log |V|)	O(|V|)
Shortest path by Dijkstra, using an unsorted array as priority queue	Graph with |V| vertices and |E| edges	O(|V|^2)	O(|V|^2)	O(|V|)
Shortest path by Bellman-Ford	Graph with |V| vertices and |E| edges	O(|V||E|)	O(|V||E|)	O(|V|)

 

Sorting

Algorithm	Data Structure	Time Complexity			Worst Case Auxiliary Space Complexity
		Best	Average	Worst	Worst
Quicksort	Array	O(n log(n))	O(n log(n))	O(n^2)	O(n)
Mergesort	Array	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Heapsort	Array	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Bubble Sort	Array	O(n)	O(n^2)	O(n^2)	O(1)
Insertion Sort	Array	O(n)	O(n^2)	O(n^2)	O(1)
Select Sort	Array	O(n^2)	O(n^2)	O(n^2)	O(1)
Bucket Sort	Array	O(n+k)	O(n+k)	O(n^2)	O(nk)
Radix Sort	Array	O(nk)	O(nk)	O(nk)	O(n+k)

 

Heaps

Heaps	Heapify	Find Max	Extract Max	Increase Key	Insert	Delete	Merge
Linked List (sorted)	-	O(1)	O(1)	O(n)	O(n)	O(1)	O(m+n)
Linked List (unsorted)	-	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
Binary Heap	O(n)	O(1)	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(m+n)
Binomial Heap	-	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))
Fibonacci Heap	-	O(1)	O(log(n))*	O(1)*	O(1)	O(log(n))*	O(1)

 

Graphs

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency list	O(|V|+|E|)	O(1)	O(1)	O(|V| + |E|)	O(|E|)	O(|V|)
Incidence list	O(|V|+|E|)	O(1)	O(1)	O(|E|)	O(|E|)	O(|E|)
Adjacency matrix	O(|V|^2)	O(|V|^2)	O(1)	O(|V|^2)	O(1)	O(1)
Incidence matrix	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|E|)

 

Data Structures

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Indexing	Search	Insertion	Deletion	Indexing	Search	Insertion	Deletion
Basic Array	O(1)	O(n)	-	-	O(1)	O(n)	-	-	O(n)
Dynamic Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)	O(n)
Singly-Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Doubly-Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Skip List	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)	O(n log(n))
Hash Table	-	O(1)	O(1)	O(1)	-	O(n)	O(n)	O(n)	O(n)
Binary Search Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)	O(n)
Cartesian Tree	-	O(log(n))	O(log(n))	O(log(n))	-	O(n)	O(n)	O(n)	O(n)
B-Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Red-Black Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Splay Tree	-	O(log(n))	O(log(n))	O(log(n))	-	O(log(n))	O(log(n))	O(log(n))	O(n)
AVL Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)

 

Notation for asymptotic growth

letter	bound	growth
(theta) Θ	upper and lower, tight[1]	equal[2]
(big-oh) O	upper, tightness unknown	less than or equal[3]
(small-oh) o	upper, not tight	less than
(big omega) Ω	lower, tightness unknown	greater than or equal
(small omega) ω	lower, not tight	greater than

Basic Questions and Answers on Artificial Intelligence

1) What is AI?

Systems that think like humans

Systems that think rationally

Systems that act like humans

Systems that act rationally

2) Define an agent.

     An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.

3) What is an agent function?

   An agent’s behavior is described by the agent function that maps any given percept sequence  to an action.

4) Differentiate an agent function and an agent program.

Agent Function Agent Program

An abstract mathematical description A concrete implementation,running on the agent Architecture.

5) What can Ai do today?

 

 

6) What is a task environment? How  it is specified?

Task environments   are essentially the "problems" to which rational agents are the "solutions."

A Task environment is specified using PEAS (Performance, Environment,    Actuators, Sensors) description.

     

7) Give an example of PEAS description for an automated taxi.

 

8) Give PEAS description for different agent types.

9) List the properties of task environments.

 Fully observable vs. partially observable.

 Deterministic vs. stochastic.

 Episodic vs. sequential

 Static vs, dynamic.

 Discrete vs. continuous.

 Single agent vs. multiagent.

10) Write a function for the table driven agent.

11) What are the four different kinds of agent programs?

Simple reflex agents;

Model-based reflex agents;

Goal-based agents; and

Utility-based agents.

12) Explain a simple reflex agent with a diagram.

Simple reflex agents

 The simplest kind of agent is the simple reflex agent. These agents select actions on the basis AGENT

of the current percept, ignoring the rest of the percept history.

 

13) Explain with a diagram the model based reflex agent.

13a)  Explain with a diagram the goal based reflex agent.

Knowing about the current state of the environment is not always enough to decide what

to do. For example, at a road junction, the taxi can turn left, turn right, or go straight on.

The correct decision depends on where the taxi is trying to get to. In other words, as well

as a current state description, the agent needs some sort of goal information that describes

situations that are desirable-for example, being at the passenger's destination.

13b) What are utility based agents?

Goals alone are not really enough to generate high-quality behavior in most environments.

For example, there are many action sequences that will get the taxi to its destination (thereby

achieving the goal) but some are quicker, safer, more reliable, or cheaper than others.

A utility function maps a state (or a sequence of states) onto a real number, which

describes the associated degree of happiness.

13c) What are learning agents?

A learning agent can be divided into four conceptual components, as shown in Fig-

 2.15. The most important distinction is between the learning element, which is re-

ELEMENT sponsible for making improvements, and the performance element, which is responsible for

selecting external actions. The performance element is what we have previously considered

to be the entire agent: it takes in percepts and decides on actions. The learning element uses

CRITIC feedback from the critic on how the agent is doing and determines how the performance

element should be modified to do better in the future.

 

Searching Techniques

14) Define the problem solving agent.

           A Problem solving agent is a goal-based agent . It decide what to do by finding sequence of actions that lead to desirable states. The agent can adopt a goal and aim at satisfying it. 

Goal formulation is the first step in problem solving.

      

15) Define the terms goal formulation and problem formulation.

               Goal formulation,based on the current situation and the agent’s performance measure,is the first step in problem solving. 

                       The agent’s task is to find out which sequence of actions will get to a goal state.

Problem formulation is the process of deciding what actions and states to consider given a goal

16) List the steps involved in simple problem solving agent.

(i) Goal formulation

(ii) Problem formulation

(iii) Search

(iv) Search Algorithm

(v) Execution phase

17) Define search and search algorithm.

                    The process of looking for sequences actions from the current state to reach the goal state is called search.

The search algorithm takes a problem as input and returns a solution in the form of action sequence. Once a solution is found,the execution phase consists of carrying out the recommended action..

18) What are the components of well-defined problems?

o The initial state that the agent starts in . The initial state for our agent of example problem is described by In(Arad)

o A Successor Function returns  the possible actions available to the agent. Given a state x,SUCCESSOR-FN(x) returns a set of {action,successor} ordered pairs where each action is one of the legal actions in state x,and each successor is a state that can be reached from x by applying the action.

      For example,from the state In(Arad),the successor function for the Romania  

       problem would return 

{ [Go(Sibiu),In(Sibiu)],[Go(Timisoara),In(Timisoara)],[Go(Zerind),In(Zerind)] }

o Thr goal test determines whether the given state is a goal state.

o A path cost function assigns numeric cost to each action. For the Romania problem the cost of path might be its length in kilometers.

19) Differentiate toy problems and real world problems.

TOY PROBLEMS REAL WORLD PROBLEMS

A toy problem is intended to illustrate various problem solving methods. It can be easily used by different  researchers to compare the performance of algorithms.

A real world problem is one whose solutions people actually care about.

20) Give examples of real world problems.

(i) Touring problems

(ii) Travelling Salesperson Problem(TSP)

(iii) VLSI layout

(iv) Robot navigation

(v) Automatic assembly sequencing

(vi) Internet searching

21) List the criteria to measure the performance of different search strategies.

o Completeness : Is the algorithm guaranteed to find a solution when there is one?

o Optimality : Does the strategy find the optimal solution?

o Time complexity : How long does it take to find a solution?

o Space complexity : How much memory is needed to perform the search?

22) Differentiate Uninformed Search(Blind search) and Informed Search(Heuristic Search) strategies.

Uninformed or Blind Search Informed or Heuristic Search

o No additional information beyond that provided in the problem definition

o Not effective

o No information about number of steps or path cost o More effective

o Uses problem-specific knowledge beyond the definition of the problem itself.

23) Define Best-first-search.

Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on the evaluation function f(n ). Traditionally,the node with the lowest evaluation function is selected for expansion.

Basic Questions and Answers on Algorithms

1. Define Algorithm.

An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.

2.Write a short note on Algorithm Design and Analysis of Process.

o Understand the problem

o Decide onComputational DeviceExact Vs Approximate Algorithms

o Algorithm Design Techniques

o Design an algorithms

o Prove Correctness

o Analyze the Algori thm

o Code the Algorithm

3. What are the 2 kinds of Algorithm Efficiency

Time Efficiency-How fast your algorithm runs?

Space Efficiency-How much extra memory your algorithm needs?

 4. How can you specify Algorithms?

Algorithms can be specified natural language or pseudo code. 

5. What is Pseudo Code?

Pseudo Code is a mixture of Natural Language and Programming Language Constructs such as functions, loops, decision making statements..etc

6. What are the Important Problem Types?

• Sorting

• Searching

• String Processing

• Graph Problem

• Combinatorial Problem

• Geometric Problem

• Numerical Problem

7.How can you Classify Algorithms

Among several ways to classify algorithms, the 2 principal alternatives are

• To group algorithms according to types of problem they solve com

• To group algorithms according to underlying design techniques they are based upon

8. What is Sorting Problem?

Sorting algorithm is rearrange the items of given list descending/ascending order. Sorting algorithms classified into

• Stable Sorting Algorithm

• Non-Stable Algorithm

9.What is Searching Problem?

Finding a given value, called search key given set.  Searching Algorithms needs more

memory space   and sorted array.

10. What is Graph Problem?

Graph is a collection of dg s and vertices. G=(V,E). For e.g. Traversal Algorithms, Shortest

Path Algorithm, Graph Colouring Problem

11. What is Combinatorial  Problem.

This problem that ask to find combinatorial object such as permutations, combinations or a

subset. Combinatorial problems are most difficult to solve. For eg Travelling sales man

problem

12. Differentiate Time Efficiency and Space Efficiency?

Time Efficiency measured by counting the number of times the algorithms basic operation is executed. Space Efficiency is measured by counting the number of extra memory units consumed by the algorithm.

13. What are the features of efficient algorithm?

• Free of ambiguity

• Efficient in execution time

• Concise and compact Completeness

• Definiteness Finiteness

14.Define Order of Algorithm

The order of algorithm is a standard notation of an algorithm that has been developed to represent function that bound the computing time for algorithms.The order of an algorithm is a way of defining its efficiency. It is usually referred as O-notation

15.  Define Big Omega Notation.

Omega notation provides lower bound for the function t

A function t(n) is said to Omega (g(n)), if there exist some.positive constant C and some non negative integer N0, such that

t(n)>=Cg(n) for all n>=n0 

     16.What is Big ‘Oh’     

               Notation.

The Big ‘Oh’ notation provides an upper bound for the function t.A function t(n) is said to be O(g(n)), if there exist some positive constant C and some non negative number,suchthat, t(n)<=Cg(n), for all n>=no

17. What are the different types of time complexity?

The time complexity can be classified into 3 types, they are

• Worst case analysis

• Average case analysis

• Best case analysis

18.How the algorithm’s time efficiency is measured.

Time efficiency indicates how fast an algorithm runs. Time taken by a program to complete its task depends on the number of steps in an algorithm.

The time taken by an algorithm is the sum of compile time and execution time. The compile time does not depend on the instance characteristics

Python Programming MCQ

1. Which of the following is correct about Python?

A - Python is a high-level, interpreted, interactive and object-oriented scripting language.

B - Python is designed to be highly readable.

C - It uses English keywords frequently where as other languages use punctuation, and it has fewer syntactical constructions than other languages.

D - All of the above.

2. Which of the following operator in python performs exponential power calculation on operands?

A - **

B - //

C - is

D - not in

3. Which of the following operator in python evaluates to true if it does not finds a variable in the specified sequence and false otherwise?

A - **

B - //

C - is

D - not in

4. Which of the following function converts a string to all uppercase?

A – upper

B - isdecimal

C - swapcase

D – title

5. Which of the following is correct about Python?

A - It supports automatic garbage collection.

B - It can be easily integrated with C, C++, COM, ActiveX, CORBA, and Java.

C - Both of the above.

D - None of the above.

6. Which of the following statement terminates the loop statement and transfers execution to the statement immediately following the loop?

A - break

B - continue

C - pass

D - None of the above.

7. What is the output of len[1, 2, 3]?

A - 1

B - 2

C - 3

D – 4

8. Which of the following function checks in a string that all characters are in lowercase?

A - islower

B - isnumeric

C - isspace

D – istitle

9. Which of the following environment variable for Python tells the Python interpreter where to locate the module files imported into a program?

A - PYTHONPATH

B - PYTHONSTARTUP

C - PYTHONCASEOK

D – PYTHONHOME

10. Which of the following data types is not supported in python?

A - Tuple

B - Dictionary

C - Generics

D - List

Microprocessor and interfacing MCQ

1. The size of 8086 16 bit is decided by

a.  Control Bus                                                   b. Data Bus                 

c. Address Bus                                                   d. Flag register

2. The size of address bus of 8086 is

a. 16 bit                                                               b. 32 bit             

c. 20 bit                                                               d. 64 bit

3. Which one is/are control flag in flag register?

a. Trap       flag                                                   b. Interrupt flag         

c. Direction Flag                                                d. All of these

4. How many pins are there in 8086 microprocessor?

a. 24                              b. 28                              c. 40                              d. 16

5. How many pins are there in 8251 USART chip?

a. 24                              b. 28                              c. 40                              d. 16

6. How many pins are there in 8253 PIT chip?

a. 24                              b. 28                              c. 40                              d. 16

7. How many pins are there in 8255 PPI chip?

a. 24                              b. 28                              c. 40                              d. 16

8. How many pins are there in 8237 DMA chip?

a. 24                              b. 28                              c. 40                              d. 16

9. How many pins are there in 8259 PIC chip?

a. 24                              b. 28                              c. 40                              d. 16

10. How many pins are there in 8279 KDC chip?

a. 24                              b. 28                              c. 40                              d. 16

Discrete Mathematical Structure MCQ

1. Which one is not set operation?

a. Set difference                   b. Union                     c. Intersection                      d. Proper subset

2. Which is the intersection of set A={a,e,i,o,u} and B={a,b,c,d,e}?

a. {a,e}                                    b. {a}                          c. {b}                                      d. {c}

3. What is the formula for Power set (A), if A has n number of elements?

a. 2n                                       b. 2ⁿ                            c. 2n-1                                    d. 2^n-1

4. Which is not the property of Binary relation?

a. Reflexive                           b. Symmetric            c. Identity                             d. Transitive

5. How many words can be formed for the word “DISCRETE”?

a. 20160                                 b. 40320                     c. 5040                                   d. None

6. If n is number of holes and m is number of pigeon, then which condition has to be followed by Pigeon-hole principle?

a. n>m                                    b. n                        c. n=m                                    d. n=

7. DeMorgan Law is

a. (a’+b’)=(ab)’                     b. (a’b’)=(a+b)’         c. both                                    d. none

8. Which symbol is known as Universal Quantifier?

a. ∀                                         b. ∃                             c. ∆                                          d. ∁

9. Which symbol is known as existential quantifier?

a. ∀                                         b. ∃                             c. ∆                                          d. ∁

10. P->Q is equivalent to

a. ~P⋁Q                                 b. ~P⋀Q                     c. P⋁~Q                                 d. P⋀~Q

Digital Electronics MCQ

1. Which one is unary gate?

a. NOR                                    b. XNOR                                 c. NOT                                    d. XOR

2. Which binary number is same as 2’s complement of itself?

a. 1001                                   b. 0110                                   c. 1010                                   d. 1000

3. Which is/are used to reduce the Boolean expression?

a. Karnaugh map                                                                  b. Boolean algebra laws

c. Boolean properties                                                          d. All of these

4. What is the Boolean expression of given logic diagram?

a. A⊙B
b. A’B’ + AB
c. (A⊕B)’
d. All of these

5. Race around condition is associated with

a. RS flip flop                        b. JK flip flop                         c. MS flip flop                        d. none of these

6. If X is any input of flip flop, then the expression Q⊕X is of___________________________ flip flop.

a. Toggle Flip Flop               b. Delay Flip Flop                 c. MS Flip Flop                      d. RS Flip flop

7. How many flip flops are needed to design MOD-27 counter?

a. 5                                          b. 6                                          c. 4                                          d. 3

8. What is/are the difference between Sequential circuit and combinational circuit?

a. Feedback in sequential circuit                                     

b. Only Universal gates are used to design sequential circuit

c. Sequential circuits are used to design memory.

d. All of the above

9. How many RAM chips are needed to design the main memory capacity of 2MB, where one RAM chip is of the size 512 bytes?

a. 12                                        b. 16                                       c. 9                                          d. 11

10. Determine the effective access time, if the cache access time is 10ns and main memory access time is 110ns?

a. 19ns                                   b. 20ns                                   c. 18ns                                   d. 21ns