Code Monkey home page Code Monkey logo

daa's Introduction

DAA

Design and Analysis of Algorithms

1 Assignment-1
Problem: Finding MIN, MAX, Second MIN, Second MAX in an integer array. Present 3 different logic. NO logic should use sorting. For example, one of the logic is to divide the array into two equal halves, find min/max/smin/smax for each, recursively update to get the final min/max/smin/smax.Implementation using C++ classes and objects.

2 Assignment-2
Some interesting questions from geeksforgeeks. You may look at the logic if required, however, you must code using C++.
1. Trapping Rain Water: https://practice.geeksforgeeks.org/problems/trapping-rain-water-1587115621/1
2. Implement two stacks in an array https://practice.geeksforgeeks.org/problems/implement-two-stacks-in-an-array/1
3. Triplet Sum in Array https://practice.geeksforgeeks.org/problems/triplet-sum-in-array-1587115621/1
4. Given an array write an algorithm to find the sum of all the possible sub-arrays.
Example: for array = {1, 2, 3, 4}, All sub arrays are:
[1], [12], [123], [1234],
[2], [23], [234]
[3], [34]
[4]

3 Assginment 3
Divide and Conquer Paradigm
1. Find MAX using 1-way, 2-way, 3-way, k-way approach
2. Count the number of negative numbers in an integer array using 2-way and 3-way approach.
3. Implement an Iterative and a Recursive algorithm for binary search, ternary search.

4 Assginment 4
1. Implement Classical Bubble, Selection, Insertion Sort, Merge Sort, Heap Sort.
2. Insertion Variant: Note that at iteration i, the first (i−1) elements are sorted and as part of the insertion sort algorithm, we look for the right position for A[i]. The position for A[i] is determined by performing a linear search on A[1..(i − 1)]. You are asked to implement the following; since A[1..(i − 1)] is sorted, perform binary search to identify the right position for A[i]. At each iteration i, perform binary search instead of linear search to identify the right position for A[i] so that at the end of the iteration A[1..i] is sorted.

5 Assginment-5
1. Hybrid Sorting: Insertion sort + Merge sort - Consider a large sized array (size at least 1000). Perform Merge sort recursively until the problem size becomes less than or equal to 20. When problem size becomes less than or equal to 20, perform Insertion sort.
2. Implement Quicksort with two pivots; suppose the pivot values are x and y such that x ≤ y, then Partition 1 has values < x, Partition 2 has values between x and y, and Partition 3 has values > y.
3. Given a set of m words (strings), arrange them in dictionary order.

6 Assginment-6
1. Implement Greedy Algorithms for Coin Change and Fractional Knapsack.
2. Implement Greedy Strategy for Matrix Chain Multiplication and Optimal Binary Search tree

7 Assginment-7
1. Implement dynamic programming for Coin Change and 0-1 Knapsack
2. Implement dynamic programming for Matrix Chain Multiplication and Optimal Binary Search tree
3. Problems involving polymorphism - check attachment.

8 Assginment-8
1. Implement DFS,BFS, Test for Bipartiteness, Cycle testing and test for connectedness.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.