Data Structures and Algorithms

• Data structures organize data within a computer's memory
• Algorithms provide step-by-step instructions to solve problems

Computer Basics

• A computer executes tasks based on step-by-step procedures
• These procedures, called algorithms, enable computers to perform calculations and store/retrieve data efficiently
• The primary function of a computer involves efficient data storage and retrieval

Data Storage in Computers

• Computer memory is split into addressable units, but searching for free units is costly
• Studying data storage and retrieval methods is crucial for efficiency

Understanding Data Structures

• A data structure defines how data is arranged in computer memory
• Includes: how to store object collections, allowed operations, related algorithms, and optimization

Data Storage Methods

• Data in a computer is stored linearly or non-linearly
• Linear structures include Linked lists, Queues, and Stacks
• Non-linear structures include Trees and Graphs

Steps for Selecting a Data Structure

• Analyze the problem to determine the basic operations that must be supported
• Quantify the resource constraints for each operation
• Select the data structure that best meets these requirements

Applications of Data Structures

• Google uses data structures to quickly find pages containing search terms
• Data structures help find the quickest way to broadcast a message across a network
• Operating systems track memory (disk/RAM) availability using data structures

Data Types Overview

• Different data types occupy varying memory and support unique operations
• A mechanism known as the "data type" system addresses these issues
• A data type defines the type of data to be stored in memory

Data Type Purpose

• They establish size for data/items and possible operations
• Data types are categorized as primitive/built-in and derived/user-defined

Data Type Categories

• Primitive types consist of numeric and non-numeric types
• Numeric types are integer and floating-point
• Non-numeric types are character, string, and Boolean data types
• Derived types are classes, structures, interfaces, and arrays

Built-in and User-Defined Data Types

• Built-in data types include int, char, float, double, bool, etc
• User-defined data types may include structures and classes

Structures vs. Classes

• Classes feature data members and operations controlling the data

Abstract Data Types (ADTs)

• User-defined data types create ADTs
• It's a logical view of data in computer memory, modeling items with characteristics and operations

Data Abstraction

• This involves modeling or constructing a logical view/picture of an item
• User-defined data types like class types then map this abstract view into a computer program

ADT Definition

• It's a set of objects with operations or the externally defined data type holding data and related operations
• It's called abstract because the internal data storage and operation implementation are not specified

Algorithm Definition

• An algorithm is a series of computational steps for solving a problem
• A program/software combines data structures with algorithms

Algorithm Properties

• Finiteness: Must complete after a finite number of steps
• Definiteness: Each step is clear, leaving no room for interpretation
• Feasibility: Must be possible with available resources
• Correctness: Must compute the correct results for all legal inputs
• Completeness: Must solve the problem completely
• Input/output: Must have a specified number of input and output values.

Algorithm Properties

• Sequence: Each step has unique preceding and succeeding steps, with clearly noted start and halt indicators
• Language Independence: Must not rely on a specific programming language
• Effectiveness: Each step must be performed precisely and within a finite timeframe
• Efficiency: Must solve with minimal time and space requirements.
• Generality: Should be valid for all possible inputs

Algorithm Analysis Overview

• Algorithm analysis assesses computing time and space for different algorithms
• It is the study of program performance and resource usage
• The process involves establishing the function T(n) or S(n) for a given algorithm

Computer Resources

• Running Time
• Memory Usage
• Communication Bandwidth

Algorithm Performance Analysis

• Performance involves measuring best, average, and worst-case scenarios for a given algorithm
• These scenarios utilize notations like (Ο,Ω,Θ,0,0) employing both formal and informal operation-counting methods

Complexity of Algorithms

• Complexity reflects an algorithm's efficiency relative to the amount of data it processes
• This is described by the functions T(n) for time or S(n) for space

Time and Space Functions

• T(n): Indicates the time complexity of an algorithm for 'n' inputs
• S(n): Indicates the memory space complexity of an algorithm for 'n' inputs

Measuring Algorithm Complexity

• Time complexity, T(n), is the most common measure
• The testing conditions depend on the number of inputs

Testing Conditions

• Best-case: Few inputs
• Average-case: Normal inputs
• Worst-case: Large number of inputs

Complexity Function

• The complexity function T(n) is determined by counting the number of operations in the algorithm

Algorithm Order

• It's the categorization of a given complexity function related to resource usage
• This order is determined by the established function T(n) or S(n)

Growth Rate

• It is determined by how storage or time grows with the size of inputs like O(n), O(n!), O(logn), etc

Algorithm Analysis Steps

