Data Structures and Algorithms

• Programming involves defining computations to solve problems or implement functionality.
• Most useful computations involve organizing and processing data.

Examples of Data Processing

• Extracting records from a database
• Generating embeddings for words using a transformer model
• Organizing PDF pages for fast searching

Key Requirements for Data Processing

• Data Representation: Choosing the right structure for the data
• Data Processing: Implementing efficient methods to manipulate the data
• Data representation and processing are interconnected
• Good representation enables efficient processing.

Data Structures & Algorithms

• Data structures are how data is organized and stored.
• Algorithms are a well-defined set of instructions for solving a problem.
• Algorithm's and Data Structures are studied together to optimize performance

Built-in vs. Custom Data Structures

• Some data structures are directly supported by programming languages, such as arrays and structs in C.
• Others are created by programmers for specific needs.

Reusable Data Structures

• Common data structures are often stored in libraries.
• Example: The Vector class in java.util for dynamic arrays in Java.
• Algorithms require a specific data structure to perform tasks like sorting data.

Linear Structures

• Represent sequential data and simple ordering relationships.
• Simple and powerful, applicable in many scenarios like web applications.
• Examples: Arrays, linked lists, stacks, and queues.
• Used in scheduling, parsing, and managing ordered data.

Hierarchical & Graph Structures

• Hierarchical Structures (Trees): Represent one-to-many relationships with efficient searching and organization.
• Graph Structures: Represent many-to-many relationships, modeling complex connections and networks.
• Example of Graph Structure: Google Maps (Road Network), where cities (nodes) are connected and Social Media Networks, where users are connected

Set Structures

• Track membership which is checking if an element exists
• Example include checking if a website has been visited

Hash Tables

• Key-value store for fast lookups
• These structures have specialized applications like Bloom filters

Operations on Data Structures

• Dynamic Nature: Data structures can change in size, growing or shrinking.
• Operations Classification:
  • Queries: Return information about the structure or its elements.
  • Modifiers: Change the content of the structure.

Query Operations

• Search: Finds and returns a pointer to a record matching a key value, or nil if no match.
• Minimum: Returns the record with the smallest key.
• Maximum: Returns the record with the largest key.
• Successor: Returns the pointer to the next element in sequence.
• Predecessor: Returns the pointer to the previous element in sequence.

Modifier Operations

• Insert: Adds a new record to the data structure.
• Delete: Removes a record from the structure.
• Replace: Replaces an entire record with another (can be done using delete and insert).
• Update: Modifies one or more fields in an existing record.

Caveats

• Not all operations apply to all structures (e.g., no "previous element" in undirected graphs).
• Some data structures, like arrays and linked lists, share common interfaces.
• Performance varies depending on the structure used.

List Comprehension with Filters

• Creates a new list while filtering elements based on a condition.
• Example:

numbers = [1, 3, 6, 8, 10]
numsq = [n* n for n in numbers if n > 5] # [36, 64, 100]

List Comprehension with Conditionals

• Applies different operations based on a condition.
• Example:

numbers = [1, 3, 5, 7, 9]
numdst = [n* n if n < 5 else n / 2 for n in numbers] # [1, 9, 2.5, 3.5, 4.5]

Recursion

• Maintains the program state in the call stack
• Involves less bookkeeping and reduces potential for errors.
• Recursive algorithms are common when operating on data structures

Testings

• Tests individual functions or small sections of code separately
• Ensures that each function works correctly on its own.
• Example: Testing a single function that adds two numbers.

Integration Testing

• Tests how different functions or modules work together.
• Helps catch issues when combining different parts of the program.
• Example: Checking if a login system correctly interacts with a database.

Types of Integration Testing

• Incremental Testing: Components are tested one at a time and added gradually -Example: First testing the login system, then adding and testing the profile page.
• Non-Incremental Testing: All components are combined at once and tested together.
• Example: Building the entire system first, then testing everything in one go.

System Testing

• Tests the entire software system as a whole.
• Ensures that all components work together correctly.
• Example: Running a full test of a web application, including login, payments, and navigation.

Non-Functional: Performance Testing

• Checks how well a system performs under specific workloads, measuring speed, responsiveness, and stability.

