Flowchart
----------
Definition:
A flowchart is a diagrammatic representation of an algorithm or process.
It uses symbols to represent steps and arrows to show the flow of control.
Common Symbols in Flowcharts:
| Symbol | Purpose |
|----------------|----------------------------------|
| Oval | Start/End |
| Rectangle | Process/Instruction |
| Diamond | Decision (Yes/No) |
| Parallelogram | Input/Output |
| Arrow | Flow of control |
Uses of Flowcharts:
- Visualize logic before coding.
- Improve understanding and communication.
- Help in debugging and documentation.
Variables
----------
Definition:
A variable is a named storage location used to hold data in a program.
Its value can change during program execution.
Example (in Python):
age = 20
name = "Alice"
Types of Variables:
- Integer: Holds whole numbers (e.g., x = 10)
- Float: Holds decimal numbers (e.g., price = 99.99)
- String: Holds text (e.g., name = "John")
- Boolean: Holds True or False (e.g., is_valid = True)
Keywords
---------
Definition:
Keywords are reserved words in a programming language.
They have special meanings and cannot be used as variable names.
Examples of Keywords in Python:
if, else, for, while, def, return, True, False, import
Importance:
- Used to write the syntax and structure of programs.
- Misusing a keyword leads to errors.
Linear Search Algorithm
-------------------------
Definition:
Linear Search is a simple searching algorithm that checks each element of a list or
array one by one, from the beginning to the end, until the target element is found or
the list ends.
Steps of Linear Search:
1. Start from the first element.
2. Compare each element with the target value.
3. If a match is found, return the index (or position).
4. If the loop ends without finding the value, return "not found".
Example:
numbers = [5, 12, 7, 20, 3]
target = 20
Python Code:
def linear_search(numbers, target):
for i in range(len(numbers)):
if numbers[i] == target:
return i # returns the index where target is found
return -1 # not found
# Example usage
index = linear_search([5, 12, 7, 20, 3], 20)
print("Element found at index:", index)
Output:
Element found at index: 3
Advantages:
- Very simple and easy to implement.
- Works on unsorted data.
Disadvantages:
- Slow for large datasets (Time complexity: O(n)).
Stack: Operations and Applications
-----------------------------------
Definition:
A stack is a linear data structure that follows the LIFO principle:
Last In, First Out
Stack Operations:
| Operation | Description |
|---------------|-------------------------------------|
| push(item) | Adds an item to the top of the stack |
| pop() | Removes and returns the top item |
| peek() / top()| Returns the top item without removing it |
| isEmpty() | Checks if the stack is empty |
| size() | Returns the number of items |
Example (in Python):
stack = []
stack.append(10) # push
stack.append(20)
print(stack.pop()) # pop -> 20
print(stack[-1]) # peek -> 10
Applications of Stack:
| Application | Explanation |
|-------------------|--------------------------------------------|
| Expression Eval. | Used in infix/postfix/prefix expressions |
| Function Calls | Call stack in programming |
| Undo Mechanism | Used in text editors |
| Backtracking | Algorithms like maze-solving, DFS |
| Syntax Parsing | For checking balanced parentheses |
| Web Browsers | History (back/forward stack) |
What is an Array? Types of Array
---------------------------------
Definition:
An array is a collection of elements stored in contiguous memory locations.
All elements are of the same data type and accessed using an index.
Example in Python:
arr = [10, 20, 30, 40]
print(arr[2]) # Output: 30
Types of Arrays:
1. One-Dimensional Array (1D):
arr = [1, 2, 3, 4]
2. Two-Dimensional Array (2D):
matrix = [[1, 2], [3, 4]]
3. Multi-Dimensional Array:
three_d = [[[1, 2], [3, 4]], [[5, 6], [7, 8]]]
4. Dynamic Array:
Arrays that change size during runtime (e.g., Python lists)
5. Jagged Array:
jagged = [[1, 2], [3, 4, 5], [6]]
Common Operations:
- Access: arr[i]
- Update: arr[i] = new_value
- Traversal: for i in arr
- Search and sort
Binary Search Algorithm and C++ Program
----------------------------------------
Definition:
Binary Search is an efficient algorithm to find an element in a sorted array by
repeatedly dividing the search interval in half.
Algorithm:
1. Set low = 0 and high = size - 1
2. While low <= high:
a. mid = (low + high) / 2
b. If arr[mid] == target, return mid
c. If arr[mid] < target, set low = mid + 1
d. If arr[mid] > target, set high = mid - 1
3. If not found, return -1
C++ Program:
#include <iostream>
using namespace std;
int binarySearch(int arr[], int size, int target) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target)
return mid; // Element found
else if (arr[mid] < target)
low = mid + 1; // Search right half
else
high = mid - 1; // Search left half
}
return -1; // Element not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60};
int size = sizeof(arr) / sizeof(arr[0]);
int target;
cout << "Enter the number to search: ";
cin >> target;
int result = binarySearch(arr, size, target);
if (result != -1)
cout << "Element found at index: " << result << endl;
else
cout << "Element not found in the array." << endl;
return 0;
}
Notes:
- Time Complexity: O(log n)
- Works only on sorted arrays
