Introduction to Arrays

Arrays are one of the fundamental data structures in computer science. They are a collection of elements of the same type, grouped together under a single name. One of the key properties of arrays is that they have a fixed size, meaning the number of elements they can hold is determined at the time of declaration.

In C++, arrays are represented by contiguous blocks of memory, where each element occupies a specific position. The elements of an array are accessed through their indices, which start from 0.

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Arrays in C++
6    int numbers[5] = {1, 2, 3, 4, 5};
7    cout << "The first element is: " << numbers[0] << endl;
8    return 0;
9}

In the above example, we declare an array called numbers with 5 elements and initialize them with values 1, 2, 3, 4, and 5. To access the first element of the array, we use the index 0 and print its value.

Arrays provide efficient random access to elements, making them suitable for scenarios where elements need to be accessed by their indices, such as storing a collection of data points, like the coordinates of pixels in an image.

Arrays also support various operations like insertion, deletion, and sorting, which we will explore in detail in the next screens.

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

    // Arrays in C++

    int numbers[5] = {1, 2, 3, 4, 5};

    cout << "The first element is: " << numbers[0] << endl;

    return 0;

}

Arrays Operations

Arrays are a versatile data structure that allows us to efficiently perform various operations such as insertion, deletion, and searching.

Insertion

To insert an element at a specific index in an array, we need to shift all the elements after that index to the right and then assign the new value to the desired index. Here's an example in C++:

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Insertion
6    int numbers[5] = {1, 2, 3, 4, 5};
7    int index = 2;
8    int newValue = 10;
9    for (int i = 4; i > index; i--) {
10        numbers[i] = numbers[i - 1];
11    }
12    numbers[index] = newValue;
13
14    // Print the array
15    for (int i = 0; i < 5; i++) {
16        cout << numbers[i] << " ";
17    }
18    cout << endl;
19
20    return 0;
21}

In the above example, we have an array numbers with 5 elements. We want to insert the value 10 at index 2. By shifting the elements after index 2 to the right, we create space for the new value and then assign it to the desired index.

Deletion

To delete an element at a specific index in an array, we simply need to shift all the elements after that index to the left. Here's an example in C++:

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Deletion
6    int numbers[5] = {1, 2, 3, 4, 5};
7    int index = 3;
8    for (int i = index; i < 4; i++) {
9        numbers[i] = numbers[i + 1];
10    }
11
12    // Print the array
13    for (int i = 0; i < 4; i++) {
14        cout << numbers[i] << " ";
15    }
16    cout << endl;
17
18    return 0;
19}

In the above example, we have an array numbers with 5 elements. We want to delete the element at index 3. By shifting the elements after index 3 to the left, we effectively remove the element from the array.

Searching

To search for a specific value in an array, we can iterate through the elements and compare each one with the search value. If we find a match, we can return the index. Here's an example in C++:

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Searching
6    int numbers[5] = {1, 2, 3, 4, 5};
7    int searchValue = 4;
8    int foundIndex = -1;
9    for (int i = 0; i < 5; i++) {
10        if (numbers[i] == searchValue) {
11            foundIndex = i;
12            break;
13        }
14    }
15
16    cout << "The element " << searchValue << " is found at index " << foundIndex << endl;
17
18    return 0;
19}

In the above example, we have an array numbers with 5 elements. We want to search for the value 4. By iterating through the elements and comparing each one with the search value, we can find the index at which the element is present.

Arrays operations like insertion, deletion, and searching are fundamental in many algorithms and applications. Understanding these operations is essential for efficient programming and problem-solving.

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

