Data Structures & Algorithms

Data Structures and Algorithms Study Notes

Introduction to Data Structure

• Data Structures is defined as the grouping of data elements for efficient storage and organization in a computer, enabling efficient usage.
• Arrays, linked lists, stacks, and queues are examples of data structures.
• Data structures are used in many areas of computer science, such as Artificial intelligence, Graphics, and Compiler design.

Importance of Data Structures

• The relationship between data elements within memory can be understood, with the help of Data structures.
• Aids in data analysis, storage, and organization in a mathematical style.

Data and Information

• Data consists of raw, unorganized facts about a condition, event, idea, or entity,
• Information refers to facts that are refined by processing.
• Data are raw text and numbers, while information is processed and interpreted data.

Objectives of Studying Data Structures

• To discuss primitive and composite data types.
• To explain linear and non-linear data structures.
• To analyze abstract data types.

Types of Data Structures

• Primitive data structures operate directly on machine instructions.
• Integer, character, and string are all primitive data types.
• Non-primitive data structures are complex and are derived from primitive data structures.
• A linear data structure is where elements are arranged in a linear order.
• In linear data structures, each element has a successor and predecessor (except the first and last).
• Non-linear data structures do not form a sequence.

Examples of Linear Data Structures

• Arrays are collections of similar data types where each item is an element, with elements sharing a variable name but having unique index numbers (subscripts).
• Linked Lists are linear which maintain a list in memory and store nodes at non-contiguous memory locations, with each node containing a pointer to the next adjacent node.
• Stacks are linear lists where insertions and deletions occur at only one end (the "top"), operating according to the Last-In-First-Out (LIFO) principle.
• Queues are linear lists where elements are inserted at the "rear" and deleted from the "front," operating according to the First-In-First-Out (FIFO) principle.

Examples of Non-Linear Data Structures

• Trees are multi-level data structures exhibiting hierarchical relationships among elements (nodes) and are based on parent-child relationships.
• Graphs are pictorial representations of elements (vertices) connected by links (edges).
• Graphs may contain cycles, unlike trees.

Primitive Data Types

• Pre-defined by programming they're readily available for use.

Algorithms

• Procedure with well-defined steps developed for solving a the logic or set of instructions is written ordered to for accomplish certain task.
• Characteristics of an algorithm are, Input, Output, Feasibility, Independent and Unambiguous.
• Major categories of algorithms are Sort and Search.
• Algorithms also include Delete, Insert, and Update.

Algorithm Complexity

• Time complexity the amount of time taken by an algorithm to run as a function of the length of the space.
• Space complexity quantifies the amount of memory space taken by an algorithm to run as a function of the length of the input.
• The performance of an algorithm is measured by Time and Space complexity.

Algorithm Requirements

• Each must have: Specification, Pre-conditions, Description, and Post-conditions.

Algorithm Analysis

• Asymptotic used for defining the mathematical foundation and runtime performance of an algorithm.
• Time required by an algorithm falls under Best Case, Average Case, and Worst Case.

Asymptotic Notations

• Commonly used notations to calculate running time complexity include O Notation i.e. Upper bound, Ω Notation i.e lower bounds, and 0 Notation i.e binds from top and bottom.

Check Your Progress

• Data structure is specialized format for retrieving, storing and organizing data, Time complexity of an Algorithm amount of time to fun as function of length of input Space complexity quantifies the amount of space or memory.

Summary

• Programming languages provide data types, each represented in computer memory.
• Memory needs of a type determine the range of values it can hold.
• Types are either primitive or composite.
• Languages can define user-defined data types.
• Small problems easy to handle relative to large ones
• Modular program makes implementation independent so can be easily modified
• ADT (abstract data type) defines operations logically, without implementation details.
• Model used to organize data in memory is the data structure.
• Must consider simplicity and needed features when choosing the data structure.

Traversing

• Accessing all data elements one by one to process all or some.

Recursion Tree

• Recurrences are represented as a tree to identify the various levels of recursion.

Insertion

• Adding new item to a data structure.

Deletion

• Removing an existing item from a data structure.

Arrays

• Arrays store same-type elements of same length as an collection for data.
• Instead of individual values, declare one array used with index like number{0] lowest address to the first element and increasing by 1.

Objective of Arrays

• Array characterization and Initialization
• Types of Arrays, Single- and Multi-dimensional

Array Characteristics

• Holds items that are the same type item for every item
• Must mention size, and be a constant value not a variable.

Arrays

• Is a Data structure has a group of elements.
• Sorts and searches most commonly used with strings and characters
• Items in an array have adjacent memory allocation with row by row allocation.

Array Intialization

• Declaring items by simultaneously or separately.

Types Of Arrays

• One dimensional i.e, Linear
• Multi- Dimensional i.e Matrix with 2 or 3 dimensions.

Working Array Program code

• Start with specifying max size of the data for an array
• Use integer i for referencing array number
• Use "clrscr()" C code for refreshing the screen that shows the array item, and the code uses print and and scanner formatting "printf" "scanf".

Multi Dimensional Arrays

• Each of them of dimension n has various helps for various subscript values.
• Compiler is maximum limit which is dependent on size.
• 2 sub values to arrange and and display in matrixes
• 2 dimensional arrays use matrix code prototype set by int i, and set to a limit like MAX.

Summary of Arrays

• One of the data types that can store list of items
• Can be defined as a size
• Programmer should access or select element of array
• Only one subscript known as linear-dimensional array.

Key Words For Arrays

Array: static data structure 1D, contains one subscript 2D: array constrains 2 subs

Stacks

• Stack is a linear structure where elements are added and removed at the end of stack.
• Stacks are the first principle to get out if last- in (LIFO) and a also referred to as last-in- first out (LIFO) list.

Objectives Of Stacks

• To Explain stack, related terms and operations.

Stacks Related Terms

• Top is use a variable that points to the top item of top. Initially top set to -1 for null data.

Operations on Stack

• Push;Add
• Pop; Remove
• Peep, Stack Top, isEmpty

Stack Operations

• Using two different functions

1. To create a stack of given capacity
2. Full function

Algorithm for Operations on a Stacks

• Push; Adds with the item; If stack full show overflow
• Pop; Removes with the item: If stack empty; display

Advantages for Stacks

• A stack is easy to be organized in memory using arrays or single linked list.
• Less flexible and efficient, but less memory utilizations, the linked are are dynamic in nature.
• Initial value is set a to point empty stack.

Linked-Stack

• Stack uses top to point ellement
• Stack has new number for overflow can make new effort Key Words/Concepts Stack, OverFlow/Underflow Self Instructional Materials
• ADT collects items to add and removes most recent items.

Recursion

• A way of showing to display

Representation Of Stacks

• Stacks are used to reverse strings in Postfix and Prefix
• This has stack used on the basic of first

Objectives/Applications to Stacks

• To be able to explain what a stacks and app
• And explain Implementation

Reversing Strings

• Characters are push on until string is read
• After which operations result in the reverse of the other string
• Basic way of notation for math

Check questions

• What a Notation, Inflix Postlix stacks

Summary of Stacks

• Stacks use the data type to push each of their first in operations to display

Queues

• Queue is an abstract data structure similar to stacks with open ends

Objectives Of Queues

• Queue operations, representations, types, and applications queues from either end, i.e. double queue
• Applications: ticket counters, etc. New concepts: Enqueue(add items),Dequeue(remove items)
• Concepts of Front and the Rear with initialization

Summary of Queues

• Similar to the memory can be either an array or a single linked list. Linked lists help in the queue reach a max point new slots appear front to queue.