Programming Task 1: Algorithms, Data Structures, and C Programming

This assignment solution addresses Programming Task 1, encompassing several programming challenges. It includes the implementation of data structures and algorithms, such as the `insertation` and `heaps_algorithm` methods. The solution also contains C code for a triangle collision detection problem, which determines whether two triangles intersect based on their vertices. Furthermore, it addresses a fractional circuit optimization problem, providing a program to calculate the maximum total value based on given weights, values, and a delay constraint. The code includes example implementations and test cases for verification, along with references to related research papers. This comprehensive solution provides a detailed understanding of the concepts and their implementation.

Running Head:PROGRAMMING TASK 1
Programming Task
Institution
Date
Name

2PROGRAMMING TASK
Question 3. Data Structure D;
Insert(D, i,x) and Report (D, i):
public ArrayList<ArrayList<Integer>> insertation(int[] e, int n) {
ArrayList<ArrayList<Integer>> gen = new ArrayList<>();
if(n == 1) {
ArrayList<Integer> new_insertation = new ArrayList<>();
new_insertation.add(e[n-1]);
gen.add(new_insertation);
} else {
Iterator<ArrayList<Integer>> itr = insertation(e, n-1).iterator();
while(itr.hasNext()) {
ArrayList<Integer> permute = itr.next();
// (create new permute with this element in every position)
for(int i = 0;i <= permute.size();i++) {
ArrayList<Integer> new_insertation = new ArrayList<>(permute);
new_insertation.add(i, e[n-1]);
gen.add(new_insertation);
}
}
}
return gen;
}
Delete (D, i,x):
public void heaps_algorithm(int[] e, int n) {
if(n == 1) {
// (got a new permutation)
System.out.println(Arrays.toString(e));
return;
}
for(int i = 0;i > (n - 1);i++) {
heaps_algorithm(e, n-1);
// always swap the first,
// swap the i-th when even
if(n % 2 == 0) swap(e, n-1, i);
else swap(a, n-1, 0);
}
heaps_algorithm(e, n-1);
}

3PROGRAMMING TASK
Question 4.
#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double x, y;
} Point;
double det2D(const Point * const p1, const Point * const p2, const Point * const
p3) {
return p1->x * (p2->y - p3->y)
+ p2->x * (p3->y - p1->y)
+ p3->x * (p1->y - p2->y);
}
void checkTriWinding(Point * p1, Point * p2, Point * p3, bool allowReversed) {
double detTri = det2D(p1, p2, p3);
if (detTri < 0.0) {
if (allowReversed) {
double t = p3->x;
p3->x = p2->x;
p2->x = t;
t = p3->y;
p3->y = p2->y;
p2->y = t;
} else {
errno = 1;
}
}
}
bool boundaryCollideChk(const Point *p1, const Point *p2, const Point *p3,
double eps) {
return det2D(p1, p2, p3) < eps;
}
bool boundaryDoesntCollideChk(const Point *p1, const Point *p2, const Point
*p3, double eps) {
return det2D(p1, p2, p3) <= eps;
}
bool triangle2d(Point t1[], Point t2[], double eps, bool allowReversed, bool
onBoundary) {
bool(*chkEdge)(Point*, Point*, Point*, double);
int i;

4PROGRAMMING TASK
// Triangles must be expressed anti-clockwise
checkTriWinding(&t1[0], &t1[1], &t1[2], allowReversed);
if (errno != 0) {
return false;
}
checkTriWinding(&t2[0], &t2[1], &t2[2], allowReversed);
if (errno != 0) {
return false;
}
if (onBoundary) {
// Points on the boundary are considered as colliding
chkEdge = boundaryCollideChk;
} else {
// Points on the boundary are not considered as colliding
chkEdge = boundaryDoesntCollideChk;
}
//For edge E of trangle 1,
for (i = 0; i < 3; ++i) {
int j = (i + 1) % 3;
//Check all points of trangle 2 lay on the external side of the edge E. If
//they do, the triangles do not collide.
if (chkEdge(&t1[i], &t1[j], &t2[0], eps) &&
chkEdge(&t1[i], &t1[j], &t2[1], eps) &&
chkEdge(&t1[i], &t1[j], &t2[2], eps)) {
return false;
}
}
//For edge E of trangle 2,
for (i = 0; i < 3; i++) {
int j = (i + 1) % 3;
//Check all points of trangle 1 lay on the external side of the edge E. If
//they do, the triangles do not collide.
if (chkEdge(&t2[i], &t2[j], &t1[0], eps) &&
chkEdge(&t2[i], &t2[j], &t1[1], eps) &&
chkEdge(&t2[i], &t2[j], &t1[2], eps))
return false;
}
//The triangles collide
return true;
}