Components of Performance Testing

• Scalability Testing: Tests how well the system can handle increasing loads (more users, data, requests).
• Example: Testing a platform's ability to support millions of users without performance issues.
• Stability Testing: Ensures the software remains stable over time and under stress or long periods of use.
• Example: Running an app for 24 hours to check if it crashes or freezes.
• Speed and Memory Testing: Measures how fast the software performs and how efficiently it uses memory.
• Example: Checking if an app consumes too much memory or if a website loads quickly.

Usability Testing

• Tests how user-friendly the software is.
• Example: Seeing if users can easily navigate a shopping app.

Compatibility Testing

• Ensures the software works correctly on different devices, browsers, and operating systems.
• Example: Checking if a website works on Chrome, Safari, and Edge.

Gray Box Testing

• Combines Black Box Testing (no internal knowledge) and White Box Testing (full internal knowledge).
• A tester has partial knowledge of the system's internal workings but still tests it from an end-user perspective.

Automation Testing

• Uses scripts or tools to automate repetitive testing tasks.
• Example: Running an automated test to check login functionality after every update.
• Programs must minimize running time and use less memory and be logically correct for all inputs!
• Efficiency is measured by complexity analysis.
• Only optimize when necessary and premature optimization is not neccessary

Key Considerations for Performance Testing

• Optimize Only When Necessary- A program is only "too slow" if it fails to meet the project's performance goals.
• Fast Code vs. Correct Code- Correctness is always more important than speed and only optimize after ensuring the code works correctly.
• Defining Reasonable Performance Requirements- User Experience is the top priority

Algorithm Performance Analysis

• Internal Factors (Depend on the Algorithm Itself): Run Time → How long the algorithm takes to execute. Memory Requirement → How much memory the algorithm uses.
• External Factors (Depend on the Environment): Input Size → Larger inputs can slow down an algorithm. Computer Specs → Faster processors and more RAM can improve performance. Compiler Quality & Optimization → A better compiler can make the code run faster.
• Speed is generally prioritized over memory usage, internal factors are the main focus when analyzing algorithms, but this depends on the problem.

Empirical Analysis (Evidence-Based Testing) Limitations

• It can be misleading because hardware and software differences impact results.
• It may not accurately reflect the algorithm's true complexity (Big-O).
• It cant test completeness soundness, and correctness
• Can't compare results unless experiments are done in the same environment

Performance Analysis Analytical Approach – Complexity Analysis: Analytical Analysis explained

• Ignores implementation details: (e.g., hardware, programming language).
• Uses pseudocode to analyze performance.
• Counts the number of primitive operations: (basic steps) executed.
• Assumes each operation takes a constant amount of time.

Why Use It?

• Provides general function t(n): that describes how the algorithm scales with input size (n).
• Helps estimate actual running time without depending on a specific computer.

Benchmarking Types

• Software Benchmarking: Measuring how well a program or app runs on different systems- Example: Checking how fast a web browser loads pages on Windows vs. Mac.
• Hardware Benchmarking: Testing the performance of computer components like CPU, GPU, or storage.-Example: Measuring how fast an SSD copies files.
• General Benchmarking: Evaluating the overall performance of a system, including both hardware and software.- Example: Testing how long a laptop battery lasts while playing videos.

Complexity

• Time Complexity: How long the algorithm takes to run.
• Computational Complexity: How many steps or operations are needed.
• Space Complexity: How much memory the algorithm uses.

Analyze Complexity to

• Understand how performance changes as input size (n) grows
• Express as a function of n like O(n), O(log n), O(n²).

Benchmarking: Timing Methods

• Method- Record start and end times manually, example: timeModule
• Method- Runs code multiple times to get an average execution time, timeit Module Module

Profiling

• Measuring detailed system statistics to analyze performance
• Key Focus:
  • Time Spent: Identify where the most time is being spent, which method is slowest or called the most. Memory Usage: Track memory allocation, types of objects created, and memory consumption.
• Importance: Especially useful in Object-Oriented and Garbage-Collected environments.

Profiling vs. Benchmarking vs. Optimizing

• Profiling: See the internal details such as where time is spent and internal memory used
• Benchmarking: Measures how fast your program runs overall.
• Optimizing: Refactoring and enhancing to speed up code

