Introduction to algorithms

Question 1

What is an algorithm?

Answer 1

An algorithm is a set of finite steps, aimed at providing a solution to a problem

Question 2

What are the charateristics/properties of an algorithm?

Answer 2

1. Input/Output: Algorithms can take in 0 or more inputs, but must always produce some sort of output
2. Finiteness: Algorithms must have a finite number of steps
3. Definiteness: Every step of an algorithm must be clearly stated and unambigous
4. Effectiveness: Every step of an algorithm must be able to be converted into a programming language
5. Generality: An algorithm must be able to accept all inputs in it’s valid set of inputs, to produce the desired output

Question 3

What are the categories of algorithms?

Answer 3

Algorithms are categorised based on how their instructions are executed.
1. Sequencial algorithms: Here every instruction is executed, and they are executed in a succesive manner
2. Selective algorithms: Here every the execution or omision of certian instructions depends on if a certain condition is fuffilled or not
3. Iterative algorithms: These are algorithms where intructions or sets of instructions are repeated a number of times

Question 4

How is the performance analysis of an algorithm done?

Answer 4

The efficeincy of algorithms is determined by how much time or space(memory) they require to complete execution, algorithms are said to be efficent if they
require the least amount of space(memory) or time to complete execution. The two ways of determining an algorithm’s efficiency are:

1. Space complexity: This is the amount of space(memory) required by an algorithm to complete execution
2. Time complexity: This is the amout of time required by an algorithm to complete execution

Question 5

What is asymtotic analysis and what are asymtotic notations?

Answer 5

Asymtotic analysis is a mathematical way of figuring out the effiency of algorithm, it is solely dependent on the input of the algorithm and it is done with the help
of asymtotic notations, whtich are mathematical notations used to reppresent the effiency of algorithms

Question 6

What are the types of efficiency/scenariors of algorithms?

Answer 6

1. Worst case: The maximum time or memory(space) required by an algorithm to complete execution
2. Average case: The typical or average time or space required by an algorithm to complete execution
3. Best case: The minimum time or memery(space) required by an algorithm to complete execution

Question 7

What are some asymtotic noations used?

Answer 7

Asymtotic notations are used to represent the different scenerios of algorithms, big Oh (O) for worst case, Omega() for best case, and Teta() for best and worst case

Question 8

What are the Issues that come about when designing an algorithm?

Answer 8

How to design and how to analyze the algorithm

Question 9

what are the types of brute force algorithms?

Answer 9

Sacrificing and Optimizing Algorithms

Question 10

What are the different design approaches to algorithms?

Answer 10

Design an algorithm can be approached in 1 of 5 ways that include:
1. Brute force algorithms: These are algorithms where every potential solution to a problem is tried until the solution is found

2. Divide and Conquer: These are algorithms where a problem is divided into smaller problems, each is solved and their solutions are combined to solve the initial problem
3. Greedy Algorithms: These are algorithms where the optimal decision is made at every step of the algorithm with the aim of producing the optimal solution
4. Branch and bound algorithms: These are algorithms where every possible solution to a problem is analyzed to find the most efficient solution
5. Randomized algorithms: These are algorithms where random bits are added to the input to produce randomized outputs

Question 11

Which algorithm is used only in integer programming?

Answer 11

Branch and Bound algorithms

Question 12

Differentiate between Priori and Posterior Analysis.

Answer 12

Priori Analysis is the analysis of an algorithm before it is implemented. Posterior analysis is the analysis of an algorithm after its implementation

Question 13

What is the performance analysis of an algorithm?

Answer 13

It is analyzing an algorithm and predicting how much space(memory) or time it will require to complete execution based on its input

Question 14

What are the types of algorithms that exist?

Answer 14

insertion, deletion, updation, search and sorting algorithms

Question 15

Explain binary search.

Answer 15

1. Sort the array we want to search in ascending order
2. Set the first index of the array as the left, and the last index of the array as the right
   3.1 Find the midpoint, which is the left + (right -1) /2 ;
   3.2 if the left is greater than the right then the value is not in the array
3. check if element in the array[midpiont] == the element to be searched(key)
   4.1 if yes then the position of the element is the midpoint
   4.2 if at array[midpoint] > key
   4.2.1 repeat 3 and 4(in their entirety) but this time the left stays the same but the right becomes the midpoint-1
   4.3. if the array[midpoint[ < key] then :
   4.3.1 repeat 3 and 4(in their entirety) but this time the right stays the same but the left becomes the midpoint + 1

Question 16

Differentiate between Depth-first search and breath-first search.

Answer 16

DFS searches as far as possible on each branch of a graph, while BFS searches all neighboring nodes before moving on to the next dept

Question 17

what is dynamic programming?

Answer 17

With dynamic programming, a problem is broken down into sub-problems, each is solved and stored in an overlapping manner to avoid duplicaito