Scribd Logo
Upload

Welcome to Scribd!

  • 32 views

    CS702 - Advanced Algorithms Analysis and Design: Instructions To Solve Assignments

    Uploaded by

    mc210202963 MAMOONA RANA
    The document provides instructions for an assignment in a course on advanced algorithms analysis and design. It states that students must solve assignments independently and cheating will result in zero marks or an F grade. It also notes that no late assignments will be accepted. The document includes two questions to answer in one's own words for marks, checking for plagiarism.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd

    CS702 - Advanced Algorithms Analysis and Design: Instructions To Solve Assignments

    Uploaded by

    mc210202963 MAMOONA RANA
    32 views4 pages
    The document provides instructions for an assignment in a course on advanced algorithms analysis and design. It states that students must solve assignments independently and cheating will result in zero marks or an F grade. It also notes that no late assignments will be accepted. The document includes two questions to answer in one's own words for marks, checking for plagiarism.

    Original Title

    Fall 2017_CS702_2_SOL

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides instructions for an assignment in a course on advanced algorithms analysis and design. It states that students must solve assignments independently and cheating will result in zero marks or an F grade. It also notes that no late assignments will be accepted. The document includes two questions to answer in one's own words for marks, checking for plagiarism.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    32 views4 pages

    CS702 - Advanced Algorithms Analysis and Design: Instructions To Solve Assignments

    Uploaded by

    mc210202963 MAMOONA RANA
    The document provides instructions for an assignment in a course on advanced algorithms analysis and design. It states that students must solve assignments independently and cheating will result in zero marks or an F grade. It also notes that no late assignments will be accepted. The document includes two questions to answer in one's own words for marks, checking for plagiarism.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 4

    Virtual University of Pakistan

    Fall 2017

    CS702 – Advanced Algorithms Analysis and Design

    Assignment 2

    Instructions to Solve Assignments

    The purpose of the assignments is to give students hands on practice. It is expected that
    students will solve assignments themselves.The Following rules that will apply during
    the evaluation of the assignment.

     Cheating from any source will result in zero marks in the assignment.
     Any student found cheating in any two of the assignments submitted during the
    course will be awarded "F" grade in the course.
     No assignment after the due date will be accepted.

    1
    Virtual University of Pakistan
    Fall 2017

    Answer the following questions in your own words. Plagiarism will be checked for
    each question. Marks will be awarded on the basis of the answer and plagiarism
    report.

    Question 1 (25 Marks)


    For the sequence of matrices, given below, compute the order of the product,
    A1.A2.A3.A4.A5, in such a way that minimizes the total number of scalar multiplications,
    using Dynamic Programming.

    Order of A1 = 20 x 30
    Order of A2 = 30 x 10
    Order of A3 = 10 x 15
    Order of A4 = 15 x 25
    Order of A5 = 25 x 15
    Solution:
    Following Recursive formulation will be used to device the solution

    Main diagonal will be filled with the base case

    m[i, j] 1 2 3 4 5
    1 0 6000 9000 14750 16500
    2 0 4500 11250 12000
    3 0 3750 7500
    4 0 5625
    5 0

    s[i, j] 2 3 4 5
    1 1 2 2 2
    2 2 2 2
    3 3 4
    4 4

    2
    Virtual University of Pakistan
    Fall 2017

    Question 2 (25 Marks)


    There are two assembly lines, as shown in the diagram below, each with 6 stations. The
    auto is required to go through from all of these 6 stations from left to right. Nodes
    represent stations. The assembly time at each station is shown at each node. The entering
    and exit times for an auto are also given. The transfer time is represented at the edges
    when an auto moves to next station on a different line. There is no transfer time if it stays
    on the same line. Determine which stations to choose from lines 1 and 2 to minimize total
    time through the factory. Also compute the optimal value in terms of time. Use Dynamic
    Programming Approach. You need to calculate fi[j], li[j], f*, l* and the
    optimal path.

    5 5 8 6 4 7
    1 2

    5 4 1 6 3
    In Out

    1 4 5 3 1
    4 3 7 6 2 5 7 6

    Solution:

    fi[j] 1 2 3 4 5 6
    1 6 11 19 25 29 35
    2 7 14 20 22 27 34

    li[j] 2 3 4 5 6
    1 1 1 1 1/2 2
    2 2 2 1/2 2 2

    f* = 37, l* = 1

    3
    Virtual University of Pakistan
    Fall 2017

    You might also like