Example of Complexity Analysis

def sumArray(A, n):
    total = 0             # 1 operation
    for i in range(n):    # Loop runs n times
        total += A[i]     # 1 operation per iteration
    return total          # 1 operation

• Outside the loop: total = 0: 1 operation return total: 1 operation → 2 operations
• Loop: Loop runs n times. Each iteration: 1 addition(total += A[i])→n operation
• Total Operations: t(n) = 2 + n

Asymptotic Complexity

• Growth Rate: Measures how an algorithm's performance grows as the input size n increases.
• Asymptote: A straight line approached by a curve as it moves toward infinity.
• Ignoring Constants and Lower Terms: As n becomes large, constants and lower order terms of t(n) contribute little to the overall function and are ignored in asymptotic analysis
• Simplification: Simplify analysis by ignoring details that don't significantly impact comparisons between algorithms such as t(n)=8n-2 simplified to 0(n)

Upper and Lower Bounds

• Help simplify analysis of complex functions by focusing on their asymptotic growth
• Big-O : Represents an upper bound on the growth rate, showing the worst-case performance.
• Big-Ω : Represents a lower bound, showing the best-case performance.
• Big-O : Represents a tight bound, where both the upper and lower bounds are the same, indicating the algorithm's growth rate is bounded both from above and below.

Big-O Notation

• The purpose is to represents the worst-case scenario, the maximum amount of time or space an algorithm will take as the input n increases.
• F(n) is the function and g(n) is the upper bound

Big-Ω (Omega) Notation

• Specifies a lower bound for an algorithm's time or space complexity.
• Represents the best-case scenario—the minimum amount of time (or space) required.
• Helps determine the absolute least amount of resources an algorithm must use.

Big-Θ (Theta) Notation

• Specifies both an upper and lower bound on a function (tight bound).
• Ensures that f(n) grows at the same rate as g(n).
• Ignores constants and lower-order terms.
• If a function is Θ(g(n)), it must be both O(g(n)) and Ω(g(n)).
• Used for tight complexity analysis

Classes of Algorithms

• O(1): Constant time complexity
• O(log n): Logarithmic time complexity
• O(n): Linear time complexity
• O(n log n): N-Log-N time complexity
• O(n²): Quadratic time complexity
• O(n³): Cubic time complexity
• O(2ⁿ): Exponential time complexity

Best, Worst, and Average-Case Analysis

• Worst case: Maximum steps taken on any input of size n
• Best case: Minimum steps taken
• Average case: Expected steps based on input distribution.
• Basic Rules:
  • Simple statements are → O(1)
  • Worst case matters consider the longest path in conditionals
  • Halving the problem each time that is a binary search) → O(log n)
• Sum Rule:
  • Drop lower-order terms ex: O(n³ + n²) = O(n³)
• Product Rule: ex: Nested loops multiply complexities like 0(N) = O(n²)

Definitions For Terminology:

• Data: Consists of independent facts, observations, or values
• Record: Is made up of fields in a row in a table and are Data related to a unique object
• Field: Is a Single data element within a record and has a type/size

More Terminology

• File: Is a Collection of records
• Key: Is a Field used to select or order records may not be unique - Primary Key Main field for sorting ex: last name in phone book -Secondary Key Used when primary keys are identical ex: first name
• Searching : Returns a record and Finds it matching a key
• Sorting : Arrange records in ascending/descending order

Search Algorithms

• Search through a find that is related to a data structure and finds or retrieves element from data structure
• Sequential Search (Linear Search)
  • Checks each element one by one and Is for sorted & unsorted data ex: Linear Search (O(n) complexity) and it isn't that efficient for large datasets
  • Designed for sorted data only and Is more efficient than Linear Search ex: Binary Search (O(log n) complexity)
• In O(n) algorithms, Input doubles, time doubles the This is because each element adds more step to the process
• In contrast, number of comparison increases search grows much slower by 1 if input increases.
• ex 100 element equals 7 steps. Whereas, 200 Elements approximately equals 8 steps

Best Case / Worst Case and Average Case Analysis

