| // C++ program for Assignment 1 Question 8 | |
| // We will count inversions using merge sort algorithm | |
| // and divide and conquer paradigm | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| long long _mergeSort(long long original_array[], long long arbitrary_array[], | |
| long long left_index, long long right_index); | |
| long long merge(long long original_array[], long long arbitary_array[], | |
| long long left_index, long long mid_index, long long right_index); |
| /* | |
| write an algorithm called Count-Values that takes as | |
| input two arrays A and C and then compute value of each counter and store it in array C. | |
| Your algorithm must have ϴ (n) time complexity. | |
| Hint C[ A[i] ] = C[ A[i] ] + 1 might be a useful statement here | |
| */ | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| /** |
| /* | |
| Following algorithm decides as if a given number M is the median of A or | |
| otherwise. The algorithm outputs either M if M is the median, a number M + 1 if median | |
| is larger than M and the number M – 1 otherwise. Give a tight bound on the running | |
| time of this algorithm | |
| */ | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| /** |
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.
For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0
In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.
Radix sort works by grouping the keys by individual digits that share the same significant position and value (place value). Radix sort uses counting sort as a subroutine to sort an array of numbers. Because integers can be used to represent strings (by hashing the strings to integers), radix sort works on data types other
Like merge sort, but unlike insertion sort, heapsort’s running time is O.n lg n/. Like insertion sort, but unlike merge sort, heapsort sorts in place: only a constant number of array elements are stored outside the input array at any time. Heapsort also introduces another algorithm design technique: using a data structure, in this case one we call a “heap,” to manage information. Not only is the heap data structure useful for heapsort, but it also makes an efficient priority queue. The term “heap” was originally coined in the context of heapsort, but it has since come to refer to “garbage-collected storage,” such as the programming languages Java and Lisp provide. Our heap data structure is not garbage-collected storage, and whenever we refer to heaps, we shall mean a data structure rather than an aspect of garbage collection.
The (binary) heap data structure is an array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element of the array
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. (“Programming” in this context refers to a tabular method, not to writing computer code.) Divide-and-conquer algorithms partition the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming applies when the subproblems overlap—that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem. We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with
In mathematics, the Fibonacci numbers, commonly denoted Fn form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F0 = 0 , F1 = 1 and
Fn = Fn-1 + Fn-2 ∀ n > 1.
One has F2 = 1. In some books, and particularly in old ones, F0, the "0" is omitted, and the Fibonacci sequence starts with F1 = F2 = 1. The beginning of the sequence is thus:
Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises wants to know the best way to cut up the rods.
We assume that we know, for i = 1,2,... the price pi in dollars that Serling Enterprises charges for a rod of length i inches. Rod lengths are always an integral number of inches.
Above figure gives us a sample price table.
The rod-cutting problem is the following. Given a rod of length n inches and a table of prices pi for i = 1,2,... n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces. Note that if the price pn for a rod of length n is large enough, an optimal solution may require no cutting at all. Consider the cas
