Introduction

This question tested the following topics/items:

• Programming paradigms: object-oriented vs. functional
• Stages of the program translation process: lexical analysis, syntax analysis, code generation
• The need for different programming languages
• Writing a C function that processes an array

Part a)

An object-oriented language organises a program around objects, which combine data (attributes) and the methods that operate on that data. Objects are created from classes and use features such as encapsulation and inheritance, e.g. Java, C++.

A functional language builds a program by applying and combining mathematical functions. Functions return values without changing the program’s state (no side effects), and data is usually not modified once created, e.g. Haskell, Lisp.

See this note: External Resource: Types of Programming languages

Part b) i)

Lexical analysis: The source code is broken up into tokens (keywords, identifiers, operators, literals, punctuation). White space and comments are removed, a symbol table is built, and illegal tokens (lexical errors) are reported.

Part b) ii)

Syntax analysis: The tokens are checked against the grammatical rules of the language, and a parse tree is generated. Syntax errors (e.g. a missing semicolon or bracket) are reported.

Part b) iii)

Code generation: The (optimised) intermediate code is converted into the target machine’s assembly/object code (machine instructions), and memory locations and registers are assigned to the variables.

See this note: Translation (Program Translation During the Compilation process), Lexical Analysis, Syntax analysis (parsing), Code Generation (Object Code)

Part c)

Different programming languages are needed because each is designed to suit a particular type of application, so no single language is the best choice for every problem:

• JavaScript is designed for web applications. It runs inside the web browser and can make web pages interactive (e.g. validating a form or updating page content) without needing to reload the page.
• C/C++ is used for games (and system software) because it compiles to fast machine code and gives the programmer low-level control over memory and hardware, which is needed for high-performance graphics.
• Other examples: FORTRAN for formula translation (scientific and mathematical calculations), and Swift/Kotlin for mobile device applications.

Therefore, the language is chosen based on how appropriate it is for the application (speed, platform, ease of development and the features it provides).

See this note: External Resource: Types of Programming languages

Part d)

void maximum(int arr[], int size)
{
    int i;
    int max = arr[0];              //assume the first element is the largest

    for (i = 1; i < size; i++)     //compare against every other element
    {
        if (arr[i] > max)
            max = arr[i];          //a larger value was found
    }

    printf("The maximum value is %d\n", max);
}

Further explanation

The function returns void since it should not return a value. It starts by assuming that arr[0] is the largest, and then traverses the rest of the array using a loop. Whenever a larger element is found, it replaces max. After the loop, max holds the largest value, which is printed.

A complete program to test the function (writing the function only would be sufficient):

#include <stdio.h>

//prints the largest value stored in arr; size is the number of elements
void maximum(int arr[], int size)
{
    int i;
    int max = arr[0];              //assume the first element is the largest

    for (i = 1; i < size; i++)     //compare against every other element
    {
        if (arr[i] > max)
            max = arr[i];          //a larger value was found
    }

    printf("The maximum value is %d\n", max);
}

int main()
{
    int numbers[] = {12, 45, -3, 67, 9};
    maximum(numbers, 5);           //prints: The maximum value is 67
    return 0;
}

See this note: Introduction to functions, Linear search

Links to Notes

© 2026 Vedesh Kungebeharry. All rights reserved.

Introduction

This question tested the following topics/items:

• Debugging
• Programming style for maintainable code: indentation and comments
• Identifying and correcting errors in C code (for loops, printf format specifiers, string literals)
• File operations in C: read, append and close

Part a) i)

Debugging is the process of detecting, locating and correcting (removing) errors in a program.

See this note: Debugging

Part a) ii)

Indentation: Code is indented every time a control structure (e.g. a loop or an IF) is entered. This shows which statements belong to each block, making the logic easier to read, follow and modify.

Comments: Comments explain what sections of code are intended to do (and why), making it easier for the programmer or another programmer to understand and update the code later.

See this note: 2019 U1 Q5

Part b)

Corrected code:

int a, b;
for (a = 1; a <= 5; a++)                //a was not incremented
    for (b = 1; b < a; b = b + 1)
        printf ("%d", b);               //%d is used for integers, not %s
printf ("\n");                          //string must be in double quotes

Note: As in similar past questions, the indentation suggests that the inner loop and the last printf may have been meant to be inside braces { } for the outer loop. The question only asks for the three errors, so this is not required.

