Paper Of Design and Analysis Of Algorithm Department Of Computer Science and Software Engineering

Let’s cut to the chase: Design and Analysis of Algorithms (DAA) is not a subject. It’s a superpower. This past paper is your trial by fire to prove you don’t just write code—you engineer solutions that are elegant, efficient, and scalable. It’s the difference between brute-forcing your way through a maze and deriving a theorem for the shortest path.

Forget memorizing syntax. This is about raw, analytical problem-solving. It asks the fundamental question: “Given a problem and unlimited computational power in theory, but very real constraints in practice, what is the most intelligent way to make the machine work?”

What This Paper Actually Measures: Your Computational Intelligence

1. The Two Pillars: Design & Analysis
The title says it all. You are tested on a dual mastery:

• Design: Can you craft a clever, step-by-step strategy (an algorithm) to solve a problem?
• Analysis: Can you prove why your strategy is good? This means rigorously analyzing its Time Complexity (how fast it runs) and Space Complexity (how much memory it uses) using Big O, Θ (Theta), and Ω (Omega) notation.

2. The Algorithmic Toolbox: Recognizing Patterns in Chaos
Great algorithm designers see problems not as unique monsters, but as members of familiar families. The paper tests your fluency with these core algorithmic paradigms:

• Divide and Conquer: The art of breaking a problem into independent subproblems, solving them, and combining results. You’ll dissect Merge Sort and QuickSort, derive their recurrences, and solve them to prove O(n log n) complexity. You’ll apply this to problems like finding the closest pair of points.
• Greedy Algorithms: The strategy of making the locally optimal choice at each step, hoping it leads to a global optimum. You’ll prove when it works (Huffman coding, Activity Selection) and when it fails. A classic question: *”Prove that the greedy choice for Fractional Knapsack is optimal, but for 0/1 Knapsack it is not.”*
• Dynamic Programming (DP): The paradigm of solving overlapping subproblems and storing their solutions to avoid recomputation. This is where many students hit a wall. You’ll need to:
  1. Identify the optimal substructure (how the optimal solution incorporates optimal solutions to subproblems).
  2. Define the recurrence relation (the mathematical heart of the DP).
  3. Implement it (either top-down with memoization or bottom-up with tabulation).
     Problems: Fibonacci, Longest Common Subsequence, Matrix Chain Multiplication, Floyd-Warshall. You must not just solve them, but explain why DP is applicable.
• Graph Algorithms: Modeling relationships. You’ll implement and analyze:
  • Traversal: BFS (shortest path on unweighted graphs) and DFS (cycle detection, topological sort).
  • Shortest Path: Dijkstra’s (greedy, for non-negative weights) and Bellman-Ford (handles negative weights).
  • Minimum Spanning Tree: Kruskal’s (uses a Union-Find data structure) and Prim’s algorithms.
• Backtracking & Branch-and-Bound: Systematic search for solutions, like solving the N-Queens or 0/1 Knapsack problem by exploring a state-space tree and pruning futile branches.

3. The “Hard” Problems: P, NP, and Intractability
The course often culminates in a philosophical and practical bombshell: NP-Completeness. You won’t solve NP-Complete problems (that’s the million-dollar question), but you must:

• Understand the classes P (problems solvable in polynomial time) and NP (problems whose solutions can be verified in polynomial time).
• Prove a problem is NP-Complete by performing a polynomial-time reduction from a known NP-Complete problem (like 3-SAT or Vertex Cover) to your new problem.
• This section tests your ability to recognize when you’re facing an intrinsically hard problem, so you can seek approximations or heuristics instead of an exact solution.

The Paper’s Ultimate Challenge: Proof and Justification
This is not a coding exam. You might write pseudocode, but the primary currency is your reasoning.
You will be asked:

• “Prove the correctness of this greedy algorithm.”
• *”Solve this recurrence relation: T(n) = 2T(n/2) + O(n).”*
• “Show that the Hamiltonian Cycle problem is NP-Complete by reducing from the Traveling Salesman Problem.”

How to Conquer This Past Paper:

