Analysis & Design of Algorithms(3466)-solved assighnments.aiou autumn 2015

solved Assighnments

AIOU













Course: Analysis & Design of Algorithms (3466) Semester: Autumn 2015
Level: BS (CS) Total Marks: 100
Credit: Half Credit Pass Marks: 50
ASSIGNMENT No. 1
Units: (1 – 4)

Note: All questions are compulsory. Each question carries equal marks.
Q. 1 a) Let c(n) and d(n) be asymptotically positive functions. Prove or disprove each of the following conjectures; (20)
  1. c(n) = θ(c(n/2))
  2. c(n) = O((c(n))2)
  3. c(n) = O(d(n)) implies d(n) = Ω(c(n))
b) Prove that Pr{A | C} + Pr{ | C} = 1.

Q. 2 a) Give examples of relations that are: (20)
  1. Reflexive and Symmetric but not Transitive
  2. Reflexive and Transitive but not Symmetric
  3. Symmetric and Transitive but not Reflexive
  1. Illustrate the operation of counting sort on the array A = [6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2].

Q. 3 a) Let A and B be finite sets, and f : A −> B be a function. Show that: (20)
  1. If f is injective, then |A| ≤ |B|
  2. If f is surjective, then |A| ≥ |B|
b) Show that any connected, undirected graph G = (V, E) satisfies |E| ≥ |V| - 1.

Q. 4 a) Illustrate the operation of Heap sort on the array A = [5, 13, 2, 25, 7, 17, 20, 8, 4].
  1. What is the running time of heap sort on an array A of length n that is already sorted in increasing order? What about decreasing order? (20)

Q. 5 Write notes on the following topics: (20)
ASSIGNMENT No. 2
Units:(5 – 8)
Total Marks: 100
Pass Marks: 50

Note: All questions are compulsory. Each question carries equal marks.

Q. 1 Give and explain each step with graph example for the trace of following graph traversal algorithms: (20)
a) Breadth first search
b) Depth first search

Q. 2 a) Demonstrate theinsertion of the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hashtable with collisions resolved by chaining. Let the table have 9slots, and let the hash function be h(k) = k mod 9.

Q. 3 a) Prove that thefractional knapsack problem has the greedy-choice property

b:What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers? (20)\
 
 
Q. 4 Execute the following algorithms for the given graph. Analyze the difference between the order of nodes or edges visited for the two algorithms: (20)
a) Prim’s algorithm
b) Kruskal’s algorithm
Q. 5 Write notes on the following topics: (20)













Analysis and Design of Algorithm (3466/3503) Credit Hours: 3(3+0)

Recommended Book:
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Course Outlines:
Unit No.1: Introduction
Introduction to Algorithm Analysis and Design
Growth of Functions, Summations Formulas and Properties

Unit No.2: Recurrences and Sets
Substitution, Iteration and Master Methods
Sets, Relations, Functions, Graph and Trees, Counting and Probability

Unit No.3: Sorting Algorithms
Heaps, Maintaining the Heap Property, Heap Sort algorithm,
Quick Sort, Performance and Analysis of Quick Sort

Unit No.4: Sorting in Linear Time and Order Statistics
Lower bounds for sorting, Counting sort, Radix and Bucket Sort, Medians and order Statistics

Unit No.5: Elementary Data Structures
Analysis of Stack, Queues and Linked List Algorithms, Hash Table and Functions, Binary Search Trees

Unit No.6: Dynamic Programming
Matrix Chain Multiplication, Longest Common Subsequence, Optimal Polygon Triangulation

Unit No.7: Greedy Algorithms
An activity selection problem, Huffman Codes, A Task Scheduling Problem, Amortized Analysis

Unit No.8: Graph Algorithms
Elementary Graph Algorithms, Breadth first search, Depth first search, Minimum Spanning Trees

Unit No.9: Single Source Shortest Paths
Shortest Paths and Relaxation, Dijkstra’s Algorithm, The Bellman-Ford Algorithm, Introduction to NP-Completeness


assginment No 1


You may like these posts