Skip to content

CS502 - Fundamentals of Algorithms

11 Topics 57 Posts
  • 0 Votes
    6 Posts
    626 Views
    cyberianC

    Q.2
    Solution:
    Method 1
    0e7322a1-5dce-4ad9-acd1-733be402ae4b-image.png

    Method 2
    fc8e2c51-4c04-4b4e-9bd0-b2b542a413f2-image.png

    a29b0121-e9be-4b74-aea3-d49d9f189d4c-image.png

  • 0 Votes
    15 Posts
    4k Views
    cyberianC

    @Ainhashmi you can choose in categories where you expect.

  • 0 Votes
    2 Posts
    103 Views
    M

    @moaaz said in The Huffman algorithm finds for?:

    Optimal

    If optimal is measured by average code word length, Huffman’s algorithm gives optimal codes, and the redundancy can be measured as the difference between the average code word length and Shannon’s entropy. If the objective function is replaced by an exponentially weighted average, then a simple modification of Huffman’s algorithm gives optimal codes. The redundancy can now be measured as the difference between this new average and Renyi’s generalization of Shannon’s entropy. By decreasing some of the codeword lengths in a Shannon code, the upper bound on the redundancy given in the standard proof of the noiseless source coding theorem is improved. The lower bound is improved by randomizing between codeword lengths, allowing linear programming techniques to be used on an integer programming problem. These bounds are shown to be asymptotically equal, providing a new proof of Kricevski’s results on the redundancy of Huffman codes. These results are generalized to the Renyi case and are related to Gallager’s bound on the redundancy of Huffman codes.

  • 0 Votes
    2 Posts
    375 Views
    M

    @moaaz said in What is generally true of Adjacency List and Adjacency Matrix representations of graphs?:

    Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
  • 0 Votes
    1 Posts
    98 Views
    No one has replied
  • 0 Votes
    2 Posts
    729 Views
    zareenZ

    @zareen said in CS502 GDB 1 Solution and Discussion:

    require to find the shortest possible route algorithm

    Dijkstra’s algorithm (or Dijkstra’s Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
    Reff

    Dijkstra’s algorithm to find the shortest path between a and b. It picks the unvisited vertex with the low distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor’s distance if smaller. Mark visited (set to red) when done with neighbors.
    220px-Dijkstra_Animation.gif
    Dijkstra’s algorithm

    llustration of Dijkstra’s algorithm finding a path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the “tentative” set (aka set of “unvisited” nodes). Filled nodes are visited ones, with color representing the distance: the greener, the closer. Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular wavefront as Dijkstra’s algorithm uses a heuristic identically equal to 0.
    Dijkstras_progress_animation.gif

    A demo of Dijkstra’s algorithm based on Euclidean distance. Red lines are the shortest path covering, i.e., connecting u and prev[u]. Blue lines indicate where relaxing happens, i.e., connecting v with a node u in Q, which gives a shorter path from the source to v.
    DijkstraDemo.gif

  • 0 Votes
    7 Posts
    852 Views
    zareenZ

    Q.1 Answer
    09060a11-e58a-4510-b329-9e0ee2e4ea71-image.png

    Q.2 Answer
    3cd1afd9-1b1a-40ab-b8e3-96784cc3c253-image.png

  • 0 Votes
    6 Posts
    304 Views
    zareenZ

    Solution:
    Question No. 01: The name of the algorithm being used for sorting the given array has given below.
    Selection sort
    Question No. 02: The Pseudo code for the algorithm used for sorting the given array has given below.

    Pseudo code:
    1 Selection sort (A)
    {
    2 For i 1 to A.lenght-1
    {
    3 imin i
    4 for j i+1 to A.length
    {
    5 If (A[j] < A[imin])
    Imin j
    }
    6 Temp A[i]
    7 A[i] A[imin]
    8 A[imin] Temp
    }
    }

    Question No. 03: The step by stem analysis of the algorithm designed in question 2 is as follow,

    The time taken by each statement (step) is given as follows,

    b8c2d4d9-76e3-4841-94a7-e8c1a8202f51-image.png

    Selection sort (A) Cost Times

    {
    For i 1 to A.length-1 |c1 | n
    {
    imin i--------------------> c2 n-1
    for j i+1 to A.length
    { c3 n+n-1+…1=n(n+1)/2
    If (A[j] < A[imin])
    imin j
    }
    Temp A[i] c4 n-1
    A[i] A[imin] c5 n-1
    A[imin] Temp c6 n-1
    }
    }

    Total time T(n) can be calculated as follows,

    T(n)= c1n+c2(n-1)+c3(n(n+1)/2)+c4(n-1)+c5(n-1)+c6(n-1)
    c1n+c2n-c2+c3 (n2+n/2) +c4n-c4+c5n-c5+c6n-c6 collect the like terms
    c3n2/2+ (c1+c2+c3/2+c4+c5+c6) n + (-c2-c4-c5-c6)

    This is equivalent to a polynomial an2+bn+c
    Therefore T (n) = Big O (n2) by taking the highest order term of the equation.
    Note: a, b, c in polynomial represents constants

    // Ignoring constant terms

    T(n) = O (n2)

  • 0 Votes
    6 Posts
    2k Views
    zareenZ

    Current CS502 Paper Mid-Fall-2019

    Cs502 Divide and conquer (3) Catalan number(5) Chain matrix multiple cation (5) Bubble sort(5) Property of algorithms (3) McQ from handout CS-502 Today's Mid Term Paper MCQ's Mostly from pastpers 2 qs marks 3 and 3 qs marks 5 1.Sorting and write its types..5 marks 2. Counting sort numbers are given.. 5 marks 3.Any Program.. i don't know this qs..5 marks 4. Edit Transcript.. 3 marks 5. Upper bound and lower bound
  • 1 Votes
    9 Posts
    314 Views
    zareenZ

    @zareen said in CS502 Assignment No. 01 Solution and Discussion:

    Question No 02: (Marks: 10)
    You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 01.

    Solution:
    Question No. 02: The step by stem analysis of the algorithm designed in question 1 is as follow,

    The time taken by each statement (step) is given as follows,

    Step 1: C1 // Execute only 1 time or Constant Time or O (1)
    Step 2: C2 // Execute only 1 time or Constant Time or O (1)
    Step 3: n -2 // Execute n -2 times
    Step 4: n -2 // Execute n -2 times
    Step 5: n – 2 // Execute n -2 times
    Step 6: C3 // Execute only 1 time or Constant Time or O (1)
    Step 7: C4 // Execute only 1 time or Constant Time or O (1)
    Step 8: C5 // Execute only 1 time or Constant Time or O (1)
    Step 9: C6 // Execute only 1 time or Constant Time or O (1)

    Total time T(n) can be calculated as follows,

    T(n) = C1 + C2 + (n -2 ) + (n -2 ) + (n -2 ) + C3 + C4 + C5 + C6
    T(n) = C1 + C2 + n -2 + n -2 + n -2 + C3 + C4 + C5 + C6
    T(n) = C1 + C2 + n + n + n - 6 + C3 + C4 + C5 + C6
    T(n) = 3n + C1 + C2 + C3 + C4 + C5 + C6 -6
    T(n) = 3n + (C1 + C2 + C3 + C4 + C5 + C6 -6)
    T(n) = 3n + C7 // C7 = (C1 + C2 + C3 + C4 + C5 + C6 -6)
    T(n) = n // Ignoring constant terms

    Or T(n) = O (n )

  • 0 Votes
    1 Posts
    192 Views
    No one has replied