What is an algorithm?
An algorithm is a set of finite steps, aimed at providing a solution to a problem
What are the charateristics/properties of an algorithm?
- Input/Output: Algorithms can take in 0 or more inputs, but must always produce some sort of output
- Finiteness: Algorithms must have a finite number of steps
- Definiteness: Every step of an algorithm must be clearly stated and unambigous
- Effectiveness: Every step of an algorithm must be able to be converted into a programming language
- Generality: An algorithm must be able to accept all inputs in it’s valid set of inputs, to produce the desired output
What are the categories of algorithms?
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
How is the performance analysis of an algorithm done?
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:
- Space complexity: This is the amount of space(memory) required by an algorithm to complete execution
- Time complexity: This is the amout of time required by an algorithm to complete execution
What is asymtotic analysis and what are asymtotic notations?
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
What are the types of efficiency/scenariors of algorithms?
- Worst case: The maximum time or memory(space) required by an algorithm to complete execution
- Average case: The typical or average time or space required by an algorithm to complete execution
- Best case: The minimum time or memery(space) required by an algorithm to complete execution
What are some asymtotic noations used?
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
What are the Issues that come about when designing an algorithm?
How to design and how to analyze the algorithm
what are the types of brute force algorithms?
Sacrificing and Optimizing Algorithms
What are the different design approaches to algorithms?
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
- 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
- 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
- Branch and bound algorithms: These are algorithms where every possible solution to a problem is analyzed to find the most efficient solution
- Randomized algorithms: These are algorithms where random bits are added to the input to produce randomized outputs
Which algorithm is used only in integer programming?
Branch and Bound algorithms
Differentiate between Priori and Posterior Analysis.
Priori Analysis is the analysis of an algorithm before it is implemented. Posterior analysis is the analysis of an algorithm after its implementation
What is the performance analysis of an algorithm?
It is analyzing an algorithm and predicting how much space(memory) or time it will require to complete execution based on its input
What are the types of algorithms that exist?
insertion, deletion, updation, search and sorting algorithms
What is a data structure?
A data structure is a set of data elements that provide an efficient way to store, organize, and use data in the computer.
Why do we need data structures?
When data is stored in increasingly large amounts, and the data is not stored and organized efficiently through the use of data structures, 3 problems arise:
- Processing: Large amounts of processing speeds are required to handle the data, and the processor is likely to fail
- Searching: Searching through the data becomes slow and inefficient
- Multiple requests: If the data is stored on a server, the more the request for the data from that server the more likely it is to fail
What are the advantages of data structures?
- Efficiency: The efficiency of a program depends on the data structure used e.g In a searching algorithm it is better to use a binary search tree or sorted array, to
reduce the number of traversals needed for searching, and increase efficiency. - Re-usability: Data structures only need to be implemented once and can be used multiple times throughout the program.
- Abstraction: Data structures provide abstraction as they can be used by client programs that do not know about the details of their implementation
How are data structures classified?
Data structures are of two types: primitive and nonprimitive
primitive data structures include: int, float, char, e.t.c
nonprimitive data structures include: Linear and Nonlinear data structures
nonlinear data structures include: trees and graphs
linear data structures include: static and dynamic data structures
static data structures include: arrays
dynamic data structures include: stacks, queues, linked list
What is a linear data structure and what are the types of linear data structures?
Linear data structures are data structures whose data elements are organized in a linear and non-hierarchical manner they include:
1. Arrays: A collection of data elements of the same data type, that share the same name but different positions/indexes within the collection
2. Linked List: A collection of elements called nodes, each node containing data and a pointer pointing to the next node in the collection
3. Stacks: Linear data structures where insertion and deletion are done at one end called the top
4. Queues: Linear data structures where insertion is done at one end called the rear and deletion is done at the other end called the front
What is a non-linear data structure and what are the types of non-linear data structures?
A nonlinear data structure is a data structure whose elements are organized in a nonsequential manner and elements can be connected to multiple other elements. They
include:
1. Trees: A multilevel data structure where data elements are called nodes, nodes up a level are called parents, and the nodes connected to them on a level below are called
children, the topmost node is called the root node, and the bottom-most nodes are called the leave node, each node can have multiple children and a parent except the leave nodes
and the root node respectively
- Graphs: A data structure, with data elements called nodes each node can be connected to multiple other nodes through a link called an edge
What is the difference between a graph and a tree?
Graphs can form a cycle while tress cannot
What are the types of operations that can be performed on a data structure?
There are 6 operations that can be performed on data structures which include:
1. Traversal: When every element in the data structure is visited
2. Inserting: When an element is added to the data structure
3. Deleting: When an element is removed from the data structure
4. Searching: When the position of an element in the data structure is located
5. Sorting: When elements are arranged in a specific order
6. Merged: When multiple data structures are fused together to form a single data structure
What is a function and what are its characteristics?
A function is a self-contained block of code, that can be invoked multiple times throughout a program, its characteristics include the following:
1. Modularity: Fuctions allow code to be broken down into smaller parts that perform specific tasks
2. Reusability: Once a function is defined it can be used multiple times throughout a program
3. Input/Output: Functions take in inputs as parameters and can return output
4. Scope: Variables created within a function, can only be accessed from within that function
5. Signature: Functions have a signature that includes their: Name, Input Parameters, and the data type of the value they return
What are some advantages of functions?
- They make modularity possible making code more readable, maintainable and manageable
- They are reusable, which reduces code duplication
