"The quicksort algorithm has a worst-case running time of Θ(n^2 ) on an input array of n numbers. Despite this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is Θ(nlgn), and the constant factors hidden in the Θ(nlgn) notation are quite small. It also has the advantage of sorting in place, and it works well even in virtual-memory environments." [Introduction to algorithms]
Maximum-subarray problem
/*
Maximum-subarray problem
Given an array, find the subarray whose sum is the largest among all of the subarrays. The program prints the left index, right index and the sum of the subarray. The maximum-subarray problem is interesting only when the array containssome negative numbers.
The program uses divide-and-conquer algorithm described on Page68, Introduction to Algorithms.
Of course, this problem can be solved by using loops directly as the second program does.
*/
Maximum-subarray problem
Given an array, find the subarray whose sum is the largest among all of the subarrays. The program prints the left index, right index and the sum of the subarray. The maximum-subarray problem is interesting only when the array containssome negative numbers.
The program uses divide-and-conquer algorithm described on Page68, Introduction to Algorithms.
Of course, this problem can be solved by using loops directly as the second program does.
*/
[C++]Polynomial Class
Polynomial Class
The eval member function uses Horner algorithm.
File: polynomial.h
The eval member function uses Horner algorithm.
File: polynomial.h
A 0-1 Knapsack Problem
/*
Input two integers M and N. Find all possible ways that the sum of numbers chosen from 1, 2,3,...N equals M. Print all possible combinations.
*/
Input two integers M and N. Find all possible ways that the sum of numbers chosen from 1, 2,3,...N equals M. Print all possible combinations.
*/
Combination of letters
// List all combinations of letters in a string. Suppose no letter is repeated.
// traverse letters from the first one to the last one.
// combination[ ] is used to save the result of each combination.
// layer indicates the number of letters in the combination, also it tells you
// the position of the newly visited letter in combination[ ]
// layer increases by one in each recursion
// traverse letters from the first one to the last one.
// combination[ ] is used to save the result of each combination.
// layer indicates the number of letters in the combination, also it tells you
// the position of the newly visited letter in combination[ ]
// layer increases by one in each recursion
Sieve of Eratosthen algorithm
Sieve of Eratosthen algorithm is used to find primes.
The following codes(modified) are from Algorithms in C++ and Core Java Volume I.
The following codes(modified) are from Algorithms in C++ and Core Java Volume I.
Palindrome
The following program determines if a given string is a palindrome.
Another way to do this is first to copy the string to another char[] and remove the non- alphabet characters from the string. Then copy it to the third char array and reverse the order of the string . Finally compare the two strings.
Another way to do this is first to copy the string to another char[] and remove the non- alphabet characters from the string. Then copy it to the third char array and reverse the order of the string . Finally compare the two strings.
Subscribe to:
Posts (Atom)