See this note: Adding 2 numbers – Outputting the result with printf(), Examples of Errors During Compilation Stages (Lexical, Syntax, Semantic)

Part c) i)

FILE *fp;
int num;
fp = fopen("data.txt", "r");    //open the file for reading
fscanf(fp, "%d", &num);         //read a value from the file

Part c) ii)

fp = fopen("data.txt", "a");    //open the file in append mode
fprintf(fp, "%d\n", num);       //write the value to the end of the file

Part c) iii)

fclose(fp);                     //close the file

Further explanation

A complete program using all three operations:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE *fp;          //file pointer
    int num;

    //(i) Read: open the file for reading and read a value from it
    fp = fopen("data.txt", "r");
    if (fp == NULL)
    {
        printf("Error opening file\n");
        return 1;
    }
    fscanf(fp, "%d", &num);
    printf("Value read: %d\n", num);
    fclose(fp);

    //(ii) Append: open the file in append mode and add a value to the end
    fp = fopen("data.txt", "a");
    fprintf(fp, "%d\n", 25);

    //(iii) Close: close the file
    fclose(fp);

    return 0;
}

“r” opens an existing file for reading, “a” opens a file for appending (data is added to the end of the file, and the file is created if it does not exist), and fclose() closes the file so that the data is saved and the file pointer is released.

See this note: Tutorial: Storing and loading data in a plain textfile., Strategy For Storing Records In Plaintext Files

Links to Notes

© 2026 Vedesh Kungebeharry. All rights reserved.

Introduction

This question tested the following topics/items:

• Problem-solving methods: stepwise refinement and bottom-up design
• Control constructs in structured programming
• Determining the output of an algorithm with nested selection
• Completing a trace table for a while loop

Part a) i)

Stepwise refinement is a method where the problem is first written as a few major steps, and each step is then broken down (refined) repeatedly into smaller, more detailed sub-steps until each step is simple enough to be converted directly into program code.

See this note: Introduction to Top-Down Stepwise Refinement

Part a) ii)

In the bottom-up method, the smallest, most detailed sub-problems (modules) are solved, coded and tested first. These modules are then combined to form larger modules, and so on, until the complete solution to the overall problem is built.

Part b)

• Sequence
• Selection (e.g. IF-THEN-ELSE)
• Iteration/Repetition (looping, e.g. FOR, WHILE)

See this note: Constructs used in structured programming

Part c) i)

GREEN

Part c) ii)

BLUE
GREEN

Part c) iii)

RED
GREEN

Explanation

When num = 1, the condition num > 1 is false, so the whole inner IF is skipped and only GREEN is printed. When num = 2, num > 1 is true but num == 3 is false, so the ELSE prints BLUE, then GREEN is printed. When num = 3, both conditions are true, so RED is printed, then GREEN. GREEN is always printed because it is outside both IF statements.

See this note: The Selection Construct

Part d)

Initially x = 9, y = 2

Further explanation

Each time through the loop, y is increased by 1 and x is decreased by 1, then x and y are printed. After the 4th iteration, x = 5 and y = 6, so the condition x > y (5 > 6) is false and the loop ends. There is no 5th iteration, so that row stays empty.

See this note: SBA-How to Approach a Dry run using test data and trace tables to uncover errors in your algorithm, Repetition (Iteration) Constructs

Links to Notes

© 2026 Vedesh Kungebeharry. All rights reserved.

Introduction

This question tested the following topics/items:

• Stages in the problem-solving process (applied to a software project)
• Properties of well-defined algorithms
• Representing an algorithm using a flowchart
• Selection (nested/multiple IF) to apply rates to a range of values

Part a)

Any two of the following stages (definition + what it involves for TechWorld):

Problem definition – The software company states precisely and concisely what the software must do, i.e. move TechWorld from its current way of working to the desired state. For example: the software must track purchases, the quantity of laptops and tablets in stock, and customer information.

Problem analysis – The company determines all the details needed to solve the problem: the inputs (e.g. purchase details, item details, customer details), the processing (e.g. update the stock quantity when a laptop or tablet is sold) and the outputs (e.g. stock reports, customer lists). Functional and non-functional requirements are gathered, e.g. by interviewing TechWorld’s staff.

Identify and evaluate possible solutions – Several possible solutions are generated (e.g. an off-the-shelf package, a custom desktop application or a web-based system), and the strengths and weaknesses of each are compared.

