Wednesday, April 20, 2022

Modify the original inventory.c program that we wrote in class by making inventory and num parts local to the main function.

 Modify the original inventory.c program that we wrote in class by making inventory and num parts local to the main function.












Here is the solution given below:

After modifing the original inventory.c program:

#include <stdio.h>
#define NAME_LEN 25
#define MAX_PARTS 100

struct part {
  int number;
  char name[NAME_LEN+1];
  int on_hand;
} inventory[MAX_PARTS];

int num_parts = 0;   /* number of parts currently stored */

int find_part(int number);
void insert(void);
void search(void);
void update(void);
void print(void);
int main(void)
{
  char code;

  for (;;) {
    printf("Enter operation code: ");
    scanf(" %c", &code);
    while (getchar() != '\n')   /* skips to end of line */
      ;
    switch (code) {
      case 'i': insert();
                break;
      case 's': search();
                break;
      case 'u': update();
                break;
      case 'p': print();
                break;
      case 'q': return 0;
      default:  printf("Illegal code\n");
    }
    printf("\n");
  }
}
int find_part(int number)
{
  int i;

  for (i = 0; i < num_parts; i++)
    if (inventory[i].number == number)
      return i;
  return -1;
}
void insert(void)
{
  int part_number;

  if (num_parts == MAX_PARTS) {
    printf("Database is full; can't add more parts.\n");
    return;
  }

  printf("Enter part number: ");
  scanf("%d", &part_number);
  if (find_part(part_number) >= 0) {
    printf("Part already exists.\n");
    return;
  }

  inventory[num_parts].number = part_number;
  printf("Enter part name: ");
  read_line(inventory[num_parts].name, NAME_LEN);
  printf("Enter quantity on hand: ");
  scanf("%d", &inventory[num_parts].on_hand);
  num_parts++;
}
void search(void)
{
  int i, number;

  printf("Enter part number: ");
  scanf("%d", &number);
  i = find_part(number);
  if (i >= 0) {
    printf("Part name: %s\n", inventory[i].name);
    printf("Quantity on hand: %d\n", inventory[i].on_hand);
  } else
    printf("Part not found.\n");
}
void update(void)
{
  int i, number, change;

  printf("Enter part number: ");
  scanf("%d", &number);
  i = find_part(number);
  if (i >= 0) {
    printf("Enter change in quantity on hand: ");
    scanf("%d", &change);
    inventory[i].on_hand += change;
  } else
    printf("Part not found.\n");
}
void print(void)
{
  int i;

  printf("Part Number   Part Name                  "
         "Quantity on Hand\n");
  for (i = 0; i < num_parts; i++)
    printf("%7d       %-25s%11d\n", inventory[i].number,
           inventory[i].name, inventory[i].on_hand);
}

In a system with 100 processors (multiprocessor), each processor reaches a maximum operating speed of 2Gflops. If 2% of the code we want to run in such a system can be serial and 98% parallel, what will be the performance of the system in terms of Gflops?

 In a system with 100 processors (multiprocessor), each processor reaches a maximum operating speed of 2Gflops. If 2% of the code we want to run in such a system can be serial and 98% parallel, what will be the performance of the system in terms of Gflops?







If run-time's 2% belongs to serial execution, then even if you have infinite Gflops you can't surpass 50x speedup. If parallelized codes perfectly scale to 100 processors, then 98% of run-time reduces to 0.98% which makes 2.98% of unoptimized run-time. This means nearly (2/3) of the time, it is serial work, nearly (1/3) parallel work. So, running at 200 Gflops for ~1 unit time and 2 Gflops for ~2 unit time means the average is ~67 Gflops. If just the serial part was run on an overclock of 100% (2% to 1% time reduction), then it would be ~100 Gflops on average (1% time with 1 core, ~1% time with 100 cores, roughly 50 cores on average). So, even a single-core turbo on a 128-core CPU can boost overall performance by 25%-50% for some optimized algorithms. For example, a game scene has 40,000 colliding balls and you build an octree to find collisions faster, using an old 4 core CPU. Building the octree in single thread takes 12 milliseconds and computing collisions in single thread parallizable code takes 24 milliseconds. That's only 3x speedup even with infinite number of cores and perfect scaling. With 4 cores, it gets 6 milliseconds for collision. When added to 12ms of octree building, its 18 milliseconds, or 100% more speed while having only 1/3 of the time on parallelized codes. If the octree building had turbo core with 100% overclock, total time would be 6ms+6ms so it would have half the time on 4 core and half the time on single core, this means 2.5 cores on average or 150% more performance. But, nothing stops you implementing a pipeline and overlap two frames in time line such that a serial and a parallel region works at the same time but for different frames. Then you can double the average performance (perfect scaling, i.e. equal timings for octree building amd collision) or reach max cores performance.

