Create the illusion that each user has a dedicated machine

Assignment Help Computer Engineering

Reference no: EM131216090

Aims:

1. To ensure you understand the material discussed in lectures.

2. To give you practice in following the various algorithms discussed in the lectures.

Fill in the form fields as appropriate, save and submit via Blackboard.

The first ten questions are multiple choice questions. In each case there is only one correct answer for which 1 mark will be awarded. Incorrect or missing answers will score 0.

1. Which of the following tracks the progress of a program during execution?
A) process management
B) memory management
C) multiprogramming
D) timesharing
E) CPU scheduling

2. Which of the following is a technique for keeping more than one process in memory at the same time?
A) process management
B) memory management
C) multiprogramming
D) timesharing
E) CPU scheduling

3. Which of the following shares CPU time among multiple processes to create the illusion that each user has a dedicated machine?
A) process management
B) memory management
C) multiprogramming
D) timesharing
E) CPU scheduling

4. Which of the following describes a memory management technique in which a program is divided into fixed sized sections and stored into areas of memory called frames?
A) single contiguous
B) logical address
C) physical address
D) round robin
E) paged

5. Which of the following describes the act of bringing in a page from secondary memory, which may cause another to be written back to secondary memory?
A) swapping
B) context switch
C) demand paging
D) thrashing
E) virtual memory

6. Which of the following describes the situation in which memory appears to be unlimited because the program size is not restricted?
A) swapping
B) context switch
C) demand paging
D) thrashing
E) virtual memory

7. To which state does the currently executing process return when it is interrupted by the operating system?
A) ready
B) new
C) blocked
D) suspended
E) running

8. In which state does a process reside if it is not currently resident in main memory?
A) ready
B) new
C) blocked
D) suspended
E) running

9. In which state does a process reside if it does not have a needed resource, such as a page from secondary memory?
A) ready
B) new
C) blocked
D) suspended
E) running

10. To which state does a process move when the CPU scheduling algorithm determines it may next use the CPU?
A) ready
B) new
C) blocked
D) suspended
E) running

11. Consider the following Binary Search Algorithm

upper = length - 1;
lower = 1;
while (upper >= lower)
{ mid_pt = (upper + lower) / 2;
if(data[mid_pt] < target) ; comparison A
{ lower = mid_pt + 1; }
elseif (data[mid_pt] == target) ; comparison B
{ return mid_pt; }
else { upper = mid_pt - 1;}
}
//target not found

Give the values for lower, upper and mid-pt for each iteration of the while loop and state how many times will the two comparisons A and B be executed using this algorithm to find the value 77 in the following array? You may not need to complete all the rows.

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]
14	27	29	38	42	55	57	61	64	69	77	79	84

Comparison A executed times;Comparison B executed times;

12. A Bubble Sort algorithm as discussed in lectures is given below

index1 = 1;
repeat exchange = false;
{ for index2 ← length- 1 downto index1
{ if data[index2] < data[index2-1]
{ //exchange
exchange = true;
tmp = data[index2];
data[index2] = data[index2-1];
data[index2-1] = tmp;
}
}
index1 = index1 + 1;
} until (not exchange)

Apply this algorithm to the following data. Give the contents of the array after each pass (repeat loop) is completed. For each pass how many exchanges are made?

Note it may not be necessary to use all 7 passes.

Original Data 14 27 12 56 63 72 8 10

After Pass 1

Exchanges

After Pass 2

Exchanges

After Pass 3

Exchanges

After Pass 4

Exchanges

After Pass 5

Exchanges

After Pass 6

Exchanges

After Pass 7

Exchanges

How many comparisons will be made in total?

13. Consider the following quicksort algorithm

Quicksort(first, last)
{IF (first < last) // There is more than one item
       splitVal = data[first];
       splitPoint = Split(splitVal);
       left= first + 1;
       right= last;
       WHILE (left <= right)
          {Increment left until data[left] > splitVal OR left > right;
           Decrement right until data[right] < splitVal OR left > right;
           IF(left < right)
           Swap data[left] and data[right]
           }
           splitPoint= right;
           Swap data[first] and data[splitPoint];
           Quicksort(first, splitPoint - 1);
           Quicksort(splitPoint + 1, last)
}

Each recursive call to the Quicksort function acts on a portion of the array to be sorted. Illustrate how the algorithm works on the same data as in the previous questions by completing the trace below. For each call of Quicksort give the index values for first and last as well as the value (splitVal) used as a pivot value. Also show the state of the array being sorted after the evaluation of all the Quicksort functions applied to the array.

You may not need to complete all the tables below.

Original Data

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
14	27	12	56	63	72	8	10

First	Last	splitVal
0	7	14

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]

First	Last	splitVal		First	Last	splitVal

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

First

Last

splitVal

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]

14. Complete the following table. Where appropriate you may use scientific notation (eg 1.5E+6)Give values to 6 significant figures.

n	log₂n	log₁₀n	n²	2ⁿ	nlog₂n
1
5
10
50
100
500
1000

15. Complete the following table stating the start and end times for each process using the first-come, first-served algorithm.

Process	P1	P2	P3	P4	P5
Service time	40	70	100	20	80
Arrival Time	0	20	40	60	80
Start Time
End Time

16. Complete the following table stating the start and end times for each process using the shortest-job-next algorithm.

Process	P1	P2	P3	P4	P5
Service time	40	70	100	20	80
Arrival Time	0	20	40	60	80
Start Time
End Time

17. Complete the following table stating the start, pause, restart and end times for each process (including any times when a process is swapped out) using the round robin algorithm and a time slice of 30. You may not need to complete all entries.

Process	P1	P2	P3	P4	P5
Service time	40	70	100	20	80
Arrival Time	0	20	40	60	80
Start Time
Pause
Restart
Pause
Restart
Pause
Restart
End Time

Reference no: EM131216090

Questions Cloud

What is the process time of the order picker : Wally is not satisfied with the number you give in (a); he wants the process capacity to become larger. There is a worker recently hired. Who do you want the new worker to help? Order taker, picker, or packer? Why?

Does it matter what gender an artist is : There were very few female Impressionist artists. - Does it matter what gender an artist is?- Does being male or female affect the subject an artist chooses or the ways in which that subject is portrayed?

Compute what is the power dissipated by the resistor : What is the power dissipated by the resistor? What is the voltage v0 provided by the 1.5A current source? Which of Kirchhoff's Laws do you use to find this? What is the current i1? Which of Kirchhoff's Laws do you use to find this?

What is the combined effect of curvature : What is the combined effect of curvature and refraction for a 300 foot long level shot - How much (and in what way) should the preliminary elevation of the seventh turning point be adjusted (± 0.01')?

Create the illusion that each user has a dedicated machine : CS-155 Concepts of Computer Science - Which of the following tracks the progress of a program during execution and create the illusion that each user has a dedicated machine?

Taxpayer works at corporation nearing the end of fiscal year : A taxpayer works at a corporation nearing the end of its fiscal year. The company has had a very successful (profitable) year and has decided to award the employee a cash bonus of 20% of annual salary (a bonus of $30,000). Assuming she can earn 5% af..

Difference between an analog and digital signal : When is the spectrum of a periodic analog signal reproduced correctly via digital signal processing by means of FFT?

Concepts of quality improvement in the health care industry : Explain basic concepts of quality improvement in the health care industry. - Explain the concepts of risk management in the health care industry.

Disposal cost at end of life and energy savings : An air handling system must be purchased for your company. The best estimates for the first costs, yearly costs (O&M) and yearly benefits (Energy savings) are given below. However, uncertainty exists about the disposal cost and energy savings. Dispos..

User Account

All Pages