CodeCrucks

CodeCrucks

Assignments: Algorithm

Each assignment has 10 questions. Each student has to write only one question from each assignment. For every assignment, the student has to write the problem numbered with the last digit of his enrollment number. For example, if your enrollment number is 200160107007, then you have to write 7th question from all listed assignments. If your enrollment number is ending in 0 (for example, 200160107010), then you have to write 10th question from all assignments.

Assignment – 01:

  1. Given the function f(n) = 3n3 + 4n2 + 10, find its upper bound, lower bound and tight bound with necessary constants
  2. Discuss linear search and binary search. Also derive their best case, average case and worst case time complexities.
  3. Discuss Bubble sort with its algorithm, property, time complexity, pros and cons
  4. Discuss Selection sort with its algorithm, property, time complexity, pros and cons
  5. Discuss Insertion sort with its algorithm, property, time complexity, pros and cons
  6. Discuss Heap sort with its algorithm, property, time complexity, pros and cons
  7. Discuss Shell sort with its algorithm, property, time complexity, pros and cons
  8. Discuss Radix sort with its algorithm, property, time complexity, pros and cons
  9. Discuss Bucket sort with its algorithm, property, time complexity, pros and cons
  10. Discuss Counting sort with its algorithm, property, time complexity, pros and cons

Assignment – 02:

  1. What is an algorithm? What is the need for an algorithm?
  2. Write an example of equal sets.
  3. Write the subsets of {1,2,3}.
  4. If set A = {1, 3, 5}, B = {2, 4, 6} and C = {0, 2, 4, 6, 8}. Then write the universal set for all three sets.
  5. If A = {3, 5, 7, 9, 11}, B = {7, 9, 11, 13}, C = {11, 13, 15}. Find A ∩ (B ∪ C).
  6. Identify the range and domain the relation below: {(-2, 3), {4, 5), (6, -5), (-2, 3)}
  7. Check if the following ordered pairs are functions: W= {(1, 2), (2, 3), (3, 4), (4, 5),  Y = {(1, 6), (2, 5), (1, 9), (4, 3)}
  8. What is a function? How to Determine if a Relation is a Function?
  9. Solve the following linear equation: 2x+4y=20 and x+3y=30
  10. Discuss various types of functions

Assignment – 03:

All questions in this assignment are based on Greedy Algorithms. Write an explanation, algorithm, complexity analysis and suitable example for the first 8 problems.

  1. Binary knapsack
  2. Fractional knapsack
  3. Job scheduling
  4. Minimum Spanning tree using Prim’s Algorithm
  5. Minimum Spanning tree using Kruskal’s Algorithm
  6. Dijkstra’s Algorithm
  7. Activity Selection Problem
  8. Huffman Coding
  9. Compare and contrast: Greedy Algorithm vs. Divide and Conquer
  10. Compare and contrast: Greedy Algorithm vs. Dynamic Programming

Assignment – 04:

All questions in this assignment are based on Dynamic Programming. Write an explanation, algorithm, complexity analysis and suitable example for problems 4-10.

  1. Write a note on dynamic programming. Explain the principle of optimality.
  2. Compare and contrast: Divide and conquer vs. Dynamic Programming
  3. Compare and contrast: Branch and Bound vs. Dynamic Programming
  4. Binomial Coefficient
  5. Making change problem
  6. Assembly Line-Scheduling
  7. Knapsack problem
  8. All Points Shortest path
  9. Matrix chain multiplication
  10. Longest Common Subsequence.