Understanding Data Structures and Algorithms

• Data structures organize data for effective operations and storage.
• Data structures are programmed to store ordered data for easy operation.
• Well-designed data structures reduce complexity and increase efficiency.

Characteristics of a Data Structure

• Correctness ensures the data structure implements its interface correctly.
• Time complexity refers to the running or execution time of data structure operations, which should be as small as possible.
• Space complexity refers to minimizing memory usage of a data structure operation.

Need for Data Structure

• Data structures help manage complexity in data-rich applications.
• Data structures can reduce the number of items that need to be searched.
• Data structures optimize how data is organized so that required data can be searched instantly.

What is an Algorithm?

• Algorithms provide a step-by-step procedure with instructions to achieve a desired output.
• Algorithms are language-independent.
• In computer programming, an algorithm consists of well-defined instructions to solve a particular problem, taking input(s) and producing a desired output.
• Example algorithm: add two numbers by taking inputs, adding with '+', and displaying the result.
• An example of an algorithm is a set of instructions to make an omelette

Qualities of a Good Algorithm

• A good algorithm should have precisely defined inputs and outputs.
• Each step in the algorithm should be clear and unambiguous.
• Algorithms should be effective in problem-solving.
• An algorithm should be written in a way that it can be used in different programming languages, without including computer code

Categories of Algorithms

• Searching algorithms find items in a data structure.
• Sorting algorithms sort items in a certain order.
• Insertion algorithms insert items into data structure.
• Update algorithms update existing items in a data structure.
• Deletion algorithms delete existing items from a data structure.

Characteristics of an Algorithm

• Algorithms must be unambiguous and clear, with each step leading to only one interpretation.

• An algorithm can have zero or more inputs.

• An algorithm should have at least one output that matches the desired result.

• Algorithms must terminate after a finite number of steps (finiteness).

• Algorithms should be feasible with the available resources

• Algorithms should be independent of any specific programming code.

• Example algorithm 1: Add two numbers entered by the user by taking two nums as input, adding them together and displaying the sum.

• Example algorithm 2: Find the largest number among three numbers by taking three values as input, reading them comparing them and displaying the largest variable.

• A good algorithm must be correct, efficient, and comprehensible.

Recipes

• Following a recipe is a type of algorithm that results in a predictable outcome.

Sorting Papers

• Sorting papers is a simple task that uses algorithmic thinking and simplifies the organizational process.

Types of Data Structure

• Data structures are categorized into linear and non-linear types.

Linear Data Structures

• In linear data structures, elements are arranged in sequence
• Linear data structures are easy to implement when elements are arranged in order.
• As program complexity increases, linear data structures may not be the best choice

Array data structure

• Elements are located in continuous memory.
• All elements are the same type.

Stack Data Structure

• Elements are stored in the LIFO principle so that the last element to be stored is the first element to be removed.

Queue Data Structure

• Elements are stored in the FIFO principle where the first element stored will be removed first.

Linked List Data Structure

• Data elements are connected through a series of nodes.
• Each node contains data items and the address to the next node.

Non-linear data structures

• Elements are not arranged in a particular sequence but are arranged in a hierarchical order where elements can be connected to one or more elements
• Non-linear data structures are further divided into graph and tree-based data structures.
• Graph data structure: each node is called vertex and each vertex is connected to other vertices through edges
• Tree data structure: Like a graph, a tree is also a collection of vertices and edges with only one edge between two vertices

Linear vs. Non-linear Data Structures

• Linear data structures arrange items sequentially, while non-linear structures use a hierarchical manner.
• Linear structures have elements in a single layer, while non-linear structures have elements at different layers.
• Linear structures can be traversed in a single pass, while non-linear structures require multiple runs.
• Memory utilization is not efficient in linear structures, while non-linear structures utilize memory efficiently depending on the need.
• Time complexity increases with data size in linear structures but remains the same in non-linear structures.
• Examples of linear structures: Arrays, Stack, Queue.
• Examples of non-linear structures: Tree, Graph, Map.