Select and justify the optimal solution – The best solution is chosen based on criteria such as cost, speed, storage and how well it meets TechWorld’s requirements. A detailed algorithm of the chosen solution is produced.

Implementation and review – The solution is coded, tested and installed at TechWorld. It is then reviewed using feedback from the users to make sure it solves the original problem, and it is maintained afterwards.

See this note: Stages in problem solving

Part b) i)

Any two:

• It has a finite number of steps (it must terminate).
• The steps are clearly defined, precise and unambiguous.
• It shows the flow of control from one process to another.
• It is a general solution to the problem (it works for all valid inputs).

See this note: Algorithms, WHAT IS AN ALGORITHM? – DEFINITION

Part b) ii)

Suggested response:

                    +-----------+
                    |   START   |
                    +-----------+
                          |
                          v
                  /---------------/
                 /    READ gb    /
                /---------------/
                          |
                          v
                     /---------\
                    <  gb < 1 ? >----Yes--->[ cost = gb * 4.00 ]-----+
                     \---------/                                     |
                          | No                                       |
                          v                                          |
                     /---------\                                     |
                    < gb <= 2 ? >----Yes--->[ cost = gb * 3.00 ]-----+
                     \---------/                                     |
                          | No                                       |
                          v                                          |
                [ cost = gb * 2.50 ]                                 |
                          |                                          |
                          +<-----------------------------------------+
                          |
                          v
                  /---------------/
                 /   PRINT cost  /
                /---------------/
                          |
                          v
                    +-----------+
                    |    STOP   |
                    +-----------+

Flowchart symbols: START/STOP – terminal (oval); READ/PRINT – input/output (parallelogram); cost = … – process (rectangle); gb < 1 ? – decision (diamond).

Further explanation

The same algorithm in pseudocode:

START
READ gb
IF gb < 1 THEN
    cost <-- gb * 4.00
ELSE
    IF gb <= 2 THEN
        cost <-- gb * 3.00
    ELSE
        cost <-- gb * 2.50
    ENDIF
ENDIF
PRINT cost
STOP

Testing the algorithm:

Note: “Between 1 and 2 gigabytes” is taken to include 1 and 2. The rate is applied to all gigabytes used (not in tiers).

See this note: Flowcharts – Representation, Using multiple selection statements (By Example)

Links to Notes

© 2026 Vedesh Kungebeharry. All rights reserved.

Introduction

This question tested the following topics/items:

• Designing a logic circuit from a truth table using only primary logic gates (AND, OR, NOT)
• Multiplexers: purpose and use of the select lines
• Block diagram of a 4-to-1 multiplexer
• Signed magnitude representation (range of integers in 8 bits)
• Two’s complement representation of a negative integer

Part a)

Suggested response:

Z = 1 when A and B are both 0 OR when A and B are both 1, i.e.

Z = (NOT A AND NOT B) OR (A AND B)    i.e.  Z = A’.B’ + A.B

Circuit:

A --------+-------------------------------+
          |                               |---[ AND ]--- A.B ------+
B --------|------+------------------------+                        |
          |      |                                                 +---[ OR ]--- Z
          |      |                                                 |
          +------|---[ NOT ]---- A' ------+                        |
                 |                        |---[ AND ]--- A'.B' ----+
                 +---[ NOT ]---- B' ------+

Two NOT gates produce A’ and B’. One AND gate produces A.B, a second AND gate produces A’.B’, and the OR gate combines both products to give the output Z. (This circuit is an XNOR, i.e. an equivalence circuit.)

Gate symbols to use when drawing the circuit:

Explanation

For each row that produces a 1, we write an AND term that is true only for that row’s inputs (an input that is 0 is inverted with a NOT gate):

We see that either row i) OR row iv) produces a 1, i.e. (NOT A AND NOT B) OR (A AND B). From this expression, we draw the circuit as shown in the suggested response above.

See this note: 2009 U1 Q1, Logic Gates – Formal Introduction

Part b) i)

The four sensors are connected to the four data input lines (D0 to D3) of a 4-to-1 multiplexer, and the multiplexer’s single output is connected to the alarm notification line.

The two select lines (S1 S0) are driven by a counter/timer which changes every second through 00, 01, 10, 11. Each select value routes one sensor’s data to the output line, e.g. 00 selects Sensor 1 and 01 selects Sensor 2.

