Combined Assignment 8 and 9 Solution

$30.00

Description

  • Instructions

For this assignment:

Answer the questions individually. Group e ort is not allowed. Reading: http://c-faq.com, K&R C, chapter 1-6.

You are allowed to use resources from the internet as long as you refer them in your repository README le.

You will note that none of the les in the repository have been populated except the Make le (and even that only speci es the targets you must implement and includes our testing Make le into your Make le). As we are in the last half of the semester, you should be able to do these tasks with much less guidance.

  • Questions

2.1 sort nodes

(80 points) You are given structure struct Node below, where next points to the next node in the list (or NULL if it is the last node in the list), and prev presents to the previous node in the list (or NULL if it is the rst node).(see Figure 1):

1

s t r u c t

Node

f

s t r u c t

Node

next ;

3

s t r u c t

Node

prev ;

g;

5

t y p e d e f

s t r u c t Node Node ;

Implement a function Node *sort nodes(Node *head) that returns head of list such that: &node1 > &n2 > &n3 > ::: > &last node You will submit sorter.c and node.h. sorter.c will contain the sort nodes function. node.h will contain the de nition of the Node structure and the prototype for the sort nodes function.

Figure 1: Lists before and after sorting. Arrows going left to right indicate \next” pointers, and arrows going right to left indicate the \prev” pointers.

Input

Node* head

struct _Node N1

struct _Node N2

struct _Node N3

struct _Node N4

0x1300

0x1000

0x3000

0x2000

next

next

next

next

NULL

NULL

prev

prev

prev

prev

Output

Node* head

struct _Node N3

struct _Node N4

struct _Node N1

struct _Node N2

0x3000

0x2000

0x1300

0x1000

next

next

next

next

NULL

NULL

prev

prev

prev

prev

2.1.1 Hints and Notes

You should mix nodes from stack (local variables), heap (dynamic variables) and global variables to generate a list comprising of nodes of varying addresses.

Although you are free to use any sorting algorithm, it might be easier to use selection sort. In simple words, selection sort is where you iterate through the list to select the largest element and move it to the beginning of the list. (https://en.wikipedia. org/wiki/Selection_sort).

You are guaranteed that your function will be tested against lists that contain at least 3 elements. So, you are not required to handle lists of smaller size.

You are not allowed to make copies of the nodes. You are required to sort them by altering the next and prev pointers.

2.2 Estimator

(60 points) You are to write a program to estimate the throughput of nop instructions. That is, you are to nd the number of nop instructions that the processor can execute in 1 second. Your program must be called estimator ands its implementation is in estima-tor.c. It should print a single number in scienti c notation indicating the number of nop instructions the processor can execute in 1 second with a trailing newline and nothing else. This number of instructions should re ect the average of at least 5 trials.

2.2.1 Hints and Notes

Using the timer code given in the Labs, run an assembly function comprising of 100 nop instruction a large number of times (e.g., (unsigned int) 0xffffffff), and run another assembly function that contains 0 nop instructions (only a ret instruction) the same num-ber of times. In both cases, measure the time consumed over at least 5 trials. Compute the average number of nop instructions the processor executes per second. You can expect at least 2 x 109 nop’s per second.

2.3 Toggle

(60 points) You are to implement the following function in 64 bit assembly in le toggle.S, with the function prototype in toggle.h.

unsigned long toggle_bit(unsigned long num, unsigned long bit_num);

The function accepts an unsigned long num and toggles (A 0 bit changes to 1 and a 1 bit changes to 0) the bit at bit num position (0 bit num 64, where 0 is the least signi cant bit and 63 is the most signi cant bit).

  • Submission

Submit the 7-digit SHA hash as a student comment to a MyCourses submission.


error: Content is protected !!