Ediquation

Algorithmic Complexity

Introduction

Algorithmic complexity is concerned about how fast or slow particular algorithm performs. We define complexity as a numerical function T(n) - time versus the input size n. We want to define time taken by an algorithm without depending on the implementation details. But you agree that T(n) does depend on the implementation! A given algorithm will take different amounts of time on the same inputs depending on such factors as: processor speed; instruction set, disk speed, brand of compiler and etc. The way around is to estimate efficiency of each algorithm asymptotically. We will measure time T(n) as the number of elementary "steps" (defined in any way), provided each such step takes constant time.
Let us consider two classical examples: addition of two integers. We will add two integers digit by digit (or bit by bit), and this will define a "step" in our computational model. Therefore, we say that addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c * n, where c is time taken by addition of two bits. On different computers, additon of two bits might take different time, say c1 and c2, thus the additon of two n-bit integers takes T(n) = c1 * n and T(n) = c2* n respectively. This shows that different machines result in different slopes, but time T(n) grows linearly as input size increases.
The process of abstracting away details and determining the rate of resource usage in terms of the input size is one of the fundamental ideas in computer science.

Asymptotic Notations

The goal of computational complexity is to classify algorithms according to their performances. We will represent the time function T(n) using the "big-O" notation to express an algorithm runtime complexity. For example, the following statement
T(n) = O(n2)
says that an algorithm has a quadratic time complexity.

Definition of "big Oh"

For any monotonic functions f(n) and g(n) from the positive integers to the positive integers, we say that f(n) = O(g(n)) when there exist constants c > 0 and n0 > 0 such that
f(n) ≤ c * g(n), for all n ≥ n0
Intuitively, this means that function f(n) does not grow faster than g(n), or that function g(n) is an upper bound for f(n), for all sufficiently large n→∞
Here is a graphic representation of f(n) = O(g(n)) relation:
Examples:
  • 1 = O(n)
  • n = O(n2)
  • log(n) = O(n)
  • 2 n + 1 = O(n)
The "big-O" notation is not symmetric: n = O(n2) but n2 ≠ O(n).
Exercise. Let us prove n2 + 2 n + 1 = O(n2). We must find such c and n0 that n 2 + 2 n + 1 ≤ c*n2. Let n0=1, then for n ≥ 1
1 + 2 n + n2 ≤ n + 2 n + n2 ≤ n2 + 2 n2 + n 2 = 4 n2
Therefore, c = 4.

Constant Time: O(1)

An algorithm is said to run in constant time if it requires the same amount of time regardless of the input size. Examples:
  • array: accessing any element
  • fixed-size stack: push and pop methods
  • fixed-size queue: enqueue and dequeue methods

Linear Time: O(n)

An algorithm is said to run in linear time if its time execution is directly proportional to the input size, i.e. time grows linearly as input size increases. Examples:
  • array: linear search, traversing, find minimum
  • ArrayList: contains method
  • queue: contains method

Logarithmic Time: O(log n)

An algorithm is said to run in logarithmic time if its time execution is proportional to the logarithm of the input size. Example:
  • binary search
Recall the "twenty questions" game - the task is to guess the value of a hidden number in an interval. Each time you make a guess, you are told whether your guess iss too high or too low. Twenty questions game imploies a strategy that uses your guess number to halve the interval size. This is an example of the general problem-solving method known as binary search:
locate the element a in a sorted (in ascending order) array by first comparing a with the middle element and then (if they are not equal) dividing the array into two subarrays; if a is less than the middle element you repeat the whole procedure in the left subarray, otherwise - in the right subarray. The procedure repeats until a is found or subarray is a zero dimension.
Note, log(n) < n, when n→∞. Algorithms that run in O(log n) does not use the whole input.

Quadratic Time: O(n2)

An algorithm is said to run in logarithmic time if its time execution is proportional to the square of the input size. Examples:
  • bubble sort, selection sort, insertion sort

Definition of "big Omega"

We need the notation for the lower bound. A capital omega Ω notation is used in this case. We say that f(n) = Ω(g(n)) when there exist constant c that f(n) ≥ c*g(n) for for all sufficiently large n. Examples
  • n = Ω(1)
  • n2 = Ω(n)
  • n2 = Ω(n log(n))
  • 2 n + 1 = O(n)