Therefore, each sensor gets to transmit its data on the single line for one second in turn, and the cycle then repeats (time-division multiplexing). This way only one line is needed instead of four.

See this note: Multiplexers, 2013 U1 Q1

Part b) ii)

                     _______________________
Sensor 1 ------ D0 -|                       |
                    |        4-to-1         |
Sensor 2 ------ D1 -|      Multiplexer      |
                    |                       |----> Output (single line to
Sensor 3 ------ D2 -|                       |      the alarm notification unit)
                    |                       |
Sensor 4 ------ D3 -|_______________________|
                           |         |
                           S1        S0
                           |         |
                    +-----------------------+
                    |  2-bit counter/timer  |
                    |  (changes every 1 s)  |
                    |  00 > 01 > 10 > 11    |
                    +-----------------------+

Data lines (inputs) D0 to D3 are connected to Sensors 1 to 4. The select lines are S1 and S0, and the single output goes to the alarm notification unit.

Alternative diagram:

See this note: Diagrams for a Multiplexer in PNG and ASCII Art

Part c) i)

Smallest integer = -127  (1111 1111)

Largest integer = +127  (0111 1111)

Explanation/Working:

In signed magnitude, the MSB is the sign bit (0 = +ve, 1 = -ve) and the remaining 7 bits hold the magnitude. The largest magnitude in 7 bits is 111 1111₂ = 2⁷ – 1 = 127, so the range is -127 to +127.

Part c) ii)

-87 = 1010 1001

Explanation/Working:

Step 1: Convert +87 to 8-bit binary:

87 = 64 + 16 + 4 + 2 + 1

+87 = 0101 0111

Step 2: Flip the bits (ones complement): 1010 1000

Step 3: Add 1: 1010 1000 + 1 = 1010 1001

Check: -128 + 32 + 8 + 1 = -87

See this note: Binary Manipulation, Solution to The Largest and Smallest magnitude twos complement numbers using 4 bits

Links to Notes

Attributions to media used in this post

Inductiveload, Public domain, via Wikimedia Commons (AND, OR and NOT gate symbols)

User:Mdd4696, Public domain, via Wikimedia Commons (4-to-1 multiplexer)

© 2026 Vedesh Kungebeharry. All rights reserved.

Introduction

This question tested the following topics/items:

• Registers found in the CPU: Instruction Register (IR), Memory Address Register (MAR) and Memory Data Register (MDR)
• Storage devices vs. memory: access method and access speed (hard disk vs. RAM)
• Memory features: volatility; storage device features: portability (RAM vs. flash drive)
• Instruction format (opcode and operand/address fields)
• Addresses per instruction: one-address and two-address instructions

Part a) i)

The Instruction Register (IR) holds the instruction that has just been fetched from memory while it is being decoded and executed.

Part a) ii)

The Memory Address Register (MAR) holds the address of the memory location that is about to be read from or written to.

Part a) iii)

The Memory Data Register (MDR) temporarily holds the data (or instruction) that has just been read from memory, or the data that is about to be written to memory.

Further explanation

During the fetch stage, the address in the Program Counter (PC) is copied to the MAR, the instruction stored at that address is copied from memory into the MDR, and then from the MDR into the IR (also called the CIR, Current Instruction Register) so that it can be decoded.

See this note: 2009 U1 Q2 Part C

Part b) i)

Access method: A hard disk uses direct (semi-random) access. The read/write head must first move to the correct track (seek time) and then wait for the required sector to rotate under it (rotational delay) before the data can be read. RAM uses random access. Any memory location can be accessed directly, electronically, using its address, and it takes the same time no matter where the data is stored.

Access speed: Since the hard disk depends on moving mechanical parts, its access time is measured in milliseconds. RAM has no moving parts, so its access time is measured in nanoseconds. RAM is therefore many thousands of times faster than a hard disk.

See this note: Serial, Sequential, Direct (Random) Access

Part b) ii)

Volatility: RAM is volatile, i.e. its contents are lost when the power is switched off. A flash drive is non-volatile, i.e. it keeps its data when it is unplugged or the power is removed, since it uses flash memory (a type of EEPROM).

Portability: RAM is installed internally on the motherboard and is not designed to be removed and carried from one computer to another. A flash drive is small and light and connects to a USB port, so it is designed to be carried around and used to transfer data between computers.

Summary

See this note: Videos: The Major components of a computer system

Part c) i)