1. Master the “Three-Step” Approach for Any Problem:
   • Step 1 (Understand): Restate the problem in your own words. Identify input, output, and constraints.
   • Step 2 (Design): Which paradigm fits? Sketch the high-level strategy.
   • Step 3 (Analyze): Derive the time/space complexity before you write pseudocode. If it’s not efficient enough, go back to Step 2.
2. Practice Deriving Recurrences and Solving Them. This is a mathematical muscle you must build. Know the Master Theorem inside out.
3. Draw, Draw, Draw. Draw graphs, draw recursion trees, draw DP tables. Visualizing the data structure or the process is 90% of the solution.
4. For NP-Completeness, Practice Reductions. This is a unique skill. Work through standard reductions until you understand the template: transform an instance of known problem A into an instance of new problem B in polynomial time, preserving the “yes/no” answer.
5. Write Clean, Commented Pseudocode. Use clear variable names. Write one-line comments that state the intent of each block (e.g., // Relax all edges in Bellman-Ford).

This past paper is your intellectual forge. It transforms you from someone who can solve problems into someone who can invent and validate the methods of solution themselves. Passing it with understanding means you hold the master key to computational efficiency—a skill that defines the very best engineers and scientists.

Design and analysis of algorithm Mid Term Examination in 2021
Q1:

1. Which parameters are considered essential to analysis a good algorithm?
2. Explain Flow Chart with the help of diagram and example?

Q2:

Write down Bubble Sort Algorithm?

Q3:

Perform Insertion Sort on following Array will all steps.

Q4:

Draw Flow Chart of following code.

int num;

cout<<”enter number”;

cin>>num;

if(num%2==0)

cout<<”even number”;

else

cout<<”odd number”;

return 0;

int marks;

cout<<”Enter Marks”;

cin>>marks;

if(marks<50)

cout<<”Fail”;

else if(marks>=50 && marks<60)

cout<<”3^rd”;

else if(marks>=60 &&marks<75)

cout<<”2^nd”;

else if(marks>=75 &&marks<100)

cout<<”1^st”;

return 0;

Q5:

Calculate Time Complexity of the following code.

Int n,i;

cin>>n;

int a=0;

i=n;

while(i>=1)

{

a=a+1;

i=i/2;

}

Design and analysis of algorithm paper II in 2020

Design and analysis of algorithm Sessional II in 2020

If total weight he can hold in his knapsack is 13 kg, which fruits and vegetables will be picked by the farmer? Also write down the algorithm for your approach with its analysis.

(Hint: Either he will take, or he will leave any particular item).

1. Which parameters are considered essential to analyze a good algorithm? [2]
2. Does input size matter? Suppose a program has run time O(n!) and the run time for

n = 10 is 1 second how much it will take for N=16  [3]

3. Write down Algorithm Development Process steps in diagram format.[5]
4. Running Time of an Algorithm depends on which parameter?[5]
5. Find time complexity of the following code. [5]

int sum = 0, j;

for (j=0; j < N; j++)

for (j=0; j < 100; j++)

sum = sum +j;

6. Find time complexity for the following [5]

int j,k;

for (j=0; j<N; j++)

for (k=2; k<8; k++)

sum += k+j;

Design and analysis of algorithm Final Paper in 2022

Q.NO.1

In Philippines, coins of 1, 5, 10, 25 centavos (officially called sentimo), IP, SP and 10P (officially called Peso) and currency notes of 20P, 50P, 100P, 500P, 1000P are used. How can we make the following denominations using Coin Change Problem with greedy approach? Also write an algorithm for coin change problem using dynamic programming with its complexity analysis. [10]

7.34 P

2891.45 P

390.21 P

74.58 P

0.99 P

-2: Apply Bellman-Ford Algorithm on the following graph. Show values after each iteration in a tabular form. S is the Starting node.

Q-5/Write down the algorithm for Huffman Encoding Technique with its complexity analysis. Consider your name and registration number as a string, apply Huffman Encoding Technique on this string (e.g. MUHAMMAD-ALI-MUSA-FA14-BCS-101).