Drive the function T(n) for the algorithm

• Determine the order/category of T(n)

Order Notation

• A given algorithm order or a function T(n) is written as O(T(n))
• O(T(n)) means "category/order of the function T(n)"

Example of Algorithm Order

• If the time complexity function T(n) is categorized in logarithmic time, it's written as O(T(n)) = logn

Calculating Order of T(n)

• Constant coefficients, logarithm bases, and powers are omitted
• The highest degree is taken from a polynomial

Rules for Computing Complexity

• The complexity function T(n) is determined by counting the number of operations of the algorithm
• There are two types of counting: informal and formal

Complexity Analysis Methods

• The informal method counts all operations in the algorithm
• The formal method counts operations ignoring variable initializations and loop controls

Running Time of Selection Statements

• The running time is {time for condition evaluation} + {the maximum running time for individual clauses}

Loop Running Time

• The loop running time equals the statements' time inside the loop multiplied by the number of iterations

Nested Loops Timings

• The total running time of nested loops is multiplied by product of the sizes of all the loops

Blocks or Sequences of Statements

• Using the order arithmetic addition rule O( f(n)+g(n)) = max( f(n), g(n)), add the time complexities of each statement

Formal vs. Informal Analysis

• Formal analysis often simplifies complexity and can be more convenient for estimating general efficiency

Complexity Orders

• O(n) – Linear Time Complexity
• O(log n) – Logarithmic Time Complexity
• O(n^2) – Quadratic Time Complexity
• O(2^n) – Exponential Time Complexity
• O(1) – Constant Time Complexity

Time-Space Tradeoff

• Choosing an algorithm often involves balancing time efficiency against memory usage

Exercises

• Computing resource requirements and determining complexity for different algorithms is important

Asymptotic Notation

• If there's a complexity function T(n) of an algorithm, the order of complexity in terms of asymptotic notation can be as follows

Types of Asymptotic Notation

• Big-Oh Notation (O)
• Big-Omega Notation (Ω)
• Theta Notation (Θ)
• Little-o Notation (o)
• Little-Omega Notation (ω)

Representing Growth Rate

• These notations are used to represent and explain the growth rate of the function, T(n), of algorithms

Big-Oh Notation (O)

• If f is a given function, and if some function g is an upper bound for f, then we express this with big O
• In simple terms, f(n) = O(g(n)) means the growth rate of f(n) is less than or equal to g(n), so g(n) is the upper bound of f(n)

Big Omega notation (Ω)

• If f is a given function, and if some function g is an lower bound for f, then we express this with big Ω
• In simple terms, f(n) = Ω(g(n)) means the growth rate of f(n) is greater than or equal to g(n), so g(n) is the lower bound of f(n)

Theta Notation

• If f is a given function, and if some function g is a tight bound for f, then we say that f is Θ of g
• In simple terms, f(n) = Θ(g(n)) means the growth rate of f(n) is the same as g(n), so g(n) is a tight bound of f(n)

Algorithm Analysis Focus

• Asymptotic analysis is used most often
• Algorithm growth rate increases as size of input increases without bound
• Focus lies on running time given worst-case inputs

Simple Sorting Algorithms

• Selection sort
• Bubble sort
• Insertion sort

Simple Searching Algorithms

• Linear/sequential searching
• Binary searching

Sorting Basics

• Sorting reorders lists by increasing or decreasing value
• Algorithm efficiency measured by # of comparisons and data movements

Sorting Algorithms: Simple vs Advanced.

• Simple algorithms more fit for smaller datasets

Selection Sort Process

• Scan list, swapping minimum value with current position in the list. Iterate one position at a time until complete

Selection Sort Steps:

1. Go through the array from i=0 to n-1
2. Select the smallest element from i to n
3. Swap this value with position i

Selection Sort

• This algorithm repeatedly finds the next smallest element in an unsorted array and moves it to its final sorted position

List Division in Selection Sort

• Maintains a sub-list of sorted items and a sub-list of remaining items

Selection Sort Analysis

• The outer loop executes n-1 times
• Inner loop executions are about n(n-1)/2 on average: O(n²)
• Work done in inner loop is constant

Efficiency of Selection Sort

• Comparisons: O(n^2)
• Swaps: O(n)

Bubble Sort

• Called the Exchange Sort

Bubble Sort Details

• Simplest to implement but least efficient on large datasets
• Array is processed, swapping adjacent elements if out of order

Bubble Sort Process

• Each pass compares adjacent, unsorted elements
• Larger elements bubble toward their final sorted positions
• Continue sorting from the first to second largest elements, and so on

