Home /UOS — University of Sargodha /Main Campus /Design & Analysis of Algorithms

Design & Analysis of Algorithms UOS — University of Sargodha

Design & Analysis of Algorithms UOS — University of Sargodha — page 1

Discussion

Ask a question about this paper, or help someone else with theirs. Answers are emailed to whoever asked.

Your email is only used to send you replies and occasional Ustadni updates. It is never shown publicly.

Log in to post under your name

No questions yet — be the first to ask.

Need Paper? See all →

Need a paper or stuck on a question? Ask here — students reply and you get an email.

Ask about a paper
  • Ayesha Mustafa· 10 days ago

    BS ZOOLOGY first semester Animal diversity ZOOL 101 - university of Punjab 2025

    0 replies Reply →
  • Abubakar· 10 days ago

    Literary criticism

    1 reply Reply →
  • Guest· 11 days ago

    this paper consists of 60 marks but now we have 35 marks paper.

    1 reply Reply →
  • saira khalid· 1 month ago

    air past paper nhi h

    1 reply Reply →
Ad

Paper text

University of Sargodha

Paper: Analysis of Algorithms

Total Marks: 50

Time Allowed: 120 min

Roll #

Note: Attempt all questions.

Problem

1.

Answer the following questions briefly. Give examples where necessary.

i. Differentiate between min heap and max heap. [2]

ii. Prim's algorithm for computing MST and Dijikstra's algorithm for computing

shortest paths are similar in design. T/F [1]

iii. Differentiate between D.P approach and greedy approach. [4]

iv. Write down the recursive solution for assembly line scheduling. [2]

v. All pair shortest path can be calculated using greedy approach. T/F [1]

Problem

2.

i. Run Prim's MST algorithm on the graph given below. Also find how many MSTs

are there in this graph. [5+2]

ii. Write down the procedure that finds out the optimal solution in knapsack

problem. [3]

Problem

3.

i. Write down the recursive solution for knapsack problem. [1.5]

ii. Write down the recursive solution for all pair shortest path problem [1.5]

iii. Write down the procedure of Min-Heapify. [3]

iv. Suppose that all characters in the pattern P are different. Show how to

accelerate Naïve String Matcher? [4]