Algorithms and Complexity: Intro to DSA

Algorithms and Complexity - Introduction to DSA & Complexity

• This presentation is about algorithms and complexity in computer science, covering data structures and algorithms (DSA)
• The presentation covers winter semester 2024/2025

Program Week 1

• Lesson 1: Introduction and Big O
• Lesson 2: Complexity - time and memory
• Lesson 3: Mathematical and Bitwise Algorithms
• Activities: Quizzes and tasks

Program Week 2

• Lesson 3: Arrays and Matrices
• Lesson 4: Stack and Queue
• Lab 1: Lab 1
• Activities: Quizzes and tasks

Program Week 3

• Lesson 5: Recursion and Backtracking Algorithms
• Lesson 6: Divide and Conquer Algorithms
• Lab 2: Lab 2
• Activities: Quizzes and tasks

Program Week 4

• Lesson 7: Searching and Sorting Algorithms
• Lesson 8: Linked Lists and Hash
• Lab 3: Lab 3
• Activities: Quizzes and tasks

Program Week 5

• Lesson 9: Trees
• Lesson 10: Tree Algorithms
• Lab 4: Lab 4
• Activities: Quizzes and tasks

Program Week 6

• Lesson 11: Greedy Algorithms
• Lesson 12: Dynamic Programming
• Lab 5: Lab 5
• Activities: Quizzes and tasks

Program Week 7

• Lesson 13: Graphs
• Lesson 14: Graph Algorithms
• Lab 6: Lab 6
• Activities: Quizzes and tasks

Grading

• Quizzes: 20 units, 0.8 points per unit, 15 total points
• Tasks: 20 units, 0.8 points per unit, 15 total points
• Labs: 7 units, 1.4 points per unit, 10 total points
• Exam: 1 unit, 60 points
• Grading Scale: 51-60% = 6, 61-70% = 7, 71-80% = 8, 81-90% = 9, 91-100% = 10

Data Structures and Algorithms

• The study of data structures and algorithms involves organizing and storing data, and the design of algorithms for problems that use these structures
• These are used in common software challenges, managing large datasets to optimize tasks

Why This is Essential

• Efficient data storage and retrieval is key for applications
• This is fundamental to areas, like GPS systems and search engine optimization
• This is vital in web applications, databases, and machine learning

How to Learn DSA

• Choose a programming language
• Understand the time and space complexities of algorithms
• Learn common data structures and algorithms
• Focus on high-quality problem-solving
• Participate in coding contests

Analysis of Algorithms

• This aspect of computer science involves evaluating the performance of algorithms
• Measured in terms of efficiency focusing on time and space complexity

Asymptotic Analysis

• A mathematical technique to understand algorithm behavior under larger inputs, particularly their growth rates
• Uses asymptotic notations to define the algorithm's performance to compare different algorithms

Worst Case Analysis of Algorithms

• In this analysis the upper bound of an algorithm's running time for a given input size, or the maximum amount of operations possible
• Requires knowing the worst-case scenario for the input producing the most operations

Best Case Analysis of Algorithms

• The minimal running time of an algorithm for each input
• Identifying the input that results in the fewest amount of operations is necessary

Average Case Analysis of Algorithms

• Analyzing the average running time from all possible inputs
• Calculate the average value of operations

Big-O Notation

• A mathematical technique to express an upper bound on the time complexity, or runtime, of an algorithm
• Used to compare different algorithms, which is a key concept in computing
• Providing the foundation for efficiency analysis

Properties of Big-O Notation

• Reflexivity: A function f(n) = O(f(n))
• Transitivity: if f(n) = O(g(n)) and g(n) = O(h(n)) then f(n) = O(h(n))
• Constant Factor: c * f(n) = O(f(n)) given a constant c greater than zero
• Sum Rule: f(n) = O(g(n)) and h(n) = O(g(n)) then f(n) + h(n) = O(g(n))
• Product Rule: f(n) = O(g(n)) and h(n) = O(k(n)) then f(n) * h(n) = O(g(n) * k(n))
• Composition Rule: f(n) = O(g(n)) and g(n) = O(h(n)) then f(g(n)) = O(h(n))

Big-O Notation - General Rules

• Ignore Constants: 5n = O (n)
• Dominate Terms: O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

Constant Time Complexity: Big O(1)

• The running time is independent of the input size
• Constant time operations, like addition, subtraction, and accessing data elements are examples

Linear Time Complexity: Big O(n)

• The running time for each input increases linearly with the input size.
• Iterating through a list, for instance, has a linear time complexity.

Logarithmic Time Complexity: Big O(log n)

• The running time for each input increases proportionally to the logarithm of the input size.
• Binary search is an algorithm that has logarithmic time complexity.

Quadratic Time Complexity: Big O(n^2)

• The running time is proportional to the square of the input size.
• Sorting algorithms like bubble sort have quadratic time complexity.

Cubic Time Complexity: Big O(n^3)

• The running time is proportional to the cube of the input size
• Matrix multiplication algorithms have cubic time complexity

Polynomial Time Complexity: Big O(n^k)

• The running time that can be written in polynomial form of the input size n

Exponential Time Complexity: Big O(2^n)

• The running time doubles with each addition to the input set.

Factorial Time Complexity: Big O(n!)

• The running time grows factorially with the input size.
• Generating all permutations of data has factorial time complexity

Plot of the most common Big-O

• A plot that illustrates the rate of growth of common Big-O notations for varying input sizes, showing the relative efficiency of algorithms.