The instruction format is the layout of a machine code instruction, i.e. how the bits of the instruction are divided into fields. It is made up of an opcode field, which specifies the operation to be carried out, and one or more operand (address) fields, which specify the data, or the address of the data, to be used. The format also fixes how many bits are given to each field, how many addresses the instruction has, and whether instructions are of fixed or variable length.

See this note: 2009 U1 Q2 Part C

Part c) ii)

One-address

The instruction has an opcode and one address field. The second operand is implied: it is held in the accumulator (AC), and the result of the operation is also stored in the accumulator.

e.g. ADD X means AC ← AC + [X]

Two-address

The instruction has an opcode and two address fields, so both operands are given explicitly. The result is usually stored in the location given by the first address, which overwrites its original value.

e.g. ADD X, Y means X ← [X] + [Y]

Further explanation

The instructions needed to calculate X = A + B using each format:

One-address:

LOAD  A    ; AC ← [A]
ADD   B    ; AC ← AC + [B]
STORE X    ; X  ← AC

Two-address:

MOVE  X, A ; X ← [A]
ADD   X, B ; X ← [X] + [B]

One-address instructions are shorter, but more of them are needed. Two-address instructions are longer, but fewer instructions are needed.

Links to Notes

© 2026 Vedesh Kungebeharry. All rights reserved.

Introduction

This question tested the following topics/items:

• Client/Server Network Architecture
• Peer-to-Peer (P2P) Network Architecture
• Advantages and Disadvantages of Network Types
• Network Security
• Firewalls
• Firewall Configuration and Maintenance
• Security Patches and Updates
• Network Protocols
• Fiber Distributed Data Interface (FDDI)
• Ethernet Protocol
• Network Topologies (Token Ring, Star)
• Physical Media in Networking (Fiber Optics, Copper Cables)
• Open Systems Interconnection (OSI) Model
• Transport Layer Responsibilities
• Network Layer Responsibilities
• Data Segmentation and Reassembly
• End-to-End Communication
• Error Detection and Correction
• Data Flow Control
• Packet Routing and Forwarding
• IP Addressing
• Wireless Networks
• Advantages of Wireless Connectivity
• Wireless Router Setup and Configuration
• Mobile Data Communication
• General Packet Radio Service (GPRS)
• Cellular Network Technology
• Applications of GPRS (e.g., POS Systems, MMS, Tracking)
• Network Performance and Efficiency Considerations

1. Introduction
2. Part a)
3. Part b) i)
4. Part b) ii)
5. Part c)
6. Part d)
7. Part e)
8. Part f) i)
9. Part f) ii)

Part a)

A client server network has one or more computer nodes providing all the services needed by all other client computers.  E.g web server, ftp server etc.

Hardware and resources are easily configured.

Servers can be administered to allow connection only to authorized computers on the network thus benefit from better security.

The sever can easily undergo regular backups easily since all data is centralized.

For P2P each computer on the network can act as a server for all others on the network.

Each node on the P2P is not guaranteed to be powerful, and mostly have the average power as clients.

This configuration is difficult to keep secure, additional third party software is usually required to implement security.

P2P networks add strain on the network as more peers are added to the network since sometimes one node would be responsible for routing a lot of traffic to all others. It is impractical to attempt backup on this network configuration.

Part b) i)

A firewall is a hardware and/or software security measure which protects against external network threats in the form of unauthorized connections or attacks. It also filters connections within the network to prevent malicious activity.

Part b) ii)

New computer threats emerge every day, and thus the firewall must apply frequent updates which protect against new computer threats.

Part c)

Fddi uses fibre optic cables , and transfers data using token ring topology, and can be much faster over long distances (200 Km). The ring technology includes additional rings in the event that one ring fails, another exists to carry on data communication.

Ethernet mainly uses copper wires, and transfers data using packet switching (Star Topology), over shorter distances (100 m) and is slower than FDDI. Ethernet does not typically have backup lines to help prevent network failure.

Part d)

The Transport layer is responsible for segmenting packets and reliable communications across the transport layer by implementing end to end communication with error checking and data flow control (speed changes between networks)

The network layer is responsible for efficiently routing data from network to network by choosing the best paths using IP protocol which gives each node on the network a unique IP address.

Part e)

• It is convenient, the wireless signals penetrate walls and floors in all directions. Cable installation from floor to floor is not required.
• It allows for additional mobility within the range oof connection
• Overall, It is cheaper, since wired cables are not needed to be used.