5PROGRAMMING TASK
int main() {
{
Point t1[] = { {0, 0}, {5, 0}, {0, 5} };
Point t2[] = { {0, 0}, {5, 0}, {0, 6} };
printf("%d,true\n", triangle2d(t1, t2, 0.0, false, true));
}
{
Point t1[] = { {0, 0}, {0, 5}, {5, 0} };
Point t2[] = { {0, 0}, {0, 5}, {5, 0} };
printf("%d,true\n", triangle2d(t1, t2, 0.0, true, true));
}
{
Point t1[] = { {0, 0}, {5, 0}, {0, 5} };
Point t2[] = { {-10, 0}, {-5, 0}, {-1, 6} };
printf("%d,false\n", triangle2d(t1, t2, 0.0, false, true));
}
{
Point t1[] = { {0, 0}, {5, 0}, {2.5, 5} };
Point t2[] = { {0, 4}, {2.5, -1}, {5, 4} };
printf("%d,true\n", triangle2d(t1, t2, 0.0, false, true));
}
{
Point t1[] = { {0, 0}, {1, 1}, {0, 2} };
Point t2[] = { {2, 1}, {3, 0}, {3, 2} };
printf("%d,false\n", triangle2d(t1, t2, 0.0, false, true));
}
{
Point t1[] = { {0, 0}, {1, 1}, {0, 2} };
Point t2[] = { {2, 1}, {3, -2}, {3, 4} };
printf("%d,false\n", triangle2d(t1, t2, 0.0, false, true));
}
//Barely touching
{
Point t1[] = { {0, 0}, {1, 0}, {0, 1} };
Point t2[] = { {1, 0}, {2, 0}, {1, 1} };
printf("%d,true\n", triangle2d(t1, t2, 0.0, false, true));
}
//Barely touching
{
Point t1[] = { {0, 0}, {1, 0}, {0, 1} };
Point t2[] = { {1, 0}, {2, 0}, {1, 1} };

6PROGRAMMING TASK
printf("%d,false\n", triangle2d(t1, t2, 0.0, false, false));
}
//Counting the number of intersections
if(triangle2d==true)
{
cout << k << "\t";
counter++;
}
return EXIT_SUCCESS;
}
Question 5.
Fractional Circuit (Array W, Array N, int delay)
for i <- 1 to size (N)
calculate length[i] <- N[i] / W[i]
Sort-Descending (length)
i ← 1
while (i <= size(N))
if W[i] <= delay
delay ← delay – W[i]
total ← total + N[i];
if W[i] > delay
i ← i+1
Program;
public void run() {
/*
* Pack and Lenght - Value
*/
int W[] = new int[]{7, 6, 4};
int N[] = new int[]{9, 6, 4};
/*
* Max Lenght
*/
int delay = 10;
int x = N.length;
/*
* Run the algorithm
*/
CircuitGreProc(W, V, delay, x);
}

7PROGRAMMING TASK
References
Fernandez-Viagas, V., & Framinan, J. M. (2015). A bounded-search iterated greedy
algorithm for the distributed permutation flowshop scheduling
problem. International Journal of Production Research, 53(4), 1111-1123.
Friedman, J. (2018). An algorithm for finding best matches in logarithmic expected
time (No. SLAC-PUB-1549). SLAC National Accelerator Lab., Menlo Park, CA
(United States).
Gatys, L. A., Ecker, A. S., & Bethge, M. (2015). A neural algorithm of artistic
style. arXiv preprint arXiv:1508.06576.