Definition of "big Theta"

To measure the complexity of a particular algorithm, means to find the upper and lower bounds. A new notation is used in this case. We say that f(n) = Θ(g(n)) if and only f(n) = O(g(n)) and f(n) = Ω(g(n)). Examples
  • 2 n = Θ(n)
  • n2 + 2 n + 1 = Θ( n2)

Analysis of Algorithms

The term analysis of algorithms is used to describe approaches to the study of the performance of algorithms. In this course we will perform the following types of analysis:
  • the worst-case runtime complexity of the algorithm is the function defined by the maximum number of steps taken on any instance of size a.
  • the best-case runtime complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size a.
  • the average case runtime complexity of the algorithm is the function defined by an average number of steps taken on any instance of size a.
  • the amortized runtime complexity of the algorithm is the function defined by a sequence of operations applied to the input of size a and averaged over time.
Example. Let us consider an algorithm of sequential searching in an array.of size n.
Its worst-case runtime complexity is O(n) 
Its best-case runtime complexity is O(1) 
Its average case runtime complexity is O(n/2)=O(n)

Amortized Time Complexity

Consider a dynamic array stack. In this model push() will double up the array size if there is no enough space. Since copying arrays cannot be performed in constant time, we say that push is also cannot be done in constant time. In this section, we will show that push() takes amortized constant time.
Let us count the number of copying operations needed to do a sequence of pushes.
 push() 
 copy 
 old array size 
 new array size 
 1  
 0  
 1  
 -  
 2  
 1  
 1  
 2  
 3  
 2  
 2  
 4  
 4  
 0  
 4  
 -  
 5  
 4  
 4  
 8  
 6  
 0  
 8  
 -  
 7  
 0  
 8  
 -  
 8  
 0  
 8  
 -  
 9  
 8  
 8  
 16  
We see that 3 pushes requires 2 + 1 = 3 copies.
We see that 5 pushes requires 4 + 2 + 1 = 7 copies.
We see that 9 pushes requires 8 + 4 + 2 + 1 = 15 copies.
In general, 2n+1 pushes requires 2n + 2n-1+ ... + 2 + 1 = 2n+1 - 1 copies.
Asymptotically speaking, the number of copies is about the same as the number of pushes. 
       2n+1 - 1
limit --------- = 2 = O(1)
 n→∞   2n + 1
We say that the algorithm runs at amortized constant time.





        C program to find sum of all even numbers between 1 to N using for loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <conio.h> 
   
int main() { 
    int num, temp; 
    long productOfDigit = 1; 
   
    /*
     * Take a number as input from user
     */ 
    printf("Enter a Number\n"); 
    scanf("%d", &num); 
    temp = num;
     
    while(num != 0){
        /* get the least significant digit(last digit)
         of number and multiply it to productofDigit */
        productOfDigit *= num % 10;
        /* remove least significant digit(last digit)
         form number */
        num = num/10;
    }
   
    printf("Product of digits of %d = %ld", temp, productOfDigit); 
   
    getch();
    return 0; 
}


C program to print all prime numbers between 1 to N using for loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>
#include<conio.h>
  
