Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    Algorithms - Lab 1

    Uploaded by

    youssefmustafa215
    The document discusses algorithms and their analysis. It covers key topics like: 1) What algorithms are and their importance in computing. Algorithms solve problems efficiently and enable processing data. 2) Common algorithm analysis methods like time complexity, which measures how runtime grows with input size, and space complexity, which measures memory usage. 3) Common algorithm time complexities like linear, logarithmic, quadratic, and their notations like Big O for worst case and Big Omega for best case.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Algorithms - Lab 1

    Uploaded by

    youssefmustafa215
    6 views25 pages
    The document discusses algorithms and their analysis. It covers key topics like: 1) What algorithms are and their importance in computing. Algorithms solve problems efficiently and enable processing data. 2) Common algorithm analysis methods like time complexity, which measures how runtime grows with input size, and space complexity, which measures memory usage. 3) Common algorithm time complexities like linear, logarithmic, quadratic, and their notations like Big O for worst case and Big Omega for best case.

    Original Description:

    Algorithms_ Lab 1

    Original Title

    Algorithms_ Lab 1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses algorithms and their analysis. It covers key topics like: 1) What algorithms are and their importance in computing. Algorithms solve problems efficiently and enable processing data. 2) Common algorithm analysis methods like time complexity, which measures how runtime grows with input size, and space complexity, which measures memory usage. 3) Common algorithm time complexities like linear, logarithmic, quadratic, and their notations like Big O for worst case and Big Omega for best case.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    6 views25 pages

    Algorithms - Lab 1

    Uploaded by

    youssefmustafa215
    The document discusses algorithms and their analysis. It covers key topics like: 1) What algorithms are and their importance in computing. Algorithms solve problems efficiently and enable processing data. 2) Common algorithm analysis methods like time complexity, which measures how runtime grows with input size, and space complexity, which measures memory usage. 3) Common algorithm time complexities like linear, logarithmic, quadratic, and their notations like Big O for worst case and Big Omega for best case.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 25

    Algorithms

    Lab 1
    Agenda

    1. Introduction to Algorithms
    2. Data Structures & Algorithms Overlapping
    3. Analysis of Algorithms
    1. Iterative Approach
    2. Recursive Approach
    Introduction To Algorithms
    What Are Algorithms?

    • An algorithm is a precise set of instructions designed to solve a


    specific problem.

    • It's like a recipe for solving a computational task.

    • Algorithms form the basis of computer programming.


    Importance in Computing

    • Algorithms are the backbone of computing.

    • They enable us to process data, make decisions, and perform tasks


    efficiently in various applications.
    Efficiency and Optimization

    • Algorithms are not just about solving problems; they are also about
    solving them efficiently.

    • Efficient algorithms are key to saving time, computational


    resources, and energy. They're essential in today's computing
    environments.
    Algorithmic Thinking

    • Algorithmic thinking is the ability to break down complex


    problems into smaller, solvable components.

    • It's a valuable skill in the world of technology.


    DS & Algorithms Overlapping
    Data Structures & Algorithms Overlapping

    • Designing a contact book application (List vs. Map)

    • Keeping track with min or max grade of some students (List vs. Heap)
    Analysis Of Algorithms
    Performance vs Complexity

    • Performance: How much time/memory/disk/etc. is used when a


    program is run. This depends on the machine, compiler, etc. as well as
    the code we writ​e.

    • Complexity: How do the resource requirements of a program or


    algorithm scale, ( what happens as the size of the problem being solved
    by the code gets larger).
    Introduction to Analysis of Algorithms

    • Algorithm Analysis: It is an important part of computational


    complexity theory, which provides theoretical estimation for the
    required resources of an algorithm to solve a specific computational
    problem.
    • Analysis of algorithms is the determination of the amount of time and
    space resources required to execute it.
    • Analyzing algorithms helps us understand their performance, make
    informed design choices, and select the most suitable algorithm for a
    given problem.
    Type of Analysis

    • Space Complexity Analysis : Measures how the algorithm's


    memory usage increases as the input size increases.

    • Execution Time Complexity Analysis : Measures how the algorithm's


    runtime grows according to the input size.
    Space Complexity Analysis

    • Space complexity measures the amount of memory an


    algorithm requires as a function of the size of its input.

    • It helps identify algorithms with minimal memory overhead.


    Execution Time Complexity Analysis

    • Time complexity quantifies ( count ) the number of basic operations


    that the algorithm performs as a function of the size of its input.

    • Common notations include :


    o Best Case: Minimum time required for program execution (Ω Notation)
    o Average Case: Average time required for program execution (θ Notation)
    o Worst Case: Maximum time required for program execution (Big Ο Notation)
    Asymptotic notation

    • Asymptotic Notation is used to describe the running time of an


    algorithm - how much time an algorithm takes with a given input n.
    • There Are Three Main Notations :
    o Big Omega (Ω) Notation
    o Big Theta (Θ) Notation
    o Big O Notation
    Big Omega (Ω) Notation

    • Describes the lower bound of an algorithm's complexity.


    • It provides a best-case analysis.
    • We compute the big-Ω by counting how many iterations an algorithm will
    take in the best-case scenario based on an input of N.
    • For example, a Sort algorithm has a running time of Ω(N) because in
    the best-case scenario the list is already sorted, and the sort will
    terminate after the first iteration.
    Big Theta (Θ) Notation

    • Big Theta notation combines Big O (Upper Bound) and Big Omega
    (Lower Bound) to describe the tight bounds of an algorithm's
    complexity.
    • It offers a more precise analysis.
    • We compute the big-Θ of an algorithm by counting the number of
    iterations the algorithm usually takes with an input of n.
    Big O Notation

    • Big-O notation describes the worst-case running time of a program.


    • We compute the Big-O of an algorithm by counting how many iterations
    an algorithm will take in the worst-case scenario with an input of N.
    • We typically consult the Big-O because we must always plan for the
    worst case.
    • For example, O(N^2) describes the Big-O of a Bubble Sort algorithm if
    all elements in the list need to be sorted are sorted in a reverse order.
    Common Runtimes
    Common Runtimes Cont'd

    Logarithmic: O(log n) Linear: O(n)


    Common Runtimes Cont'd

    Linear Logarithmic: O(n log n) Quadratic: O(n^2)


    Common Runtimes Cont'd

    Cubic: O(n^3) Exponential: O(2^n)


    Problem
    Thank You!

    You might also like