Q2. As new links are created and old ones are removed among an existing set of Web pages, thepages move between different parts of the bow-tie structure. (05)(a) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe largest strongly connected component.(b) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe set IN.(c) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe set OUT.

 Q2. As new links are created and old ones are removed among an existing set of Web pages, thepages move between different parts of the bow-tie structure. (05)(a) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe largest strongly connected component.(b) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe set IN.(c) Name an edge you could add or delete from the graph in Figure 3 so as to increase the size ofthe set OUT.








strongly connection component : It is the subgraph of the given graph where each node can be reachable from every other vertex in the selected subgraph

In set : set of all nodes which have an incoming edge incident upon the node

out group: set of all nodes which have an outgoing edge from the node

first question : you can never increase the size of the strongly connected component with deleting an edge you must always add an edge

the largest strongly connected component in the given graph is the 9,14,15 and we can increase the size by adding another edge 9->13

second question: when we add the edge 11->6 we will increase the inset because there is no in edge on node 6 so it is not present in the in set now once we add the 11->6 edge it will be added to inset and the size will be increased

third question :

when we add the edge 2->7 we will increase the out group because there is no out edge from node 2 so it is not present in the out group now once we add the 2->7 edge it will be added to out group and the size will be increased

Using C++,Given a directed line from point p0(x0, y0) to p1(x1, y1), you can use the following condition to decide whether a point, p2(x2, y2) is on the left of the on the right, or on the same line. > 0 ; p2 is on the left side of the line ( x1 - x0 ) * ( y2 - y0 ) - ( x2- x0 ) * ( y1 - y0 ) = 0 ; p2 is on the same line (a) p2 is on the left of the line (b) p2 is on the right of the line (c) p2 is on the same line Write a program that prompts the user to enter the x-y coordinates for the three points p0, p1, and p2 and displays whether p2 is on the left of the line from p0 to p1, on the right, or on the same line.

 Using C++,Given a directed line from point p0(x0, y0) to p1(x1, y1), you can use the following condition to decide whether a point, p2(x2, y2) is on the left of the on the right, or on the same line.


> 0 ; p2 is on the left side of the line

( x1 - x0 ) * ( y2 - y0 ) - ( x2- x0 ) * ( y1 - y0 ) = 0 ; p2 is on the same line

(a) p2 is on the left of the line



(b) p2 is on the right of the line

(c) p2 is on the same line


Write a program that prompts the user to enter the x-y coordinates for the three points p0, p1, and p2 and displays whether p2 is on the left of the line from p0 to p1, on the right, or on the same line.







import java.util.Scanner;

public class Lab01 {

  

   public static void specifyposition(int x0,int y0,int x1,int y1,int x2,int y2){

     

double val = (x1 - x0)*(y2 - y0) - (x2 - x0)*(y1 - y0);

  

if(val>0)

   System.out.println("p2 is on the left side of the line");

else if (val==0)

   System.out.println("p2 is on the same line");

else

   System.out.println("p2 is on the right side of the line");

   }

   public static void main(String[] args) {

  

   Scanner sc = new Scanner(System.in);

   System.out.println("Enter coordinate for three points: ");

   System.out.println("Enter coordinate for P0: ");

   int x1 = sc.nextInt();

   int y1 = sc.nextInt();

   System.out.println("Enter coordinate for P1: ");

   int x2 = sc.nextInt();

   int y2 = sc.nextInt();

   System.out.println("Enter coordinate for P2: ");

   int x3 = sc.nextInt();

   int y3 = sc.nextInt();

     

   specifyposition(x1,y1,x2,y2,x3,y3);

   }

}

OUTPUT:

Enter coordinate for three points:

Enter coordinate for P0:

2   3

Enter coordinate for P1:

4   5

Enter coordinate for P2:

2   3

P2 is on the same line

You need to compare a student's behavior when locating admission requirements of a university. (i) A complete hierarchical task analysis (HTA) for locating admission requirements of graduate studies at New York University for the English department is required. (ii) A complete HTA for locating admission requirements for graduate studies at Harvard for the English Department is required. Discuss whether the solutions to (i) and (ii) can be modified to emphasize their common features and whether this would clarify the overall task description. P.S: This is Human Computer Interaction Topic, there are no more references to it. For the book you can refer: https://paragnachaliya.in/wp-content/uploads/2017/08/HCI_Alan_Dix.pdf, Chapter 15.

 You need to compare a student's behavior when locating admission requirements of a university.

