ch3

avatar
Created by
Hab 1

Cards (74)

  • Greedy Method

    Among all the algorithmic approaches, the simplest and straightforward approach
  • Greedy method

    • The decision is taken on the basis of current available information without worrying about the effect of the current decision in future
    • Greedy algorithms build a solution part by part, choosing the next part in such a way that it gives an immediate benefit
    • This approach never reconsiders the choices taken previously
    • This approach is mainly used to solve optimization problems
  • Greedy method

    An algorithmic paradigm based on heuristic that follows local optimal choice at each step with the hope of finding global optimal solution
  • Greedy method is easy to implement and quite efficient in most of the cases
  • In many problems, Greedy algorithm does not produce an optimal solution though it gives an approximate (near optimal) solution in a reasonable time
  • Components of Greedy Algorithm

    • A candidate set: A solution is created from this set
    • A selection function: Used to choose the best candidate to be added to the solution
    • A feasibility function: Used to determine whether a candidate can be used to contribute to the solution
    • An objective function: Used to assign a value to a solution or a partial solution
    • A solution function: Used to indicate whether a complete solution has been reached
  • Application of Greedy Method

    • Job sequencing with deadline
    • Finding the shortest path between two vertices using Dijkstra's algorithm
    • Finding the minimal spanning tree in a graph using Prim's/Kruskal's algorithm
    • Huffman Code
  • In many problems, Greedy algorithm fails to find an optimal solution, moreover it may produce a worst solution. Problems like Travelling Salesman and Knapsack cannot be solved using this approach
  • Job Sequencing with Deadline

    1. Sort the jobs in descending order of profit
    2. If the maximum deadline is x, make an array of size x. Each array index is set to -1 initially as no jobs have been performed yet
    3. For every job check if it can be performed on its last day
    4. If possible mark that index with the job id and add the profit to our answer
    5. If not possible, loop through the previous indexes until an empty slot is found
  • The complexity of the Job-Sequencing-With-Deadline algorithm is O(n^2)
  • Job Sequencing with Deadline

    • Job 2 is selected as it can be completed within its deadline and contributes maximum profit
    • Job 1 is selected as it gives more profit compared to Job 4
    • Job 4 cannot be selected as its deadline is over, hence Job 3 is selected as it executes within its deadline
    • Job 5 is discarded as it cannot be executed within its deadline
  • The total profit of the sequence (Job 2, Job 1, Job 3) is 100 + 60 + 20 = 180
  • Dijkstra's algorithm

    • A solution to the single-source shortest path problem in graph theory
    • Works on both directed and undirected graphs, however all edges must have nonnegative weights
  • Dijkstra's algorithm

    1. dist[s] ← 0 (distance to source vertex is zero)
    2. for all v ∈ V–{s} do dist[v] ← ∞ (set all other distances to infinity)
    3. S ← ∅ (S, the set of visited vertices is initially empty)
    4. Q ← V (Q, the queue initially contains all vertices)
    5. while Q ≠ ∅ do
    6. u ← mindistance(Q,dist) (select the element of Q with the min. distance)
    7. S ← S ∪ {u} (add u to list of visited vertices)
    8. for all v ∈ neighbors[u] do
    9. if dist[v] > dist[u] + w(u, v) (if new shortest path found)
    10. then dist[v] ← d[u] + w(u, v) (set new value of shortest path)
    11. return dist
  • The running time of Dijkstra's algorithm is O((|E|+|V|) log |V|) when implemented using a binary heap or priority queue
  • Minimum spanning trees

    Prim's/Kruskal's algorithm
  • Kruskal's algorithm

    1. Select the shortest edge in a network
    2. Select the next shortest edge which does not create a cycle
    3. Repeat step 2 until all vertices have been connected
  • Prim's algorithm

    1. Select any vertex
    2. Select the shortest edge connected to that vertex
    3. Select the shortest edge connected to any vertex already connected
    4. Repeat step 3 until all vertices have been connected
  • Kruskal's algorithm

    1. Select the shortest edge: ED (2)
    2. Select the next shortest edge which does not create a cycle: AB (3)
    3. Select the next shortest edge which does not create a cycle: CD (4) or AE (4)
    4. Select the next shortest edge which does not create a cycle: AE (4)
    5. Select the next shortest edge which does not create a cycle: EF (5)
    6. All vertices have been connected. The solution is: ED (2), AB (3), CD (4), AE (4), EF (5). Total weight of tree: 18
  • Prim's algorithm

    1. Select any vertex: A
    2. Select the shortest edge connected to that vertex: AB (3)
    3. Select the shortest edge connected to any vertex already connected
  • Kruskal's Algorithm

    1. Select the next shortest edge which does not create a cycle
    2. All vertices have been connected
  • Kruskal's Algorithm

    Builds a minimum spanning tree by adding edges in order of increasing weight, avoiding cycles
  • Vertices in Kruskal's Algorithm

    • A
    • F
    • B
    • C
    • D
    • E
  • Edge weights in Kruskal's Algorithm

    • 2
    • 7
    • 4
    • 5
    • 8
    • 6
    • 4
    • 5
    • 3
    • 8
  • Prim's Algorithm

    1. Select any vertex
    2. Select the shortest edge connected to any vertex already connected
  • Prim's Algorithm

    Builds one tree, starting from an arbitrary "root" vertex. At each step, adds the lightest edge crossing the cut between the tree and the remaining vertices
  • Prim's Algorithm uses a priority queue to find the lightest edge quickly
  • The key of a vertex in the priority queue is the minimum weight of any edge connecting it to a vertex already in the tree
  • Huffman Coding

    • Lossless compression technique that exploits redundancy in data
    • Lossy compression technique that exploits redundancy and human perception, used for audio/image/video
  • Building Huffman Coding Tree

    1. Begin with forest of single trees
    2. While priority queue contains two or more nodes, create new node by dequeuing two nodes and making them left and right subtrees, with frequency of new node equal to sum of frequencies of children
  • Characters in Huffman Coding Example

    • S
    • E
    • H
    • R
    • L
    • W
    • G
    • T
    • M
  • Huffman coding represents the decoding process as a binary tree, where 0 means go left and 1 means go right
  • Huffman coding algorithm has a time complexity of O(n log n)
  • Knapsack Problem

    Given a set of items with weights and values, determine the number of each to include in a collection so that the total weight is less than or equal to a given limit and the total value is maximized
  • Fractional Knapsack Problem

    Allows fractions of items to be included to maximize total value within the weight limit
  • 0-1 Knapsack Problem

    Each item must be either fully included or fully excluded to maximize total value within the weight limit
  • The brute-force approach to the 0-1 Knapsack Problem has a time complexity of O(2^n)
  • Traveling Salesman Problem

    Find the shortest tour that visits each city exactly once and returns to the starting city
  • Greedy Method

    Among all the algorithmic approaches, the simplest and straightforward approach
  • Greedy method

    • The decision is taken on the basis of current available information without worrying about the effect of the current decision in future
    • Greedy algorithms build a solution part by part, choosing the next part in such a way that it gives an immediate benefit
    • This approach never reconsiders the choices taken previously
    • This approach is mainly used to solve optimization problems