wait, wut?

Introduction

What is an Algorithm?

  • set of well-defined instructions to solve particular problem
  • takes set of input and produces desired output

Qualities of Good Algorithms

  • input and output should be defined precisely
  • east step in algorithm should be clear and unambiguous
  • should be most effective among many different ways to solve problem
  • algorithm shouldn't include "computer code" (i.e. algorithm should be written in such a way that it can be used in different programming languages)

Data Structures and Types

What are Data Structures?

  • storage device/technique used to store and organize data
  • way of arranging data on computer so that it can be accessed and updated efficiently

Types of Data Structure

  • Linear data structure
  • Non-linear data structure

Linear Data Structures

  • elements arranged in sequence one after the other

Array Data Structure

  • elements in memory arranged in continuous memory
  • all elements are of the same type (usually)
  • type of element that can be stored in form of arrays is determined by programming language
  • Java Array

Stack Data Structure

Queue Data Structure

Linked List Data Structure

  • data elements connected through series of nodes
  • each node contains data items and address to next node
  • Linked List Data Structure

Non-linear Data Structures

  • elements not stored in any sequence
  • arranged in hierarchical manner where one element connected to one or more elements

Graph Data Structure

  • each node is called vertex
  • each vertex is connected to other vertices through edges
  • Graph Data Structure

Trees Data Structure

  • collection of vertices and edges
  • can only be one edge between two vertices
  • Tree Data Structure

Linear Vs Non-linear Data Structures

Linear Data Structures Non Linear Data Structures
The data items are arranged in sequential order, one after the other. The data items are arranged in non-sequential order (hierarchical manner).
All the items are present on the single layer. The data items are present at different layers.
It can be traversed on a single run. That is, if we start from the first element, we can traverse all the elements sequentially in a single pass. It requires multiple runs. That is, if we start from the first element it might not be possible to traverse all the elements in a single pass.
The memory utilization is not efficient. Different structures utilize memory in different efficient ways depending on the need.
The time complexity increase with the data size. Time complexity remains the same.
Example: Arrays, Stack, Queue Example: Tree, Graph, Map

Why Learn Data Structures and Algorithms?

TODO


Asymptotic Analysis

Asymptotic Notations

  • mathematical notations used to describe the running time of an algorithm where input tends towards a particular value or a limiting value

Big-O Notation (O-notation)

  • represents upper bound of running time of algorithm (the worst-case complexity)

Omega Notation (Ω-notation)

  • represents lower bound of running time of algorithm (the best-case complexity)

Theta Notation (Θ-notation)

  • encloses function from above and below (the average-case complexity)

Master Theorem


Divide and Conquer Algorithm

divide and conquer algorithm is strategy of using recursion to solve a large problem by

  1. breaking the problem into smaller sub-problems
  2. solving sub-problems
  3. combining them to get desired output

Recursion in Java

How do Divide and Conquer Algorithms Work?

  1. Divide: divide given problem into sub-problems using recursion
  2. Conquer: solve smaller sub-problems recursively, and if sub-problem is small enough, solve it directly
  3. Combine: combine solutions of sub-problems which are part of recursive process to solve actual problem

Example: merge sort

Divide and Conquer Vs. Dynamic Approach

Divide and Conquer

  • result of each sub-problem is not stored for future reference
  • used when same sub-problem is not solved multiple times

Dynamic Approach

  • result of each sub-problem is stored for future reference
  • used when result of sub-problem is to be used multiple times in future

Advantages of Divide and Conquer Algorithm

  • lower overall complexity?
  • suitable for multi-processing systems
  • makes efficient use of memory caches

Divide and Conquer Applications

Made with Gatsby G Logo