(i) A complete hierarchical task analysis (HTA) for locating admission requirements of graduate studies at New York University for the English department is required.
(ii) A complete HTA for locating admission requirements for graduate studies at Harvard for the English Department is required.
Discuss whether the solutions to (i) and (ii) can be modified to emphasize their common features and whether this would clarify the overall task description.

P.S: This is Human Computer Interaction Topic, there are no more references to it.
For the book you can refer: https://paragnachaliya.in/wp-content/uploads/2017/08/HCI_Alan_Dix.pdf, Chapter 15.






Ans:One of the standard ways of presenting a HTA is as a tree structure: There may be some other notations you are familiar with where the order of appearance of boxes in the tree indicates ordering (probably left to right). This is not the case for HTA: the only thing that matters is the hierarchy. As well as presenting the hierarchy, it is necessary to describe plans that define the possible ordering of activities. In this case, a suitable plan would be: Plan 0: Do 1, then 2 and 3 in either order, then 4. Although tree structures are visually appealing – well, more appealing than the alternatives, anyway – they can be tedious to draw without a suitable tool. Therefore an alternative text-based notation that relies on indentation is often used. We will use this textual notation to expand the task description for the letter-writing task. 0: Write letter and prepare for posting 1: Prepare for writing 1.1: Get paper 1.2: Get envelope 1.3: Get pen 1.4: Get address book (not explicitly stated, but clearly necessary) 2: Write letter 2.1: Write own address 2.2: Write addressee's address 2.3: Write date and "Dear..." 2.4: Write body text of letter 2.5: Sign off 3: Prepare envelope 3.1: Write name on envelope 3.2: Write address on envelope 4: Put letter in envelope 4.1: Fold letter 4.2: Place letter into envelope 4.3: Seal envelope Again, we need plans to describe how to perform each subtask: Plan 1: Do 1.1, 1.2, 1.3 and 1.4 in any order Plan 2: Do 2.1 then 2.2 then 2.3 then 2.4 then 2.5 Plan 3: Do 3.1 then 3.2 Plan 4: Do 4.1 then 4.2 then 4.3. Task analysis involves generating as general a description as possible. So, for example, we might want to generalise tasks 2.1, 2.2 and 2.3 to a new task: write head of letter. Similarly, we might notice that it is not necessary to have the envelope to hand until the time when it is to be prepare, or the paper to hand until the point where the user starts writing the letter, but we need the pen and address book for both, so we might break down task 1. If we do these things, we get a new structure: 0: Write letter and prepare for posting 1: Get paper 2: Get envelope 3: Prepare for writing 3.1: Get pen 3.2: Get address book 4: Write letter 4.1: Write head of letter 4.1.1: Write own address 4.1.2: Write addressee’s address 4.1.3: Write date and “Dear…” 4.2: Write body text of letter 4.3: Sign off 5: Prepare envelope 6: Put letter in envelope Again, we need plans to describe how to perform each subtask: Plan 0: Do 1, 2, 3, 4 and 5, then 6. 3 must be done before 4 and 5; 1 must be done before 4; 2 must be done before 5. Plan 3: Do 3.1 and 3.2 in either order Plan 4: Do 4.1 then 4.2 then 4.3. Plan 4.1: Do 4.1.1 then 4.1.2 then 4.1.3 Plan 5: Do 5.1 then 5.2 Plan 6: Do 6.1 then 6.2 then 6.3. We see that now different parts of the task analysis are presented at different levels of detail. This is often thought of as a Bad Thing, but in this case it allows us to describe the optionally and alternative orderings within the task more clearly. As with most aspects of design, there is no perfect solution just solutions that are better or worse for particular purposes.

