Author: vkunge

...talking about ICT

2021 U2 Q2

vkungeLeave a comment

Part a) i)

In a linear search, each element of the array is traversed by using iteration.  Each element in the traversal is compared against a search key. If the key is found, the location of the array index is returned.  If the entire array is traversed without finding the key, dummy value is returned (e.g. -1)

(see this note [1])

Part b) ii)

In a binary search, an ordered list is searched for a key starting with the item at the middle of the list. If the item is not found at the location ,  a determination is made on which half of the list may contain the key, either the upper or lower half. This method is applied to search the midpoint of the half of the list which may contain the key.  This repeats until the key is found, or until the search space is reduced to a single location and  the list can no longer be divided into halves. If the key is found, the location of the element is returned, otherwise a dummy value is returned (e.g -1)

(see this note [2])

Part b)

    //Code to store values in array
    int arr[] =  {3,12,9,10,5,4}; 
    int arrayLength = sizeof(arr)/sizeof(int);
    
     //selection sort
    for ( int i = 0; i<arrayLength; ++i)
    {
        int smallest = i;
        for (int k = i  ; k<arrayLength; ++k)
        {
           if  (arr[k]<arr[smallest])
                smallest=k;
        }
        //if the first element was not the smallest,
        //swap the first item with the smallest
        if (smallest!=i)
        {
            int temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest]=temp;
        }
    }

Part c)

Search midpoint of [0-9], location 4, it is not the key, 16<27 so the left portion is searched

Search midpoint of [0-3], location 1, it is not the key, 16>9 so the right portion is searched

Search midpoint of [2-3], location 2, it is the key, thus the search function returns 2.

Further Explanation1

  1. First, the algorithm calculates the midpoint of the entire array’s index range. The array has 10 elements, indexed from 0 to 9. The midpoint is calculated as (low + high) / 2. Initially, low is 0 and high is 9, so the midpoint is (0 + 9) / 2 which equals 4.5. Since we are working with integer indices, we take the floor of this value to choose the lower index, resulting in 4. The value at index 4 is 27, which is greater than 16.
  2. Because 16 is less than 27, the algorithm ignores the right half of the array and recalculates the midpoint for the left subarray spanning from index 0 to 3. Now, low is 0 and high is 3, so the new midpoint is (0 + 3) / 2 which equals 1.5. Taking the floor of this value, we again choose the lower index, which is 1. The value at index 1 is 9, which is less than 16.
  3. The algorithm then focuses on the right subarray of the previous range, which is from index 2 to 3. The midpoint here is (2 + 3) / 2 which equals 2.5. After taking the floor, the midpoint is index 2. The value at index 2 is 16, which matches the key we are searching for.

The search concludes with the algorithm returning index 2 as the position where the key 16 is located in the array.

Footnotes

[1] https://islandclass.org/2020/09/01/linear-search/

[2] https://islandclass.org/2020/11/12/binary-search-implementation/

  1. TA Note ↩︎

2019 U2 Q5

vkungeLeave a comment

Part a

Non Pre-emptive scheduling runs processes on a first come first serve basis,  pre-emptive scheduling determines the length of time  the processes will take to be executed , and then executes the shortest process first, followed by the next shortest and so on. Pre-emptive scheduling can also be accomplished by other algorithms , e.g round robin.

(See this note1)

Part b(i)

The process’s instruction from it’s local program counter is placed on the CPU and executed one after the other until an interrupt is generated.

Part b(ii)

The process scheduler prepares to move the process of the CPU. The process’ updated program counter and state information is saved to its process control block, the process is now in the “ready” queue.

Part b(iii)

The process is interrupted by an I/O or event interrupt. The process’ updated program counter and state information is saved to its process control block, it is placed in the “waiting” queue  to wait for an I/0 or event completion.

Part b(iii)

The process is moved to the ready queue from the  waiting queue.  If the process was waiting on an I/O operation, it’s PCB and local memory would be  updated before it was moved to the ready queue.

Part c

The interrupt is a scheduling one, P5’s program counter and other information is saved to its PCB.  P5 is put into  a “ready” state since it was not blocked by IO or another event.

P2’s instruction from its Program counter is put on the cpu for execution, P2’s  PCB is updated to “running” . P2 will run to completion assuming no error interrupts are generated. When P2 is complete, it’s state is set to terminated. Assuming that there are no other high priority tasks to be run than P5, P5 will be go from ready to running, and it’s instructions are executed from it’s program counter until it terminates and enters a terminated state.

Part d

R0 is locked to P0, it cannot be accessed.

P1 wants to access R1, because it is locked to P0.

For P1 to access R0, P0 must run to completion and terminate.

However, P0 is waiting on P1 to complete in order to access R1  (Which is locked to P1 in the diagram)

Thus both processes cannot run to completion since the resources they need are locked  either one.  This produces a deadlock.

Part e

Advantages:

Advanced operations can be performed at the command line.

For an advanced user, It is faster than using a gui

It is uses comparatively less system resources.

Disadvantages:

It is difficult to learn and use for an inexperienced user.

Unable to perform multitasking.

Part f

Encrypt the files.

Password protect the files.

Employ the use of access permissions to the sender and receiver only to be able to access the file.

Send over a reliable medium which can verify and ensure that the file was sent I.e the use of an application layer protocol running over a connection oriented protocol, e.g using an email client which implements SMTP which in turn uses the IP TCP. 

Table of Contents

  1. Part a
  2. Part b(i)
  3. Part b(ii)
  4. Part b(iii)
  5. Part b(iii)
  6. Part c
  7. Part d
  8. Part e
  9. Part f
  10. Table of Contents
  11. Footnotes

Footnotes

  1. https://islandclass.wordpress.com/2021/05/12/scheduling-algorithms/ ↩︎

© 2023  Vedesh Kungebeharry. All rights reserved. 

2019 U2 Q6

vkungeLeave a comment
  1. Part a(i)
    1. Feedback to students from class notes
  2. Part a(ii)
    1. Feedback to students from class notes
  3. Part a(iii)
  4. Part b
  5. Part c
  6. Part d
  7. Footnotes

Part a(i)

Handles Host to host communication on the subnet (subnetwork to subnetwork, thus implementing a wide area network) level occurs here using packets. Packets are routed from host to host across the subnets or within a single subnet. Separate subnets may be implemented with differing protocols, the network layer will overcome these challenges by modifying packets to conform to the various protocols.

Feedback to students from class notes

  • Analogy: Sending a large quantity of flour from one country to the next with varying units (kg vs llbs) and customs rules

  • Logical addressing occurs at this protocol (ip addresses , IP protocol suite)

Part a(ii)

Here is  where raw data is transferred over the physical mediums which make up the network, protocol example : RS-232-C

Feedback to students from class notes

(See this video1)

Part a(iii)

The application layer is where applications communicate with each other through high level protocols e.g HTTP, FTP.  The application itself is only responsible for adhering to those protocols and not responsible for routing, sequencing etc that is required to send information through the lower layers which make up the network infrastructure.

Part b

Difficult to guess

Contains a combination of Uppercase and lowercase letters

Contains Special Characters

Is sufficiently long

Can be remembered easily by its creator even though it is difficult to guess.

(See this note2)

Part c

Any of the 3 responses below:

  • By using a network repeater to rebroadcast the signal.
  • By using a network boosters to amplify wireless signals
  • By upgrading the medium to one with less signal attenuation, e.g coaxial to fibre optic.

Part d

Router with access to internet, all other devices connected to the router similar to the diagram below

Footnotes

  1. https://www.youtube.com/watch?v=eo9dbnrpspM ↩︎
  2. https://islandclass.org/2021/01/20/creating-and-managing-passwords-online/ ↩︎

© 2023  Vedesh Kungebeharry. All rights reserved. 

2009 U1 Q1

vkungeLeave a comment
  1. Part a)
  2. Part b)
    1. Explanation
  3. Part c)
  4. Part d) i)
    1. Explanation/Working:
  5. Part d) ii)
  6. Part d) iii)
  7. Part d) iv)
  8. Links to Notes
    1. Attributions to media used in this post
  9. Footnotes

Part a)

AND Gate:

AND ANSI Labelled 
  A | B | A AND B
  ---------------
  0 | 0 |    0
  0 | 1 |    0
  1 | 0 |    0
  1 | 1 |    1

Or Gate:

OR ANSI Labelled 
  A | B | A OR B
  ---------------
  0 | 0 |    0
  0 | 1 |    1
  1 | 0 |    1
  1 | 1 |    1

Not Gate:

NOT ANSI Labelled 
  A | NOT A
  ---------
  0 |   1
  1 |   0

See this note1

Part b)

Suggested response:

XOR truth table:

ABA XOR B
000
011
101
110

Output is 1 in XOR for (NOT A AND B) OR (A AND NOT B)

Circuit:

XOR implemented with NOT gates (Inverters) and AND gates (Sum of products form)

Explanation


Assume we want to use an AND gate as a building block for our resulting circuit. Wherever we have an output of 1  it means that the inputs to that and gate should also be 1 .