int main(){
  
    int N, i, j, isPrime, n;
     
    printf("To print all prime numbers between 1 to N\n");
    printf("Enter the value of N\n");
    scanf("%d",&N);
  
    /* For every number between 2 to N, check
    whether it is prime number or not */
    printf("Prime numbers between %d to %d\n", 1, N);
     
    for(i = 2; i <= N; i++){
        isPrime = 0;
        /* Check whether i is prime or not */
        for(j = 2; j <= i/2; j++){
             /* Check If any number between 2 to i/2 divides I
              completely If yes the i cannot be prime number */
             if(i % j == 0){
                 isPrime = 1;
                 break;
             }
        }
          
        if(isPrime==0 && N!= 1)
            printf("%d ",i);
    }
   getch();
   return 0;

A firewall is a network security system, either hardware- or software-based, that controls incoming and outgoing network traffic based on a set of rules..

Acting as a barrier between a trusted network and other untrusted networks -- such as the Internet -- or less-trusted networks -- such as a retail merchant's network outside of a cardholder data environment -- a firewall controls access to the resources of a network through a positive control model. This means that the only traffic allowed onto the network defined in the firewall policy is; all other traffic is denied.

History and types of firewalls

Computer security borrowed the term firewall from firefighting and fire prevention, where a firewall is a barrier established to prevent the spread of fire.
When organizations began moving from mainframe computers and dumb clients to the client-server model, the ability to control access to the server became a priority. Before firewalls emerged in the late 1980s, the only real form of network security was performed by access control lists (ACLs) residing on routers. ACLs determined which IP addresses were granted or denied access to the network.
The growth of the Internet and the resulting increased connectivity of networks meant that this type of filtering was no longer enough to keep out malicious traffic as only basic information about network traffic is contained in the packet headers. Digital Equipment Corp. shipped the first commercial firewall, DEC SEAL, in 1992, and firewall technology has since evolved to combat the increasing sophistication of cyberattacks.

Packet firewalls

The earliest firewalls functioned as packet filters, inspecting the packets that are transferred between computers on the Internet. When a packet passes through a packet-filter firewall, its source and destination address, protocol, and destination port number are checked against the firewall's rule set. Any packets that aren't specifically allowed onto the network are dropped (i.e., not forwarded to their destination). For example, if a firewall is configured with a rule to block Telnet access, then the firewall will drop packets destined for TCP port number 23, the port where a Telnet server application would be listening.
Packet-filter firewalls work mainly on the first three layers of the OSI reference model (physical, data-link and network), although the transport layer is used to obtain the source and destination port numbers. While generally fast and efficient, they have no ability to tell whether a packet is part of an existing stream of traffic. Because they treat each packet in isolation, this makes them vulnerable to spoofing attacks and also limits their ability to make more complex decisions based on what stage communications between hosts are at.

Stateful firewalls

In order to recognize a packet's connection state, a firewall needs to record all connections passing through it to ensure it has enough information to assess whether a packet is the start of a new connection, a part of an existing connection, or not part of any connection. This is what's called "stateful packet inspection." Stateful inspection was first introduced in 1994 by Check Point Software in its FireWall-1 software firewall, and by the late 1990s, it was a common firewall product feature.
This additional information can be used to grant or reject access based on the packet's history in the state table, and to speed up packet processing; that way, packets that are part of an existing connection based on the firewall's state table can be allowed through without further analysis. If a packet does not match an existing connection, it's evaluated according to the rule set for new connections.

Application-layer firewalls

As attacks against Web servers became more common, so too did the need for a firewall that could protect servers and the applications running on them, not merely the network resources behind them. Application-layer firewall technology first emerged in 1999, enabling firewalls to inspect and filter packets on any OSI layer up to the application layer.
The key benefit of application-layer filtering is the ability to block specific content, such as known malware or certain websites, and recognize when certain applications and protocols -- such as HTTP, FTP and DNS -- are being misused.
Firewall technology is now incorporated into a variety of devices; many routers that pass data between networks contain firewall components and most home computer operating systems include software-based firewalls. Many hardware-based firewalls also provide additional functionality like basic routing to the internal network they protect.

Proxy firewalls

Firewall proxy servers also operate at the firewall's application layer, acting as an intermediary for requests from one network to another for a specific network application. A proxy firewall prevents direct connections between either sides of the firewall; both sides are forced to conduct the session through the proxy, which can block or allow traffic based on its rule set. A proxy service must be run for each type of Internet application the firewall will support, such as an HTTP proxy for Web services.

Firewalls in the perimeterless age

The role of a firewall is to prevent malicious traffic reaching the resources that it is protecting. Some security experts feel this is an outdated approach to keeping information and the resources it resides on safe. They argue that while firewalls still have a role to play, modern networks have so many entry points and different types of users that stronger access control and security at the host is a better technological approach to network security.

Virtualization strategies such as virtual desktop infrastructure can dynamically respond to different scenarios by offering tailored access control to applications, files, Web content and email attachments based on the user's role, location, device and connection. This approach to security does provide additional protection that a firewall can't, but information security requires defense-in-depth, and firewalls still offer essential low-level protection as well as important logging and auditing functions.






কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

এতে সদস্যতা: পোস্টগুলি (Atom)