Write (and test) a C program to edge color a provided bipartite graph. The input to your program will be: a. , , and m, the numbers of left column vertices, right column vertices, and edges. and . b. m lines, each giving an edge: left column vertex, right column vertex. Left column vertices are numbered 0 . . . - 1. Right column vertices are numbered 0 . . . - 1. Duplicate edges will not occur. The output from your program will be: a. A trace of the processing. Each edge will be processed by either 1) using a color that is “free” at both incident vertices, or 2) using an alternating (a, b) path. For (1), simply indicate the free color that is used for the edge. For (2), indicate the colors (e.g. numbers) for a and b along with the vertices on the path. b. A list of the edges (input order) and the final color for each edge. 2. Submit your C code on Canvas before 3:45 p.m. on April 11. Your code must compile and execute on omega.uta.edu. Getting Started: 1. Bipartite edge coloring is discussed in Notes 11. Do not use the approach for general graphs, since the number of colors you may use is bounded by the degree (D) of the bipartite graph (not D + 1). 2. Assigned colors must be in the range 0 . . . D - 1. You will need to preprocess the edges to determine D. 3. Do not use backtracking instead of the alternating (a, b) path technique. 4. It is useful to have several tables. Rather than having a table of free colors for each vertex, it is useful to have a table that indicates for a given vertex and color the incident edge (if any) with that color.

 Write (and test) a C program to edge color a provided bipartite graph.

The input to your program will be:
a. , , and m, the numbers of left column vertices, right column vertices, and edges. and .
b. m lines, each giving an edge: left column vertex, right column vertex. Left column vertices are numbered 0 . . . - 1. Right column vertices are numbered 0 . . . - 1. Duplicate edges will not occur.
The output from your program will be:
a. A trace of the processing. Each edge will be processed by either 1) using a color that is “free” at both incident vertices, or 2) using an alternating (ab) path. For (1), simply indicate the free color that is used for the edge. For (2), indicate the colors (e.g. numbers) for a and b along with the vertices on the path.
b. A list of the edges (input order) and the final color for each edge.
2. Submit your C code on Canvas before 3:45 p.m. on April 11. Your code must compile and execute on omega.uta.edu.
Getting Started:
1. Bipartite edge coloring is discussed in Notes 11. Do not use the approach for general graphs, since the number of colors you may use is bounded by the degree (D) of the bipartite graph (not D + 1).
2. Assigned colors must be in the range 0 . . . D - 1. You will need to preprocess the edges to determine D.
3. Do not use backtracking instead of the alternating (ab) path technique.
4. It is useful to have several tables. Rather than having a table of free colors for each vertex, it is useful to have a table that indicates for a given vertex and color the incident edge (if any) with that color.









#include<stdio.h>
#include<stdlib.h>
//return 1 if two colors are sufficient. O not.
int canColorTwo(int vertices, int **graph){
int i,j;
//res will stores the i th vertex assigned color.
int *res = (int *)malloc(sizeof(int)*vertices);
//color will stres the i th color avilable or not.available means
0.otherwise 1.
int *color = (int *)malloc(sizeof(int)*vertices);
for(i 0;i<vertices;i++){
res[i] = -1;
color[i] = 0;

}
res[0] = 0;
//for each vertex in graph.
for(i =1;i<vertices; i++){
//making the colour to neighbour vertices as unavilable.

for(j =0;j<vertices;j++) {

if(graph[i][j] == 1&& res[j] ! = -1) {

color[res[j]] = 1;

}

}

//finding color.

for(j =0;j<vertices;j++) {

if(color[j] == 0 ) break;

}

// assigning color.

res[i] = j;

// reseting the color for the next vertoces.

for(j =0;j<vertices;j++) {

if(graph[i][j] == 1 && res[j]! = -1) color[res[j]] = 0;

}

}

//finding the max color are required to color the graph.

int max = res[0];

for(i = 0;i< vertices;i++) {

if(max< res[i]) max = res[i];

}

//return

if(max<2) return 1;

return 0;

}

int main() {

//reading data.

int vertices,edges,i,j;

scanf("%d",&vertices);

scanf("%d",&edges);

//creating adjecency graph matrix.

int **graph = (int **)malloc(vertices*sizeof(int));

for(i =0;i<vertices;i++) {

graph[i] = (int *)malloc(sizeof(int)&vertices);

}

//making all cells as -1. means no (vi,vi +1) connection.

for(i =0;i< vertices;i++)

for(j =0;j<vertices;j++)

graph[i][j] = -1;

//adding edjes in the graph.

for(i =0;i<edges;i++) {

int u,v;

scanf("%d%d",&u,&v);

graph[u][v] = 1;

graph[v][u] = 1;

}

//calling canColorTwo() if possible displaying two-color.otherwise no two-color.

if(canColorTwo(vertices,graph) == 1) {

printf("two-color");

}

else {

printf("no two-color");

}

return 0;

}