Part f) i)

It is designed to provide wireless network connectivity over a cellular network so that traditional network tasks, e.g. connecting to the internet, can be facilitated. It was developed for wireless POS systems, MMS, tracking and navigation , wireless electricity meters , etc.

Part f) ii)

• Allowing for wireless POS payments over the cell network when purchasing groceries without needing a phone line.
• Allowing the electric company to carry out wireless meter readings without having to perform a physical house visit to read the meter.

© 2023  Vedesh Kungebeharry. All rights reserved. 

Introduction

This question tested the following operating system concepts:

1. Introduction
2. Part a)
3. Part b) i)
4. Part b) ii)
5. Part b) iii)
6. Part c)
7. Part d)
   1. Further explanation
8. Part e) i)
9. Part e) ii)
10. Part e) iii)
11. Footnotes

Part a)

A program is a set of computer instructions that is stored on secondary storage, and a process is a program that is currently being executed on the cpu, it’s instructions and data are stored in main memory – RAM and registers in the CPU.

Part b) i)

It’s time on the CPU has expired.

Part b) ii)

It is waiting on data from an IO operation and cannot continue until it receives the data.

Part b) iii)

The process has completed all of its instructions and no longer needs any of it’s previous system resources.

Part c)

P1 is using d1,

P2 is using d1,

Eventually p1 needs d2 also, it is put into a waiting state.

P2 needs d1, but d1 is in use by p1 and p1 is waiting on p2 to release d2.

P2 will be put into a waiting state

Both process are waiting on each other and will not release the DVD resources that they are allocated, thus neither process can complete and thus we say they are deadlocked.

Part d)

Windows 10, is a multitasking operating system, tasks share time on the CPU.

Linux is a multiprocessing operating system allowing for the running of separate tasks on separate CPUs, thus achieving higher performance.

Further explanation

All present-day operating systems support multitasking and multiprocessing, there are cases where multiprocessing may not be used, e.g where an embedded system is designed for specific task that doesn’t require much processing power.

Part e) i)

Sometimes many processes need to be run simultaneously, and the needs for physical memory can exceed the actual memory that is available.

Part e) ii)

Multiple page frames are created for each process. Ideally, the currently running’s process’s frames are stored in physical ram, and all other ready or waiting processes are stored in ram. As more processes are run which exceed the physical ram capacity, the page frames for the ready and waiting processes are swapped out of physical ram onto the page file on the hard disk to accommodate running processes. When a running process is put into waiting/ready state, it may be put on the virtual page file, and  the next process to be run can be put from the virtual page file back into the physical ram to be run.

Part e) iii)

The system can operate inefficiently since a lot of swapping may occur, and this is dependent on the much slower hard disk memory access for each swap. This condition is know as thrashing.

Footnotes

1. TA-Note ↩︎

© 2023  Vedesh Kungebeharry. All rights reserved. 

Part a) i)

int numseq[21];

Further explanation  

21 locations needed for numbers 0 to 20)

Part a) ii)

19

Part a) iii)

Suggested response

int binarySearch(int key, int list[], int low, int high) {
    int result = -1; 
    int keyFound = 0; //sentinel to end loop on a successful search

    while (low <= high && !keyFound) {
        int middle = (high-low) / 2 + low;//determine middle of the range

        if (key == list[middle]) 
        {
            result = middle;
            keyFound=1; // Key found, exit loop

        } 
        else if (key < list[middle]) 
        { 
            high = middle - 1; // Narrow the search to the lower half
        } 
        else 
        
            low = middle + 1; // Narrow the search to the upper half
        }
    }

    return result; //Returns -1 if not found, 
                   //otherwise, the index of the key
}

Further Explanation

(See this note¹)

