Data Structures and Computer Algorithms

Lecture notes on Data Structures and Computer Algorithms

By Rustam Zokirov

NOTES ON COMPUTER ALGORITHMS - HERE

Learning roadmap

• START HERE: Naso Academy DS playlist
• The Last Algorithms Course You'll Need
• ALGORITHMS VIDEO: Jenny's DSA playlist
• READING: programiz.com/dsa
• SHORT VIDEOS: Data Structures by Google Software Engineer

Practicing roadmap

• interviewbit.com
• LeetCode Explore
• LeetCode study plan — Data Structure 1, Algorithm 1, Programming Skills 1
• "Cracking the coding interview" + CTCI problems in LeetCode
• LeetCode study plan — Data Structure 2, Algorithm 2, Programming Skills 2
• AlgoExpert
• neetcode.io & NeetCode playlist

Contents

• Introduction to Data Structures
  • Introduction
  • Abstract Data Type
  • Asymptotic Notations (O, Ω, Θ)
• Searching techniques
  • Linear Search
  • Binary Search
• Sorting techniques
  • Merge sort
  • Quick sort
  • Heap sort
• Linked list
  • Insertion at the beginning
  • Insertion at the end
  • Insertion at particular position
  • Deleting the first Node
  • Deleting the last Node
  • Deleting the specific node in a Linked List
• Circular linked list
  • Insertion at the beginning
  • Insertion at the end
  • Insertion at particular position
  • Deletion a node

Introduction to Data Structures

Introduction

• Data structure usually refers to a data organization, management, and storage in main memory that enables efficiently access and modification.
• If data is arranged systematically then it gets the structure and becomes meaningful. This meaningful and processed data is the information.
• The cost of a solution is the amount of resources that the solution needs.
• A data structure requires:
  • Space for each data item it stores
  • Time to perform each basic operation
  • Programming effort
• How to select a data structure?
  • Identify the problem
  • Analyze the problem
  • Quantify the resources
  • Select the data structure

• Operations on data structures:
  • Traversing, Searching, Inserting, Deleting, Sorting, Merging.
• Algorithm properties:
  • It must be correct (must produce the desired output).
  • It is composed of a series of concrete steps.
  • There can be no ambiguity.
  • It must be composed of a finite number of steps.
  • It must terminate.
• To summarize:
  • Problem - a function of inputs and mapping them to outputs.
  • Algorithm - a step-by-step set of operations to solve a specific problem or a set of problems.
  • Program - a specific sequence of instructions in a prog. lang., and it may contain the implementation of many algorithms.

Abstract data type

• https://youtu.be/ZniDyolzrBw, https://youtu.be/n0e27Cpc88E
• Two important things about data types:
  • Defines a certain domain of values
  • Defines operations allowed on those values
  • Example: int takes
    • Takes only integer values
    • Operations: addition, subtraction, multiplication, division, bitwise operations.
• ADT describes a set of objects sharing the same properties and behaviors.
  • The properties of an ADT are its data.
  • The behaviors of an ADT are its operations or functions.
• ADT example: stack (can be implemented with array or linked list)
• Abstraction is the method of hiding unwanted information.
• Encapsulation is a method to hide the data in a single entity or unit along with a method to protect information from outside. Encapsulation can be implemented using an access modifier i.e. private, protected, and public.

What is the data structure

• A data structure is the organization of the data in a way so that it can be used efficiently.
• It is used to implement an ADT.
• ADT tells us what is to be done and data structures tell use how to do it.
• Types:
  • linear (stack, array, linked list)
  • non-linear (tree, graph)
  • static (compile time memory allocation), array
    • Advantage: fast access
    • Disadvantage: slow insertion and deletion
  • dynamic (run-time memory allocation), linked list
    • Advantage: faster insertion and deletion
    • Disadvantage: slow access

Asymptotic notations

• Efficiency measured in terms of TIME and SPACE. In terms of number of operations.

• Asymptotic complexity

  • The running time depends on the size of the input
  • f(n) = running time of an algorithm, where n= input size. We are interested in the growth of n to calculate the f(n)
  • "Functions do more work for bigger input"
  • Drop all constants: 3n, 5n, 100n => n, why?
  • Ignore lower order terms: n3 + n2 + n + 5 => n3
  • Ignore the base of logs: log(2) => ln(2)

• f(n) = O(n2) => describes how f(n) grows in comparison to n2

• Big-O notation, Ω (Omega) notation, Θ (Big-Theta) notation

• Big-O notation is used to measure the performance of any algorithm by providing the order of growth of the function.

• O (Big-O) notation (worst time, upper bound, maximum complexity), 0 <= f(n) <= c*g(n) for all n >= n0, f(n) = O(g(n))

  f(n) = 3n + 2, g(n) = n, f(n) = Og(n)
  
  3n + 2 <= Cn
  3n + 2 <= 4n
  n >= 2
  
  c = 4, n >= 2
  

  • n3 = O(n2) False
  • n2 = O(n3) True

• Ω (Omega) notation (best amount of time, lower bound), 0 <= c*g(n) <= f(n) for all n >=n0

  f(n) = 3n + 2, g(n) = n, f(n) = Ωg(n)
  
  3n + 2 <= Cn
  3n + 2 <= n
  2n >= -2
  n >= -1
  
  c = 1, n >= 1
  

• Θ (Big-theta) notation (average case, lower & upper sandwich), 0 <= c1*g(n) <= f(n) <= c2*g(n)

  f(n) = 3n + 2, g(n) = n, f(n) = Θg(n)
  
  C1*n <= 3n + 2 <= C2*n
  
  3n + 2 <= C2*n            c1*n <= 3n + 2
  3n + 2 <= 4n              3n + 2 >= n
  n >= 2                    n >= -1
  
  c2 = 4, n >= 2            c1 = 1, n >= 1
  n >=2 // We must take a greater number, which is true for both
  

• Loops, if-else asymptotic analysis

Searching Techniques

• Searching is an operation that finds the location of a given element in a list.
• The search is said to be successful or unsuccessful depending on whether the element that is to be searched is found or not.

Linear Search

• Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[].
• In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.
• Pseudocode:

  procedure linear_search(list, value)
      for each item in the list
          if item == value
              return the item's location
          end if
      end for
  end procedure
  

• Linear search in C++ | Linear search in Python
• Analysis:
  • Best case O(1)
  • Average O(n)
  • Worst O(n)

Binary Search

• Binary Search is a searching algorithm for finding an element's position in a sorted array.
• It's fast and efficient, time complexity of binary search: O(log n)
• In this method:
  • To search an element we compare it with the element present at the center of the list. If it matches then the search is successful.
  • Otherwise, the list is divided into two halves:
    • One from the 0th element to the center element (first half)
    • Another from the center element to the last element (second half)
  • The search will now proceed in either of the two halves depending upon whether the element is greater or smaller than the center element.
  • If the element is smaller than the center element then the searching will be done in the first half, otherwise in the second half.
• It can be done recursively or iteratively.
• Pseudocode:

  procedure binary_search
      A ← sorted array
      n ← size of array
      x ← value to be searched
  
      set lowerBound = 1
      set upperBound = n 
  
      while x not found
          if upperBound < lowerBound 
              EXIT: x does not exists.
      
          set midPoint