Write (and test) a C program to edge color a provided bipartite graph. The input to your program will be: a. , , and m, the numbers of left column vertices, right column vertices, and edges. and . b. m lines, each giving an edge: left column vertex, right column vertex. Left column vertices are numbered 0 . . . - 1. Right column vertices are numbered 0 . . . - 1. Duplicate edges will not occur. The output from your program will be: a. A trace of the processing. Each edge will be processed by either 1) using a color that is “free” at both incident vertices, or 2) using an alternating (a, b) path. For (1), simply indicate the free color that is used for the edge. For (2), indicate the colors (e.g. numbers) for a and b along with the vertices on the path. b. A list of the edges (input order) and the final color for each edge. 2. Submit your C code on Canvas before 3:45 p.m. on April 11. Your code must compile and execute on omega.uta.edu. Getting Started: 1. Bipartite edge coloring is discussed in Notes 11. Do not use the approach for general graphs, since the number of colors you may use is bounded by the degree (D) of the bipartite graph (not D + 1). 2. Assigned colors must be in the range 0 . . . D - 1. You will need to preprocess the edges to determine D. 3. Do not use backtracking instead of the alternating (a, b) path technique. 4. It is useful to have several tables. Rather than having a table of free colors for each vertex, it is useful to have a table that indicates for a given vertex and color the incident edge (if any) with that color.

 Write (and test) a C program to edge color a provided bipartite graph.

The input to your program will be:
a. , , and m, the numbers of left column vertices, right column vertices, and edges. and .
b. m lines, each giving an edge: left column vertex, right column vertex. Left column vertices are numbered 0 . . . - 1. Right column vertices are numbered 0 . . . - 1. Duplicate edges will not occur.
The output from your program will be:
a. A trace of the processing. Each edge will be processed by either 1) using a color that is “free” at both incident vertices, or 2) using an alternating (ab) path. For (1), simply indicate the free color that is used for the edge. For (2), indicate the colors (e.g. numbers) for a and b along with the vertices on the path.
b. A list of the edges (input order) and the final color for each edge.
2. Submit your C code on Canvas before 3:45 p.m. on April 11. Your code must compile and execute on omega.uta.edu.
Getting Started:
1. Bipartite edge coloring is discussed in Notes 11. Do not use the approach for general graphs, since the number of colors you may use is bounded by the degree (D) of the bipartite graph (not D + 1).
2. Assigned colors must be in the range 0 . . . D - 1. You will need to preprocess the edges to determine D.
3. Do not use backtracking instead of the alternating (ab) path technique.
4. It is useful to have several tables. Rather than having a table of free colors for each vertex, it is useful to have a table that indicates for a given vertex and color the incident edge (if any) with that color.





images

#include<stdio.h> #include<stdlib.h> //return 1 if two colors are sufficient. O not. int canColorTwo(int vertices, int **graph){ int inj; l/res will stores the i th vertex assigned color. int *res = (int *)malloc(sizeof(int)*vertices); //color will stres the i th color avilable or not.available means 0.otherwise 1. int *color = (int *)malloc(sizeof(int)*vertices); for(i = 0;i<vertices;i++){ res[i] = -1; color[i] = 0; } res[0] = 0; //for each vertex in graph. for(i = 1;i<vertices;i++){ //making the colour to neighbour vertices as unavilable. for(j = 0;j<vertices;j++){ if(graph[i][j] == 1 && res[j] != -1){ color[res[j]] = 1; } } //finding color. for(j = 0;j<vertices;j++){ if(color[j] == 0) break; } //assigning color. res[i] = 1; //reseting the color for the next vertices. for(j = 0;j<vertices;j++){ if(graph[i][j] == 1 && res[j] != -1) color[res[i]] = 0; } } //finding the max color are required to color the graph. int max = res[0]; for(i = 0;i<vertices;i++){ I=

if(max<reslil) max = res[i]; } //return if(max<2) return 1; return 0; } int main(){ //reading data. int vertices,edges,ij; scanf("%d",&vertices); scanf("%d",&edges); // creating adjecency graph matrix. int **graph = (int **)malloc(vertices*sizeof(int)); for(i = 0;i<vertices;i++){ graph[i] = (int *)malloc(sizeof(int)&vertices); } //making all cells as -1.means no (vi,vi+1) connection. for(i = 0;i<vertices;i++) for(j = 0;j<vertices;j++) graph[i][j] = -1; //adding edjes in the graph. for(i = 0;i<edges;i++){ - int u,v; scanf("%d%d",&u,&v); graph[u][v] = 1; graph[v][u] = 1; } // calling canColor Two() if posiible displaying two-color.otherwise no two-color. if(canColorTwo(vertices,graph) == 1){ printf("two-color"); } else{ printf("no two-color"); } return 0; }

Attachments: