Intro Data Structures & Algorithms

Data structures:

• How data is stored and or organized and the operations that can be preformed on the data.

• Data + ADT => data structure

Abstract Data Type (ADT)

• The operations that are available to preform on the data.

  • User Can’t directly access the data

  • User can only do with the data what is allowed by the operations.

Categories of Data Structures(built in to all modern launges)

• Primitives:

  • int, float, Boolean, chars, array

• Compound:

  • Linear

    • list , stack, queue

  • Non-linear

    • graph

      • Tree (not all trees are graphs but not vise versa)

      • Heaps: A specialized tree-based structure that satisfies the heap property, commonly used in priority queues.

      • set, map.

    • hash tables

      • map and set ( not looked at in depth)

Importance of Efficiency in Algorithms

• Performance Impact: Efficient algorithms preform better, reducing the time and resources requited to solve a problem.

• Scalability: Efficient algorithms should be able to handle larger input sizes without a significant increase in resource consumption or processing time.

• Resource management: Efficient algorithms use fewer recourses ( cpu, memory) especially in environment with limited computational power.

• User Experience: Faster algorithms improve the UI by providing quicker responses

Factors Influencing Efficiency

• Time Efficiency: Refers to how quickly and algorithm completes its task.

• Space Efficiency: Refers to the amount of memory an algorithm uses during is execution.

  Measure of Response

• Temporal Complexity: Refers to the computational time required to execute an algorithm as a function of the length of the input. (if we put in more data how much longer will it take the algorithm to complete)

• Spatial Complexity: Measures the amount of memory an algorithms consumes

Impact on Performance

• Algorithm Selection: Choosing which algorithm will be best based on the objective.

• Scalability Analysis: Evaluates how well an algorithm can handle an increasing amount of data or workload, ensuring that performance remains efficient as system demands grow.

Common Time Complexity Categories

• Sub-polynomial Time: Algorithms whose time complexity grows slower than any polynomial, often involving logarithmic growth.

  • Super-efficient. Time hardly grows even as input size increases.

  • Binary search, array element.

  • Faster than an algorithm in polynomial time.

Polynomial Time

• Time complexity that can be expressed as $O(n^k)$ for some constant k.

Quasi-polynomial Time

• Not very useful and is slower than polynomial time

Sub-exponential

• Faster than exponential, slower than any polynomial

• Some times used in cryptography