Bubble Sort Analysis

• n = a.length = size of the array
• The outer loop executes n-1 times
• Each time the outer loop is executed, the inner loop is executed

Inner Loop Analysis

• Inner loop executes n-1 times at first, linearly dropping to just once
• On average, inner loop executes about n(n-1)/2 times for each execution of the outer loop
• In the inner loop, the comparison is always done (constant time), the swap might be done (also constant time)

Bubble Sort Result

Result is (n-1) * [ n(n-1)/2 ] + k, that is, O(n²)

Bubble Sort Efficiency

• Comparisons: O(n²)
• Swaps: O(n²)
• Simplicity comes at cost of speed in large datasets

Insertion Sort Goal

• Each item is inserted in its proper place in the final list

Insertion Sort Steps

• The left most value can be said to be sorted relative to itself, so there is not an action required
• Check to see if the second value is smaller than the first one; if it is, swap values. The first two values are now relatively sorted

Insertion Sort Details

• Remove the third value first and slide the second value to make room for insertion. Insert the value in the proper position, so now the first three are relatively sorted
• Do same for remaining items in the list

Insertion Sort Algorithm

Algorithm checks and places each value in sorted portion of list

Insertion Sort Analysis

• Outer loop runs once through each n element
• Inner loop looks at 1/2 of 'n' elements then this gives a second factor of n/4 In Insertion sort the time required is proportional to n²/4 so insertion sort is O(n^2)

Insertion Sort Efficiency

• Comparisons: O(n²)
• Swaps: O(n²)

Summary of sorting algorithms

Bubble Sort, Selection Sort, and Insertion Sort are all O(n²) Within O(n²),

• Bubble Sort is very slow, and should probably never be used for anything
• Selection Sort is intermediate in speed
• Insertion Sort is usually the fastest–-in fact, for small arrays (like 10 or 15 elements), insertion sort is faster than more complicated sorting algorithms

Comparison of "Simple" Sorts

• While easy to code, these sorts perform poorly on larger datasets

Searching Algorithms

• Searching identifies a specific element or determines its absence

Data Set

• Sequential search and Binary Search are used

Linear Search

• Called sequential, but easy to understand and implement

Linear Search Procedure

• Scan list, comparing elements to identified variable
• End once match or last list item reached Return -1 if identified variable is not found

Linear Search Analysis

• Loop is proportional to input (n)

Binary Search Basis

• Binary Search is efficient for ordered lists This is on the basis of divide and conquer

Binary Search Steps

The basic idea is locates middle of array

• Determine if target is in lower or upper half of an array Loop until end occurs or negative is found

Binary Search Analysis

• Loop is proportional to log based of length of the array Therefore the time complexity is O(log n)

CHAPTER 3 – LINKED LISTS

• Pointer, Dynamic Memory allocation and De-allocation Pointer A pointer is a variable used for storing the address of a memory cell. This address is the location of another object (typically another variable) in memory.

Syntax:

type *name; type is the base type of the pointer and may be any valid type. The name of the pointer variable is specified by name.

Pointer Operators:

& - is a unary operator that returns the memory address of its operand.

• -is an unary operator that returns the value located at the address that follows.

Arrays of Pointers

The declaration for an int pointer array of size 10 is: int *x[10]; To assign the address of an integer variable called var to the third element of the pointer array, write: x[2] = &var; To find the value of var, write: *x[2];

Operators for Allocation and Deallocation

• Memory that has been allocated by a call to new can be released by delete operator

Structure is defined as:

struct struct-tag { Typel member variable1; Type2 member variable2; Type n member variablen; } variable-namel, variable-name2...;

• arrow operator (- ->) point it toward data members. Like pointer to an object calls variable or operator

Self Referenced using pointer

