Please try writing mostly in english and interpret code if a bit of code is nece
ID: 3561676 • Letter: P
Question
Please try writing mostly in english and interpret code if a bit of code is necessary.... THANKS
TASK 1:
Apply Merge Sort to sort the following letters into alphabetical order.
A, L, G, O, R, I, T, H, M
TASK 2:
Apply Quick Sort, using the first version of the partition module given in lectures, to sort the following letters into alphabetical order:
A, L, G, O, R, I, T, H, M
TASK 3:
Apply Quick Sort, using the second version of the partition module given in lectures, to sort the following letters into alphabetical order:
A, L, G, O, R, I, T, H, M
TASK 4:
State some of the benefits of the second version of the partition module as opposed to the first version.
TASK 5:
Write an algorithm that finds items that are in List2 but not in List1.
TASK 6:
Write an algorithm that finds the median of a list of real numbers, i.e., the value for which half the values in the list are less than it.
TASK 7:
Describe a representation for partial solutions for the Torch problem.
TASK 8:
Describe a representation for partial solutions for the 4 Queens problem when the next queen may be in any column that does not yet contain a queen.
TASK 9:
Describe different representations for the partial solutions for the Knapsack problem, and discuss their advantages and disadvantages.
TASK 10:
Consider the following problem:
ZEROES +>
where every letter stands for a different decimal digit. Such problems are known as
Explanation / Answer
1) import java.util.Queue;
import java.util.LinkedList;
public class MergeSort {
public static void sort(char[] chars, int low, int right) {
if (low < right) {
int middle = (low + right) / 2;
sort(chars, low, middle);
sort(chars, middle + 1, right);
merge(chars, low, middle, right);
}
}
public static void merge(char[] chars, int low, int middle, int right) {
Queue<Character> queue1 = new LinkedList<Character>();
Queue<Character> queue2 = new LinkedList<Character>();
for (int i = low; i <= middle; i++) {
queue1.add(chars[i]);
}
for (int i = middle + 1; i <= right; i++) {
queue2.add(chars[i]);
}
int i = low;
while (!queue1.isEmpty() && !queue2.isEmpty()) {
if (queue1.peek() <= queue2.peek()) {
chars[i++] = queue1.poll();
} else {
chars[i++] = queue2.poll();
}
}
while (!queue1.isEmpty()) {
chars[i++] = queue1.poll();
}
while (!queue2.isEmpty()) {
chars[i++] = queue2.poll();
}
}
public static void sort(char[] chars) {
sort(chars, 0, chars.length - 1);
}
public static void sort(String string) {
sort(string.toCharArray());
}
public static void main(String[] args) {
String string = "ALGORITHM";
char[] chars = string.toCharArray();
MergeSort.sort(chars);
for (int i = 0; i < chars.length; i++) {
if (i > 0) { System.out.print(", "); }
System.out.print(chars[i]);
}
}
}
2) int partitionarray(char *item[],int left, int right)
{
int i = left;
int j = right;
char *temp;
char *x;
int pi=(left+right)/2;
x=item[pi];
WordSwap(x,item[right]);
j--;
while(i < j) {
while ((i<right) && (strcmp(item[i],x)>=0)) {
i++;
}
while((j>left) && (strcmp(item[j],x)<0)) {
j--;
}
if(i <= j) {
temp = item[i];
strcpy(item[i], item[j]);
strcpy(item[j], temp);
i++;
j--;
}
}
WordSwap(item[i++],item[right]);
return i;
}
3) int partitionarray(char *item[],int left, int right)
{
//int pi=(left+right)/2;
//int pi = left;
srand(time(NULL));
int pi=rand()%right;
//cout<< "pi"<<pi<<endl;
WordSwap(&item[pi],&item[right]);
pi=right;
int i = left;
int j = right-1;
char *x;
x=item[pi];
while(i <j) {
while ((item[i]<=x)&& (i<right)) {
i++;
}
while((item[j]>x)&&(j>left)) {
j--;
}
if(i <j) {
WordSwap(&item[i],&item[j]);
}
}
WordSwap(&item[i],&item[right]);
return i;
}
4) The second one the updated partition array function . This works fine for all the type of pivot selections.
5) implementation using python
# This computes the items of B that are not in A
a=hash(A) # Hopefully you at least have some sort of hash type
result=[] #empty list
for item in B:
if item not in a:
result.append(item)
6) implementation in python
import random
def partition(L, v):
smaller = []
bigger = []
for val in L:
if val < v: smaller += [val]
if val > v: bigger += [val]
return (smaller, [v], bigger)
def top_k(L, k):
v = L[random.randrange(len(L))]
(left, middle, right) = partition(L, v)
# middle used below (in place of [v]) for clarity
if len(left) == k: return left
if len(left)+1 == k: return left + middle
if len(left) > k: return top_k(left, k)
return left + middle + top_k(right, k - len(left) - len(middle))
def median(L):
n = len(L)
l = top_k(L, n / 2 + 1)
return max(l)
7) torch puzzle
class Program
{
public static int TotalTime(List<int> band, int n)
{
if (n < 3)
{
return band[n - 1];
}
else if (n == 3)
{
return band[0] + band[1] + band[2];
}
else
{
int temp1 = band[n - 1] + band[0] + band[n - 2] + band[0];
int temp2 = band[1] + band[0] + band[n - 1] + band[1];
if (temp1 < temp2)
{
return temp1 + TotalTime(band, n - 2);
}
else if (temp2 < temp1)
{
return temp2 + TotalTime(band, n - 2);
}
else
{
return temp2 + TotalTime(band, n - 2);
}
}
}
static void Main(string[] args)
{
// change the no of people crossing the bridge
// add or remove corresponding time to the list
int n = 4;
List<int> band = new List<int>() { 1, 2, 5, 10 };
band.Sort();
Console.WriteLine("The total time taken to cross the bridge is: " + Program.TotalTime(band, n));
Console.ReadLine();
}
}
8) Backtracking algorithm
The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.
1) Start in the leftmost column
2) If all queens are placed
return true
3) Try all rows in the current column. Do following for every tried row.
a) If the queen can be placed safely in this row then mark this [row,
column] as part of the solution and recursively check if placing
queen here leads to a solution.
b) If placing queen in [row, column] leads to a solution then return
true.
c) If placing queen doesn't lead to a solution then umark this [row,
column] (Backtrack) and go to step (a) to try other rows.
3) If all rows have been tried and nothing worked, return false to trigger backtracking
9) Brute Force ? It will be 2n possible combinations of items for
the knapsack.
? It is used for small instance of the knapsack
problem.
? It does not require much programming effort.
? It can be represented as tree format.
Dynamic Programming ? Dynamic programming algorithm to derive a
recurrence relation that expresses a solution to an
instance of the problem in terms of solutions to
its smaller instances .
? It does not require any additional structures.
Greedy Algorithm ? Greedy programming techniques are used in
optimization problems.
? Possible greedy strategies to the 0/1 Knapsack
problem:
o First of all choose maximum value from
the remaining items and increases the
value of the knapsack.
o Select the lightest item from the
remaining items, which uses up capacity
as slowly as possible allowing more items
to be stuffed in the knapsack.
o Select the items with as high a value per
weight as possible.
10) The algorithm breaks strings into chunks, where a chunk contains either all alphabetic characters, or all numeric characters. These chunks are then compared against each other. If both chunks contain numbers, a numerical comparison is used. If either chunk contains characters, the ASCII comparison is used.
There is currently a glitch when it comes to periods/decimal points - specifically, periods are treated only as strings, not as decimal points. The solution to this glitch is to recognize a period surrounded by digits as a decimal point, and continue creating a numeric chunck that includes the decimal point. If a letter exists on either side of the period, or if the period is the first or last character in the string, it should be viewed as an actual period and included in an alphabetic chunk. While I have recently figured this out in theory, I have not yet implemented it into the algorithms. To be truly international, the solution shouldn't just consider periods, but should consider whatever decimal separator is used in the current language.
Currently, the algorithm isn't designed to work with negative signs or numbers expressed in scientific notation, like "5*10e-2". In this case, there are 5 chunks: 5, *, 10, e-, and 2.
The latest version of some of the code (particularly the Java version) compares numbers one at a time if those numbers are in chunks of the same size. For example, when comparing abc123 to abc184, 123 and 184 are the same size, so their values are compared digit-by-digit: 1=1, 2<8. This was done to solve the problem of numeric chunks that are too large to fit in range of values allowed by the programming language for a particular datatype: in Java, an int is limited to 2147483647. The problem with this approach is doesn't properly handle numbers that have leading zeros. For example, 0001 is seem as larger than 1 because it's the longer number.