Nangarhar University of computer science faculty
Name:faizanullah "mimlawal"
f/N:Ahsanullah
Dep: software
Class:4th 7th semester
Teacher: sir Rahmanullah "shirzad"
Ph: 0789354632
1st assignment of algorithm subject.
## 1. Definitions
- **Algorithm**: A step-by-step procedure or formula for solving a problem. It
consists of a finite sequence of well-defined instructions to achieve a specific goal.
- **Algorithm (repeated)**: This appears to be a repetition of the first term. It
would still refer to the same concept as above.
### 2. What is an Algorithm?
An algorithm is a systematic, logical approach to solving a problem. It is a finite
set of instructions or rules that, when followed, lead to the solution of a specific
problem or task. Algorithms can be expressed in various forms, such as natural
language, flowcharts, or programming languages.
### 3. Characteristics of an Algorithm
- **Finiteness**: An algorithm must always terminate after a finite number of
steps.
- **Definiteness**: Each step of the algorithm must be precisely defined and
unambiguous.
- **Input**: An algorithm can have zero or more inputs, which are the values
taken to perform operations.
- **Output**: An algorithm must produce at least one output, which is the result
of the operations performed.
- **Effectiveness**: All operations must be basic enough to be performed, in
principle, by a person using paper and pencil.
### 4. Performance of a Program
The performance of a program refers to how efficiently it executes and how it
utilizes resources. It can be measured in terms of:
- **Time Complexity**: How the execution time of an algorithm increases with
the size of the input. For example:
- A linear search has a time complexity of O(n).
- A binary search has a time complexity of O(log n).
- **Space Complexity**: The amount of memory space required by the algorithm
as a function of the input size. For example:
- A sorting algorithm like Bubble Sort may require O(1) additional space.
- Merge Sort requires O(n) additional space.
### 5. Algorithm Design Goals
- **Correctness**: The algorithm should produce the correct output for all
possible valid inputs.
- **Efficiency**: The algorithm should use the least amount of time and space.
- **Simplicity**: The algorithm should be easy to understand and implement.
- **Scalability**: The algorithm should work effectively with increasing input
sizes.
- **Robustness**: The algorithm should handle unexpected or invalid inputs
gracefully.
### 6. Classification of Algorithms
Algorithms can be classified based on several criteria:
- **Based on Design Methodology**:
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithms
- Backtracking
- **Based on Purpose**:
- Searching Algorithms
- Sorting Algorithms
- Graph Algorithms
- **Based on Complexity**:
- Polynomial Time Algorithms
- Exponential Time Algorithms
### 7. Difference between Algorithm, Pseudocode & Program
- **Algorithm**: A high-level description of a step-by-step process to solve a
problem.
- **Pseudocode**: A way to express an algorithm in a structured but informal
manner, resembling programming language syntax without being tied to any
specific language.
- **Program**: A complete implementation of an algorithm written in a specific
programming language that can be executed by a computer.
### 8. Pseudocode Examples
Example 1: Finding the maximum number in a list.
```
Function FindMax(list)
max = list[0]
For each item in list
If item > max then
max = item
Return max
End Function
```
Example 2: Calculating the factorial of a number.
```
Function Factorial(n)
If n == 0 then
Return 1
Else
Return n * Factorial(n - 1)
End If
End Function
10. Comments and Code Structure
1. **Comments**:
- Comments in code are annotations used to explain what the code is doing,
making it easier for others (or yourself) to understand later. In many
programming languages, comments begin with `//` and continue until the end of
the line. For example:
```
// This is a single-line comment
int x = 5; // This initializes x to 5
```
2. **Blocks**:
- Blocks of code are indicated with matching braces `{}`. A block can contain a
collection of simple statements and is often used to define the body of functions
or control structures (like loops and conditionals). For example:
```
if (x > 0) {
// This block runs if x is positive
print("Positive");
}
```
3. **Identifiers**:
- An identifier is a name given to a variable, function, or any other user-defined
item. Identifiers begin with a letter (A-Z, a-z) or an underscore (_) and may be
followed by letters, digits (0-9), or underscores. The data types of variables are
not explicitly declared in some languages and can be inferred from the context.
For example:
```
int count; // 'count' is an identifier of type integer
```
- Data types can include simple types like integer, float, char, boolean, etc.
Compound data types can be formed using structures or records. Here’s an
example of a record:
```
node = record {
datatype data1;
datatype data2;
link next; // Pointer to the next node
}
```
### 9. Recursive Algorithms
A recursive algorithm is one that calls itself in order to solve smaller instances of
the same problem. It typically contains:
- **Base Case**: A condition under which the recursion stops.
- **Recursive Case**: The part of the algorithm that includes the recursive call.
#### Examples of Recursive Algorithms:
1. **Factorial Calculation**:
```
Function Factorial(n)
If n == 0 then
Return 1
Else
Return n * Factorial(n - 1)
End Function
```
2. **Fibonacci Sequence**:
```
Function Fibonacci(n)
If n <= 1 then
Return n
Else
Return Fibonacci(n - 1) + Fibonacci(n - 2)
End Function
```
3. **Tower of Hanoi**:
```
Function TowerOfHanoi(n, source, target, auxiliary)
If n == 1 then
Move disk from source to target
Else
TowerOfHanoi(n - 1, source, auxiliary, target)
Move disk from source to target
TowerOfHanoi(n - 1, auxiliary, target, source)
End Function
```
4. **Binary Search**:
```
Function BinarySearch(arr, left, right, target)
If left > right then
Return -1
mid = (left + right) / 2
If arr[mid] == target then
Return mid
Else if arr[mid] > target then
Return BinarySearch(arr, left, mid - 1, target)
Else
Return BinarySearch(arr, mid + 1, right, target)
End Function
```
### Space Complexity and Time Complexity
#### Space Complexity:
Space complexity refers to the amount of memory used by an algorithm as a
function of the size of the input. It includes:
- **Fixed Part**: Space required for constants, simple variables, etc.
- **Variable Part**: Space required by dynamic memory allocation, stack space
for recursion.
#### Time Complexity:
Time complexity refers to the computational time an algorithm takes to complete
as a function of the input size, typically expressed using Big O notation.
#### Examples of Complexity:
1. **Linear Search**:
- Time Complexity: O(n)
- Space Complexity: O(1) (in-place search)
2. **Binary Search**:
- Time Complexity: O(log n)
- Space Complexity: O(1) (in-place search)
3. **Bubble Sort**:
- Time Complexity: O(n^2)
- Space Complexity: O(1) (in-place sorting)
4. **Merge Sort**:
- Time Complexity: O(n log n)
- Space Complexity: O(n) (requires additional space for merging)