struct Node { Data typel data; Data type2 data; Node * next; // Name given to pointer which point to Node data type }

Singly Linked Lists

• collection of nodes storing data and links to other nodes. A node contains some information useful for a specific application and a pointer to the next node. The most flexible implementation is by using pointers
• A node of linked list structure has a link only to its successor in the sequence of node, so the list is called a single linked list

Linked List Rules

• Linked list structure which can change during execution
• Successive elements are connected by pointers, and Last element points to NULL. If the list currently contains 0 nodes, the head points to NULL

Singly Linked Lists

• List can grow and shrink with execution
• List made as long as needed and that do not waste memory

Process to Create a new node process

1. Allocate memory for the new node with 'new' assignment
2. Initialize the contents of the node and copy data into struct
3. Set the pointer field to NULL value

Doubly LinkedList

• The pointer in the first node will be default as NULL in head pointer, node and all next nodes

New Node Insertion Location

• The simplest strategy for adding is at the beginning of a list. (see the bullet points)

Step to Insert to Beginning

1. Allocate space for a new node and copying the item into it.
2. Making pointer from new node to current head,
3. Make the head of the list point to the newly-allocated node, (see visual aides for context)

• Addition at the beginning of the list is fast and efficient

Linked List Insertion Strategies

Insertion at the end or to create the list.

• Allocate a space for new node and copying in data

Steps to new nodes to the end of a linked list

The steps to add a new node to the end of the list Allocate the space for a new node Copy the item in to it and initialize the new code

To append a new node to an empty List

Include the node in the list by making the next member of the last node point to the newly created node (see visual guides for context) assigning address to tail The steps to add node in a specified location: Allocation made and info copied Keep track of 2 node to find the right place in the list

Deleting from LinkdList

A node can be at head, end, or middle, and here release from memory. to do a delete from start of the list *Make temp pointer first

• Point it to head=temp- head= head next and move this location
• second code set then *delete temp

Operations for LinkedListDeletion Methods

Unlike the previously stored lists, the LinkedList have to be modified to avoid null points and ensure nodes link correctly

• Deleting a specific node from a list is to Unlink the node and connect to the next available node, and Delete the unlinked node* The method then iterates to search all the nodes related to a number sequence in list (see example)

Traversing a Linked List is a procedure that accesses and processes elements linked from to data structure in sequention to display note

To display a list nodes:

• Visit each node in a linked list and then perform basic processes
• • Basic process to Traverse to Display Nodes ***
• Set pointer to where the contents are contained- While there is not a NULL pointer:
• display data go to next node by setting Pointer field. the list-end while

** CHAPTER 4 – STACKS AND QUEUES **

Stack Overview

– data structure gives temp storage so element set first will be retrieved last is (LIFO) “last in first out.

• items added "pushed to list“ is removed using the stack. top. Stack temp storage. nesting

Operations:

• operations
• Push s- push #k as stack s. then Popt s deleting s Peeks returning s the value
• -IsEmptyts

IsFulls returns code if FULL

• • Array Implementation of Stacks: The PUSH operation ** -increment the stock up is alway stop +check low step + go

Step2 PUSH element in with value to be added

-Array implementation that Pops Operation

step give up "or empty give a value (see description step a and hold element point up hold value value and and change one

The Queues is used for datastructures

queues has that has the access for it for front and back. and of of the operations

Tree Categories

• Three kinds:Normal Priority Doublly-Ended (Dequeue) queuess-

Queue Details

• Operates via First in First Out or FIFO method -Using 2 or more indexes to track and basic operations use
• Enqueue-enter in data in rear of of the and and Queues
• Dequeue remove data and point in of of these questions in see see operations

LinkedList Details

To build basic arrays, to add variables, elements that index that and how the Qsize add to Q. check notes and look at sample code

CHAPTER 5 - TREE STRUCTURES

Tree Overview

A tree consists of nodes and edges, illustrating a hierarchical structure and includes these traits:

• Single root node, with connections as descendants
• Each except root connects from P as parent with the descendants

Tree properties

• Paths and length noted from root Root
• Parent less, Top most
• Node with children Leaf Child-less, Last row
• Relationships
• Ancestors the root path
• Descendants all relations from above (see graph

Tree Terms- Depth

• Number of level from root

• Tree Types, and Binary Tree are:

• A Tree is root and descendants

• Binary has most 2 children

Full, Full Binary, Balanced Types

• Full BT has all zeros or children
• Balance BT has node and children

Binary Search BST(ordered

• Search tree with the following: Each node <, node, no repeat number. Then *Right keys go larger left smaller

DATA STRUCTURE

• Structure that declares value and right and left, with right link
• Operation and BinaryTree =Root

Tree Operations

• *Insertion: Preserves the binary structure There = Null; code set that in by. 2 ptrs. insertBST for no data, should and for the set value ( see steps) CASE DATA= insert at position. See search algorithms. insert that node that can

Tree Binary Search Methods

• Binary searches in tree can be traversered in 3 ways: pre, post, in order
• • a Pre order =Traverse to see parent side left and right - post order - traverse and show right and parent
• inO. show to to list ( read ascending)
• post. do to set to read for the

DELETION

• To remove known. Note value from Bst And. four should all the (see graph/image. read and steps)