int main() {

    // Array Operations in C++

​

    // Insertion

    int numbers[5] = {1, 2, 3, 4, 5};

    int index = 2;

    int newValue = 10;

    for (int i = 4; i > index; i--) {

        numbers[i] = numbers[i - 1];

    }

    numbers[index] = newValue;

​

    // Deletion

    index = 3;

    for (int i = index; i < 4; i++) {

        numbers[i] = numbers[i + 1];

    }

​

    // Searching

    int searchValue = 4;

    int foundIndex = -1;

    for (int i = 0; i < 5; i++) {

        if (numbers[i] == searchValue) {

            foundIndex = i;

            break;

        }

Linked lists are a fundamental data structure used in programming and computer science. They are particularly useful when dealing with data that needs to be dynamically allocated and can grow or shrink in size.

Unlike arrays, which store elements in contiguous memory locations, linked lists store elements in separate nodes. Each node contains a value and a reference (or pointer) to the next node in the list.

Here's an example of a linked list in C++:

1#include <iostream>
2using namespace std;
3
4struct Node {
5    int data;
6    Node* next;
7};
8
9int main() {
10    // Create nodes
11    Node* head = new Node;
12    Node* second = new Node;
13    Node* third = new Node;
14
15    // Assign data values
16    head->data = 1;
17    second->data = 2;
18    third->data = 3;
19
20    // Connect nodes
21    head->next = second;
22    second->next = third;
23    third->next = nullptr;
24
25    // Print linked list
26    Node* current = head;
27    while (current != nullptr) {
28        cout << current->data << " ";
29        current = current->next;
30    }
31    cout << endl;
32
33    // Clean up memory
34    delete head;
35    delete second;
36    delete third;
37
38    return 0;
39}

In the above example, we create a linked list with three nodes: head, second, and third. Each node contains an integer value and a pointer to the next node. The last node's pointer is set to nullptr to indicate the end of the list.

Linked lists have several advantages over arrays, including:

• Dynamic size: Linked lists can grow or shrink in size as needed, unlike arrays that have a fixed size.
• Efficient insertions and deletions: Inserting or deleting an element in a linked list only requires updating a few pointers, whereas arrays may require shifting elements.
• Flexibility: Linked lists can easily handle data of varying sizes and structures.

It's important to note that linked lists also have some drawbacks. They require extra memory for the pointer references, sequential access is slower compared to arrays, and random access is not possible without traversing the list.

Understanding the concept of linked lists is essential for mastering data structures and building more complex algorithms and applications.

In this lesson, we will explore the operations that can be performed on a linked list. Linked list operations include insertion, deletion, and searching for nodes in the list. These operations are essential for manipulating and managing linked lists in various applications.

Let's start with the insertion operation. To insert a node at the beginning of a linked list, we can follow these steps:

1. Create a new node with the desired data.
2. Set the next pointer of the new node to point to the current head of the linked list.
3. Update the head pointer to point to the new node.

Here's an example of how the insertion operation can be implemented in C++:

1#include <iostream>
2using namespace std;
3
4// Node structure for linked list
5struct Node {
6    int data;
7    Node* next;
8};
9
10// Function to insert a node at the beginning of the linked list
11void insertAtBeginning(Node** head, int newData) {
12    // Create a new node
13    Node* newNode = new Node;
14
15    // Assign data to the new node
16    newNode->data = newData;
17
18    // Set the next pointer of the new node to the current head
19    newNode->next = *head;
20
21    // Update the head to point to the new node
22    *head = newNode;
23}
24
25int main() {
26    // Initialize an empty linked list
27    Node* head = nullptr;
28
29    // Insert nodes at the beginning of the linked list
30    insertAtBeginning(&head, 3);
31    insertAtBeginning(&head, 2);
32    insertAtBeginning(&head, 1);
33
34    // Print the linked list
35    Node* temp = head;
36    while (temp != nullptr) {
37        cout << temp->data << " ";
38        temp = temp->next;
39    }
40    cout << endl;
41
42    return 0;
43}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Node structure for linked list

struct Node {

    int data;

    Node* next;

};

​

// Function to insert a node at the beginning of the linked list

void insertAtBeginning(Node** head, int newData) {

    // Create a new node

    Node* newNode = new Node;

​

    // Assign data to the new node

    newNode->data = newData;

​

    // Set the next pointer of the new node to the current head

    newNode->next = *head;

​

    // Update the head to point to the new node

    *head = newNode;

}

​

// Function to delete a node from the linked list

void deleteNode(Node** head, int key) {

    // Store the head node

    Node* temp = *head;

    Node* prev = nullptr;

Introduction to Stacks

In this lesson, we will explore the concept of stacks and their applications in various fields, including robotics and computer vision.

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Think of it as a stack of books where you can only add or remove books from the top. The element that is added last is the first one to be removed.

Stacks have several real-life applications that align with your interests in robotics and computer vision. For example, you can use a stack to simulate the behavior of robotic arms that stack objects. The last object placed on top of the stack is the first one to be removed, just like with a stack data structure.

Let's take a look at the C++ code snippet below, which demonstrates the implementation of a stack using an array:

1#include <iostream>
2using namespace std;
3
4const int MAX_SIZE = 100;
5
6class Stack {
7private:
8    int top;
9    int stack_array[MAX_SIZE];
10
11public:
12    Stack() {
13        top = -1;
14    }
15
16    bool is_empty() {
17        return (top == -1);
18    }
19
20    bool is_full() {
21        return (top == MAX_SIZE - 1);
22    }
23
24    void push(int value) {
25        if (is_full()) {
26            cout << "Stack overflow!" << endl;
27            return;
28        }
29
30        stack_array[++top] = value;
31    }
32
33    int pop() {
34        if (is_empty()) {
35            cout << "Stack underflow!" << endl;
36            return -1;
37        }
38
39        return stack_array[top--];
40    }
41};
42
43int main() {
44    Stack stack;
45
46    // Pushing elements onto the stack
47    stack.push(10);
48    stack.push(20);
49    stack.push(30);
50
51    // Popping elements from the stack
52    cout << stack.pop() << endl;
53    cout << stack.pop() << endl;
54    cout << stack.pop() << endl;
55
56    return 0;
57}

In the code snippet above, we define a Stack class that uses an array to implement the stack data structure. The push function adds an element to the top of the stack, and the pop function removes and returns the top element from the stack.

Now that you have a basic understanding of stacks and their applications, let's move on to exploring more advanced stack operations.

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

    // Stack implementation here

    return 0;

}

Stack Operations

In this section, we will focus on implementing basic stack operations such as push, pop, and peek.

To begin, let's define the Stack class in C++ that will represent our stack data structure. The Stack class will have a fixed size and will use an array to store the elements.

1#include <iostream>
2using namespace std;
3
4const int MAX_SIZE = 100;
5
6class Stack {
7private:
8    int top;
9    int stack_array[MAX_SIZE];
10
11public:
12    Stack() {
13        top = -1;
14    }
15
16    bool is_empty() {
17        return (top == -1);
18    }
19
20    bool is_full() {
21        return (top == MAX_SIZE - 1);
22    }
23
24    void push(int value) {
25        if (is_full()) {
26            cout << "Stack overflow!" << endl;
27            return;
28        }
29
30        stack_array[++top] = value;
31    }
32
33    int pop() {
34        if (is_empty()) {
35            cout << "Stack underflow!" << endl;
36            return -1;
37        }
38
39        return stack_array[top--];
40    }
41
42    int peek() {
43        if (is_empty()) {
44            cout << "Stack is empty!" << endl;
45            return -1;
46        }
47
48        return stack_array[top];
49    }
50};

xxxxxxxxxx

#include <iostream>

using namespace std;

​

// Define the Stack class

​

int main() {

  // Create a Stack object

​

  // Perform stack operations

​

  return 0;

}

Introduction to Queues

A queue is a fundamental data structure that follows the FIFO (First-In-First-Out) principle. Just like how people wait in a queue for their turn, a queue data structure works similarly. It is used to store a collection of elements in a linear order where the addition of new elements happens at one end and the removal of elements occurs at the other end.

In a queue, new elements are always added to the rear end of the queue, and existing elements are always removed from the front end of the queue.

Queues have several real-life applications. For example, an operating system uses a queue to manage processes that are waiting to be executed. Printers use queues to manage print spooling, ensuring that print jobs are handled in the order they are received.

To implement a queue, we can use an array or a linked list. In this lesson, we will focus on implementing a queue using an array.

Let's take a look at the C++ implementation of a queue using an array:

1#include <iostream>
2using namespace std;
3
4// Queue implementation using an array
5
6class Queue {
7private:
8    int front; // front pointer
9    int rear; // rear pointer
10    int capacity; // capacity of the queue
11    int* queue; // dynamic array to store the elements
12
13public:
14    Queue(int size) {
15        capacity = size;
16        front = 0;
17        rear = -1;
18        queue = new int[capacity];
19    }
20
21    // Other member functions
22    // ...
23};

In the above implementation, we have defined a Queue class that uses an array to store the elements. The class has private member variables front, rear, capacity, and queue. The front variable points to the front element of the queue, the rear variable points to the rear element of the queue, the capacity variable represents the maximum number of elements the queue can hold, and the queue variable is a dynamic array to store the elements.

The implementation also includes member functions for basic queue operations such as is_empty() to check if the queue is empty, is_full() to check if the queue is full, and enqueue() and dequeue() to add and remove elements respectively.

Feel free to modify the code and experiment with different operations on the queue to get a better understanding of how it works.

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Queue implementation using an array

​

class Queue {

private:

    int front; // front pointer

    int rear; // rear pointer

    int capacity; // capacity of the queue

    int* queue; // dynamic array to store the elements

​

public:

    Queue(int size) {

        capacity = size;

        front = 0;

        rear = -1;

        queue = new int[capacity];

    }

​

    bool is_empty() {

        return (rear == -1);

    }

​

    bool is_full() {

        return (rear == capacity - 1);

    }

​

    void enqueue(int value) {

Queue Operations

In the previous screen, we learned about the basics of queues and how to implement a queue using an array. Now let's explore the fundamental operations that we can perform on a queue.

The main operations that we can perform on a queue are:

• enqueue(): Adds an element to the rear of the queue.
• dequeue(): Removes the front element from the queue and returns it.
• peek(): Returns the front element of the queue without removing it.

Let's take a look at the C++ implementation of these operations:

1#include <iostream>
2using namespace std;
3
4class Queue {
5private:
6    int front;
7    int rear;
8    int capacity;
9    int* queue;
10
11public:
12    Queue(int size) {
13        capacity = size;
14        front = 0;
15        rear = -1;
16        queue = new int[capacity];
17    }
18
19    void enqueue(int element) {
20        // Check if the queue is full
21        if (rear == capacity - 1) {
22            cout << "Queue is full!" << endl;
23            return;
24        }
25
26        // Add element to the rear
27        queue[++rear] = element;
28        cout << "Enqueued: " << element << endl;
29    }
30
31    int dequeue() {
32        // Check if the queue is empty
33        if (front > rear) {
34            cout << "Queue is empty!" << endl;
35            return -1;
36        }
37
38        // Remove and return the front element
39        int element = queue[front++];
40        cout << "Dequeued: " << element << endl;
41        return element;
42    }
43
44    int peek() {
45        // Check if the queue is empty
46        if (front > rear) {
47            cout << "Queue is empty!" << endl;
48            return -1;
49        }
50
51        // Return the front element
52        return queue[front];
53    }
54};
55
56int main() {
57    Queue queue(5);
58    queue.enqueue(10);
59    queue.enqueue(20);
60    queue.enqueue(30);
61    queue.enqueue(40);
62    queue.enqueue(50);
63    queue.enqueue(60); // Queue is full!
64
65    queue.dequeue();
66    queue.dequeue();
67    queue.dequeue();
68    queue.dequeue();
69    queue.dequeue();
70    queue.dequeue(); // Queue is empty!
71
72    return 0;
73}

xxxxxxxxxx

#include <iostream>

using namespace std;

​

// Queue implementation using an array

​

class Queue {

private:

    int front; // front pointer

    int rear; // rear pointer

    int capacity; // capacity of the queue

    int* queue; // dynamic array to store the elements

​

public:

    Queue(int size) {

        capacity = size;

        front = 0;

        rear = -1;

        queue = new int[capacity];

    }

​

    // Other member functions

    // ...

};

​

int main() {

    // replace with your c++ logic here

    return 0;

}

Introduction to Trees

Trees are hierarchical data structures made up of nodes. Each node has a value and can have zero or more child nodes. The topmost node is called the root node, and it does not have a parent node.

Trees have various properties that make them useful for organizing and structuring data:

1. Hierarchical Structure: Trees are organized in a hierarchical structure, where each node can have child nodes.

2. Root Node: The topmost node in a tree is called the root node. It is the starting point of the tree and does not have a parent node.

3. Parent Node: A node that has child nodes is called a parent node. It is located above its child nodes in the hierarchy.

4. Child Node: A node that is below another node in the hierarchy is called a child node.

5. Leaf Node: A node that does not have any child nodes is called a leaf node or a terminal node. It is located at the bottom of the tree.

6. Depth: The depth of a node is the number of edges between the node and the root node. The depth of the root node is 0.

7. Height: The height of a node is the number of edges in the longest path from the node to a leaf node.

Trees have various applications in computer science, such as representing hierarchical relationships, organizing data in a hierarchical manner, searching and sorting, and implementing data structures like binary search trees.

Let's take a look at an example of a binary tree:

1        1
2      /   \
3     2     3
4    / \   / \
5   4   5 6   7

In this binary tree:

• Node 1 is the root node
• Node 2 is the left child of node 1
• Node 3 is the right child of node 1
• Node 4 is the left child of node 2
• Node 5 is the right child of node 2
• Node 6 is the left child of node 3
• Node 7 is the right child of node 3

xxxxxxxxxx

}

#include <iostream>

using namespace std;

int main() {

  // Trees are hierarchical data structures made up of nodes.

  // Each node has a value and can have zero or more child nodes.

  // The topmost node is called the root node,

  // and it does not have a parent node.

​

  // Trees have various properties that make them useful

  // for organizing and structuring data:

​

  // 1. Hierarchical Structure: Trees are organized in a

  //    hierarchical structure, where each node can have

  //    child nodes.

​

  // 2. Root Node: The topmost node in a tree is called

  //    the root node. It is the starting point of the tree

  //    and does not have a parent node.

​

  // 3. Parent Node: A node that has child nodes is called

  //    a parent node. It is located above its child nodes

  //    in the hierarchy.

​

  // 4. Child Node: A node that is below another node in the

  //    hierarchy is called a child node.

​

  // 5. Leaf Node: A node that does not have any child nodes

  //    is called a leaf node or a terminal node. It is located

  //    at the bottom of the tree.

Binary Trees

Binary trees are a specific type of tree where each node has at most two child nodes, referred to as the left child and the right child. Unlike a linked list, which has a linear structure, a binary tree has a hierarchical structure.

Binary trees have various properties and operations that make them useful in computer science and robotics. For example, binary trees can be used to represent and solve problems in computer vision, such as image recognition and object detection.

Here's an example of a binary tree:

1        5
2      /   \
3     3     7
4    / \     
5   2   4    

In this binary tree, the root node is 5. The left child of the root node is 3, and the right child is 7. The left child of 3 is 2, and the right child of 3 is 4.

Binary trees have various operations that can be performed on them, such as:

• Insertion: Adding a new node to the tree
• Deletion: Removing a node from the tree
• Search: Searching for a specific value in the tree
• Traversal: Visiting every node in the tree in a specific order, like inorder, preorder, or postorder traversal

Using C++, you can implement a binary tree using the following code snippet:

1#include <iostream>
2using namespace std;
3
4struct Node {
5  int data;
6  Node* left;
7  Node* right;
8};
9
10// Function to create a new node
11Node* createNode(int data) {
12  Node* newNode = new Node();
13  if (!newNode) {
14    return NULL;
15  }
16  newNode->data = data;
17  newNode->left = newNode->right = NULL;
18  return newNode;
19}
20
21int main() {
22  // Create a root node
23  Node* root = createNode(5);
24  if (!root) {
25    return 0;
26  }
27
28  // Create child nodes
29  root->left = createNode(3);
30  root->right = createNode(7);
31  root->left->left = createNode(2);
32  root->left->right = createNode(4);
33
34  cout << "Binary Tree created successfully!";
35
36  return 0;
37}

In this code snippet, a binary tree is created with a root node containing the value 5. Child nodes are then created and linked to the root node, forming the complete binary tree.

Binary trees are a fundamental data structure in computer science and can be used to solve a wide range of problems. Understanding binary trees is essential for anyone interested in robotics and computer vision.

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

  // Binary Tree code goes here

}

Graphs

Graphs are a fundamental data structure in computer science that represent a collection of nodes (also known as vertices) connected by edges. They are used to model relationships between objects or entities.

Graphs can be visualized as a set of points connected by lines. Each point represents a node, and the lines represent the edges connecting the nodes.

For example, imagine you want to represent the connections between different social media users. You can use a graph where each user is a node, and the relationships between users (friendships, follows, etc.) are the edges.

Graphs can be directed or undirected. In a directed graph, the edges have a specific direction, while in an undirected graph, the edges have no direction.

Graphs have various applications in computer science, including:

• Social networks and relationship modeling
• Routing algorithms in computer networks
• Recommendation systems
• Genetic algorithms

To represent a graph in C++, you can use various data structures such as adjacency matrix, adjacency list, or an edge list. The choice of data structure depends on the specific requirements of your application.

Here's an example of representing a graph using an adjacency matrix in C++:

1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Function to add an edge to the graph
6void addEdge(vector<vector<int>>& graph, int u, int v) {
7  graph[u][v] = 1;
8  graph[v][u] = 1;
9}
10
11int main() {
12  int numNodes = 5;
13
14  // Create an empty graph
15  vector<vector<int>> graph(numNodes, vector<int>(numNodes, 0));
16
17  // Add edges to the graph
18  addEdge(graph, 0, 1);
19  addEdge(graph, 0, 4);
20  addEdge(graph, 1, 2);
21  addEdge(graph, 2, 3);
22  addEdge(graph, 3, 4);
23
24  cout << "Graph created successfully!";
25
26  return 0;
27}

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

  // code logic here

}