int binarySearch(int key, int list[], int low, int high) {
    int result = -1; //result is -1 if not found
    int keyFound = 0; //sentinel to end loop on a successful search

    while (low <= high && !keyFound) //while there is more locations 
                                     //to search and the key has not 
                                     //been found
    {
        int middle = (high-low) / 2 + low;//determine middle of the range

        if (key == list[middle]) //if the key is found..
        {
            result = middle;
            keyFound=1; // Key found, exit loop
        } 
        else if (key < list[middle]) //if key may be in the lower half...
        { 
            high = middle - 1; // Narrow the search to the lower half
        } 
        else //else the key may be in the upper half
        {
            low = middle + 1; // Narrow the search to the upper half
        }
    }

    return result; // Returns -1 if not found, otherwise the key

Response using recursion

int binarySearch(int key, int  list[], int low, int high)
{
    
    int result=-1;
    int middle = (high-low)/2+low;

    if (low<=high)//if low and high have not crossed...
    {
        if(key==list[middle])//if the key is found....
        {
            result=middle;
            return result
        }
        else//the key was not found
        {
            if(key<list[middle])
            {                   

               
                result= binarySearch(key,list,low,middle-1);
                return result;
            }

            else 
            {
                result= binarySearch(key,list,middle+1,high);
                return result;
            }

        }
    }
    return result;

Further Explanation

int binarySearch(int key, int  list[], int low, int high)
{
    /*we use low and high to represent a
    portion of the array. Initially, low and high
    points to the start of the array and the end of
    the array respectively. Middle indexes the location
     to the middle of the array.
    */
    int result=-1;//-1 represents a failed search
    int middle = (high-low)/2+low;

    if (low<=high)//if low and high have not crossed...
    {
        if(key==list[middle])//if the key is found....
        {
            result=middle;
            return result;//return the current index and exit function
        }
        else//the key was not found
        {
            if(key<list[middle])//if the key would be found
            {                   //from low to middle

               //we now search the lower half
                result= binarySearch(key,list,low,middle-1);
                return result;
            }

            else //key would be found from middle to high
            {
                result= binarySearch(key,list,middle+1,high);//we now search the upper half
                return result;
            }

        }
    }
    return result;

Part b i)

//assume integer array
void swap(int array[], int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

Part b ii)

• The array is traversed from index 0 to n and the location of the smallest element is determined.
• The smallest element is swapped with the first element that was traversed.
• This is repeated on the unsorted portion of the array by  incrementing the starting element that is traversed to 1 to n, then 2 to n, 3 to n, … until n-1 to n.

Part b iii)

void selectionSort (int arr[], int low, int high)
{
    for (int i = low; i<high; i++)
    {
        int smallest = getSmallest(arr,i,high);
        swap(arr,i,smallest);
    }
}

Further explanation

The following complete program in C tests that the selection sort is working.

#include <stdio.h>
 
//function declarations
void selectionSort(int arr[], int low, int high);
void swap(int array[], int a, int b);
int getSmallest(int arr[], int low, int high);
 
int main()
{
    int array[] = {64, 25, 12, 22, 11};
    int size = sizeof(array) / sizeof(array[0]);
   
 
    printf("Original array: ");
    for (int i = 0; i < size; i++)
        printf("%d ", array[i]);
    printf("\n");
 
    //sort the array
    selectionSort(array, 0, size-1);
 
    printf("Sorted array: ");
    for (int i = 0; i < size; i++)
        printf("%d ", array[i]);
    printf("\n");
 
    printf("\nEnding program...");
 
    return 0;
}
 
void selectionSort(int arr[], int low, int high) {
    // Traverse up to the
    // second-to-last element
    for (int i = low; i < high; i++)
    {
        /*find the index of the smallest
        element in the range
        */
        int smallest = getSmallest(arr, i, high);
       
        /*if the smallest element
        should be put in the first
        position that was
        traversed ...
        */
        if(arr[smallest]<arr[i])
            swap(arr, i, smallest);//swap elements
    }
}
 
void swap(int array[], int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}
 
int getSmallest(int arr[], int low, int high) {
    int smallestIndex = low;
    // Include the high in the search
    for (int i = low + 1; i <= high; i++)
    {
        if (arr[i] < arr[smallestIndex]) {
            smallestIndex = i;
        }
    }
    return smallestIndex;
}

Part c)

(See this note²)

Footnotes

1. https://islandclass.org/2020/11/12/binary-search-implementation/ ↩︎
2. https://islandclass.org/2020/11/04/bubble-sort-implementation-demonstration/ ↩︎

Navigation

1. Part a) i)
   1. Further explanation  
2. Part a) ii)
3. Part a) iii)
   1. Suggested response
   2. Further Explanation
   3. Response using recursion
   4. Further Explanation
4. Part b i)
5. Part b ii)
6. Part b iii)
7. Further explanation
8. Part c)
9. Footnotes
10. Navigation

© 2023  Vedesh Kungebeharry. All rights reserved.