• Best case complexity for linear search is O(1) and happens when the target element is found at the first position in the list.
• Worst-case complexity for linear search is O(n) and occurs when the target is at the end of the list or not present at all.
• Average-case complexity for linear search is O(n).
• **Does This Mean Worst- and Average-Case Take the Same Time?-
• *Not exactly!! O(n) means they scale the same way
• we search half the list in cases whereas in worst case we use full list

Which Complexity Should We Care About?

• Worst-case: is often the most to care about because it says performance guarantees in all the difficult scenarios
• Average-case: is useful when using randomly distributed imports
• Best-case Complexity: is rare and isn't reliable for analysis

Divide-and-Conquer:

• The following Steps include; Divide, Conquer, Combine Key
• Requirement is data must be sorted to makes implementation more straightforward.
• Recursion aligns naturally with the structure of divide-and-conquer algorithms that simplifies the code

Iterative vs. Recursive Algorithms

• Iterative Algorithm- Computes intermediate results by repeatedly executing a loop.
• Recursive Algorithm- Breaks the problem into smaller subproblems and solves them step by step

Function Call

• F is used on problem of P
• Recursion can call on one or more P, however, the size of P is smaller than P.
• This process continues until we reach base case
• Note* Binary search only searches in a half at a time instead of solving multiple problems

Steps in Binary Searches

• Binary search works by diving the array in half at each steps and follows power of 2 growth patterns.

General formula

• After n steps we would've used at least 2^(n-1) and confirms that n= O(log(n)

Binary Search vs General Divide-and-Conquer Binary Explanation

• worst-case = O (log(N ) and halves spaces for search
• Binary Search is Simpler because it saves time because the array sizes increases its because of steps

Steps in Interpolation Search

• Variant is binary search. Finds the "midpoint" based on where the is likely to
• **Benefits-**It faster binary in certain situations

Equations needed for problems

• Formula: Instead of: mid = (1o + hi) / 2
• *Use: p = (key - arr * (hi - lo Note :Searching F" start the section rather the in the telephone

Is Why Sorting?

• Helps Optimize and data processing, helps Enable algorithm and improves reliability

Steps Internal and External Sorts

• Internal - Date and small set can access with ram
• External- Data access by datasets

Important Notes

• Minimal additional space modifies array with sort of merges
• Uses extra memory to manage sorting
• Stable Sort: Maintain order of equal elements and maintains with merges.
• Change Order can be created by Quick Sort

Algorithm in Short

• Algorithm preserves order Maintained When sorting by multiple criteria
• Is useful with structure data with stable sorting

Shorting Algorithm Analysis

• Performance Metric- swaps comparisons
• Complex Notation- Describes analysis
• Trading Off- The primary factors to consider are comparisons and data movements

Important Notes

• More time to comparison to string and integers.
• Datasets helps large structure or large move and is not as as to compared to them

Algorithms

• Set of algorithm that is used to implement simple
• Types of Quick and Bubble Sorting
• Bubble: Method is adjacent comparison

Selection short

• Best Case: There is at least comparison per sort. Worst Case the more compilation there is. O (N2)

Time Complexity

• Stability In these situations is not stable and does not preserve equal elements

Like shorting of some hand

Start form 2nd and goes forward like "if" functions. Average and cases are bad and worsts

Insertion short: O (n). In average cases it does help with other situations that can be performed better by algorithm

###Ideal Performance Of Algorithm

• Has to implement a merge code. The Merge short uses divide and conquer.
• Steps for the sub codes, it splits and compares array and recursively applies the short on array and combines code. Always runs in time complexity regardless

Other Notes for Arrays and Stacks

• Arrays is store in memory.
• A linear data structure that consists of zero or more nodes.
• List can grow or dymanically
• The elements in the disk is store and more locations

Lists and Classes

• It provides data is assessment
• Initialize with data and next pointer with method access
• Insertion and Deletion in Linked Lists: There is a specific functions and location to known. Accessing a specific position otherwise there is O(n ). O is time

Last Note: Queues and Stack

• One element with predecessor Stacks pushes a new element to and queues add the list to read

Understand how data structures organize data and impact algorithm design. Learn about incremental testing strategies for components. Explore data structures in programming, like Java's Vector class, and system testing for comprehensive evaluation.