If we imagine an AND gate being the last gate before the output, wherever there is a 1 we need to understand that the inputs to that gate would have to be 1.

ABA XOR B
000
011
101
110


-For each output that produces a 1, we modify the variable input to match  the modded input listed in the specific row of the table:

Row numberABA XOR BDesired output using AND Gate
i000 
ii011NOT A AND B
iii101A AND NOT B
iv110 

We see that either row ii) OR row iii)  produces a 1, i.e

(NOT A AND B) OR (A AND NOT B)

From this expression, we draw the circuit as shown in the suggested response above.

Part c)

4-to-1 multiplexer

Data Lines (Input) are denoted as x1…x4, select line are denoted as s1 and s2, Output is denoted as f

Alternative Diagram in ASCII :

        _______________________
       |        4-to-1         |
D0 ----|      Multiplexer      |
       |                       |
D1 ----|                       |---> Output
       |                       |
D2 ----|                       |
       |                       |
D3 ----|_______________________|
              |         |
              |         |
              |         |
              |         |
              S1        S0
Data Lines (Input) are denoted as D0...D3, select line are denoted as S0 and S1.

See Note2

Part d) i)

16+8+0+2+1 =27

Explanation/Working:

(0×27)+(0×26)+(0×25)+(1×24)+(1×23)+(0×22)+(1×21)+(1×20)

0+0+0+16+8+0+2+1=27

Part d) ii)


  0111 +
  1110
———-
10101 ← this result cannot be stored in 4 bits.

Part d) iii)


Largest number = 0111 =7 (Show conversion)
Smallest number= 1111= -ve 7 (Show conversion)

Part d) iv)

Suggestion solution 1:


Algorithm, copy all numbers from LSB to MSB up to and including the first 1, then flip remaining bits in that order, i.e
5= 0101

Applying algorithm : 1011

Suggestion solution 2:

+5= 0101
Ones = 0101+1 = 1010
Twos = 1010+1 = 1011

Logic Gates – Formal Introduction
Multiplexers

Attributions to media used in this post

Inductiveload, Public domain, via Wikimedia Commons

Footnotes

  1. https://islandclass.org/2021/10/20/logic-gates-formal-introduction/ ↩︎
  2. https://islandclass.org/2021/10/21/multiplexers/ ↩︎

© 2023  Vedesh Kungebeharry. All rights reserved. 

Diagrams for a Multiplexer in PNG and ASCII Art

vkungeLeave a comment

4-to-1 multiplexer

Data Lines (Input) are denoted as x1…x4, select line are denoted as s1 and s2, Output is denoted as f

Alternative Diagram in ASCII :

        _______________________
       |        4-to-1         |
D0 ----|      Multiplexer      |
       |                       |
D1 ----|                       |---> Output
       |                       |
D2 ----|                       |
       |                       |
D3 ----|_______________________|
              |         |
              |         |
              |         |
              |         |
              S1        S0
Data Lines (Input) are denoted as D0...D3, select line are denoted as S0 and S1.

© 2023  Vedesh Kungebeharry. All rights reserved. 

2013 U1 Q1

vkungeLeave a comment
  1. Part a) i)
  2. Part a) ii)
  3. Part a) iii)
  4. Part b) i)
  5. Part b) ii)
  6. Part b) iii)
  7. Part c)
  8. Part d) i)
  9. Part d) ii)
  10. Part d) iii)

Part a) i)

        _______________________
       |        4-to-1         |
D0 ----|      Multiplexer      |
       |                       |
D1 ----|                       |---> Output
       |                       |
D2 ----|                       |
       |                       |
D3 ----|_______________________|
              |         |
              |         |
              |         |
              |         |
              S1        S0

Part a) ii)

Set the select inputlines to 01 to select the 2nd line, and when input from the 4th line is needed after 1 second (i.e i3), set the select input lines to 11

Part a) iii)

– It always exists in 1 of 2 stable states.
-It can retain its state to achieve storage (in the case the set goes from 1 to 0)

Can be used in RAM Arrays (to implement 1 bit storage) or to Implement a Ripple Counter

Part b) i)


1101

(First bit is 1 for to represent a negative value,

working for 510 to binary :

       2 | 5  

       2 |2  remainder 1

       2 |1  remainder 0 

            0  remainder 1

i.e 510  = 1012

combining the result we get 11012

)

Part b) ii)


1010 (flipped bits of 0101)

Part b) iii)

1010 +1 = 1011

Part c)

(Show binary-decimal conversions)

For an unbiased exponent and unnormalized mantissa:

sign is -ve, Exponent = 2, Mantissa= 0101

i.e -0.0101 x 2­2 = -1.01

-1.012   =  (-1 x 20)+ (0 x 2-1)+ (1 x 2-2)

          = -1 + 0+ ¼

          = -1.25

Part d) i)


Not (Unary operator)

xNot X
01
10

Part d) ii)

AND

xYX AND Y
000
010
100
111

Part d) iii)

OR

xyX OR Y
000
011
101
111

© 2023  Vedesh Kungebeharry. All rights reserved. 

Simple Sorting, Subsorting Tutorial.

vkungeLeave a comment

Step 1: Create Sample Data

First, we will create a sample dataset. We have a list of students with their names, grades, and scores.

Step 2: Enter Data in Excel

Open Excel and enter the following sample data into a new worksheet:

NameGradeScore
John SmithA99
Jane DoeA92
Mike BrownB88
Lisa RayA95
Tom HanksA98
Rita OraC55
Gary OldB82
Tina FeyC55

Step 3: Sorting Data

To sort the data:

  1. Click on any cell in the column you want to sort by (e.g., Grade).
  2. Go to the Data tab on the Excel ribbon.
  3. Click on Sort A to Z (ascending order) or Sort Z to A (descending order).

Step 4: Subsorting (Multi-level Sorting)

Subsort the data by Grade, then by Score, and finally by Name:

  1. Select any cell in the data range.
  2. Go to the Data tab on the Excel ribbon.
  3. Click on the Sort button to open the Sort dialog box.
  4. For the first level, choose Grade from the Sort by dropdown, select Values in the Sort On dropdown, and choose A to Z for the order.
  5. Click Add Level to add a second sort condition.
  6. For the second level, choose Score from the Then by dropdown, select Values in the Sort On dropdown, and choose  Largest to Smallest for the order.
  7. Click Add Level again to add a third sort condition.
  8. For the third level, choose Name from the Then by dropdown, select Values in the Sort On dropdown, and choose A to Z for the order.
  9. Click OK to apply the multi-level sort to your data.

Step 5: Review Sorted Data

What happens when 1 student has the same grade and score as another?

Sample Data

Download a file containing the sample data here:

https://drive.google.com/drive/folders/1JXTLenz8FvsX9GijfMCKkGCzQfnrlkS5?usp=drive_link

Updates to this post

2023/11/17 – Changed values for score to make the example more reasonable.

© 2023  Vedesh Kungebeharry. All rights reserved. 

Simple Chart Exercise / Tutorial (With Solution)

vkungeLeave a comment
Simple Chart Exercise Tutorial (With Solution)

Task:

Create a bar chart which compares the income, expenses, and profit for the first four months of the year.

Setup a table as shown below with values of your choosing create the chart:

IncomeExpensesProfit
Jan
Feb
Mar
Apr

Tutorial (TA-Note)

Creating the Table:

  1. Open Excel.
  2. Click on “Cell A1” and type “Month”.
  3. Starting from “Cell A2” downwards, type the months: Jan, Feb, Mar, and Apr.
  4. Click on “Cell B1” and type “Income”. Similarly, fill in “Cell C1” with “Expenses” and “Cell D1” with “Profit”.
  5. You now have your table headings ready. You can enter your data in the cells below each heading.

Creating the Bar Chart:

  1. Select the Data: Click and drag to select the cells from A1 through D5 (assuming you have data entered till the April row).
  2. Insert a Bar Chart:
    • Go to the “Insert” tab in the Excel ribbon.
    • In the “Charts” group, click on the “Column or Bar Chart” icon (it looks like a column/bar chart).
    • A drop-down menu will appear. Choose the first option under “Clustered Bar” or any other bar chart type you prefer.
  3. Adjusting the Chart (Optional):
    • Click on the chart. This will reveal three new tabs in the ribbon: “Chart Design,” “Format,” and a third contextual tab related to the type of chart.
    • Use the “Chart Design” tab to quickly adjust the chart’s layout, style, and other elements.
    • Use the “Format” tab to refine the chart’s appearance further.
  4. Title & Labels:
    • By default, Excel might add a title, axis labels, and a legend. You can click on these elements to edit them.
    • To add labels or other elements, right-click on the chart and select the desired option from the context menu.
  5. Once satisfied with the appearance and data representation of the chart, you can save your Excel sheet.

Solution

See the attached excel file:

https://drive.google.com/drive/folders/1r78T3OnNbjDJoIxOdBOXtmkAGUboqRlT?usp=sharing

© 2023  Vedesh Kungebeharry. All rights reserved.