More results...

Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors
post
page
Python IDE Dashboard

The ice cream Stack

In this blog post, we will investigate the use of a Stack data structure to store the different flavours of the different scoops of an ice cream!

A stack is a FILO data structure: First In Last Out and seems to be a suitable data structure for our ice cream, where the first scoop of ice-cream being added on the cone, will be the last one to be eaten!

With a Stack data structure you can either:

  • Push new data at the end of the stack.
  • Pop the last value of the stack.

ice-cream-stack

In order to implement our stack will use a 1D array of 5 values, assuming that you cannot make an ice cream with more than 5 scoops! We will use a pointer to store the index of the next empty cell of our array where data can be added.

Using OOP programming, we will create an IceCream class to implement our ice cream as a stack. We will encapsulate both the array data structure and the stack pointer as private properties of the IceCream class and we will use two public methods to push() and pop() scoops of different flavours to/from our IceCream!

Let’s look at the code of our class:

#A class to implement a Stack that can hold up to 5 values
class IceCream():
    #Constructor...
    def __init__(self):
        self.__array = [None,None,None,None,None] #__Private Property
        self.__pointer = 0  #__Private Property
        self.__maxCapacity = len(self.__array) #__Private Property

    #A method to push a new scoop/flavour to the ice cream
    def push(self, flavour):
        #Let's first check that we have not reached the maximum capacity (5 scoops max)
        if self.__pointer < self.__maxCapacity:
             self.__array[self.__pointer] = flavour
             self.__pointer = self.__pointer + 1
             print(flavour + " added!")
        else:
             print("Cannot add new favour! Ice cream is full!")

    #A method to pop the last scoop/flavour of the ice cream
    def pop(self):
        #Let's first check that the ice cream is not empty (has at least 1 scoop)
        if self.__pointer > 0:
             self.__pointer = self.__pointer - 1
             flavour = self.__array[self.__pointer]
             self.__array[self.__pointer] = ""
             return flavour
        else:
             print("Ice cream is empty!")
             return False

Now that we have an IceCream class, we can instantiate any ice cream object and construct each ice cream by pushing (and popping/eating) different flavours!

myIceCream = IceCream()

myIceCream.push("Strawberry")
myIceCream.push("Chocolate")
myIceCream.push("Pistachio")

flavour = myIceCream.pop()
print("This scoop of " + flavour + " was delicious!")

myIceCream.push("Blueberry")

Full Python Code

Let’s test this code… You can customise this code to create any ice cream based on your favourite flavours!!!

IP Addresses (IPv4, IPv6), MAC Addresses & URLs

In this blog post, we are going to learn about the format of different addresses used on computer networks to uniquely identify hardware devices. We will investigate the use and format of:

  • IPv4 Addresses,
  • IPv6 Addresses,
  • MAC Addresses.

IPv4 Addresses

An IP address is a unique identifier of a device on an IP network.

An IP address (IPv4) consists of 4 Bytes: 4 numbers between 0 and 255 separated by dots.

IPv4:

A dynamic IP Address can change every time your restart your device/reconnect to the network. Some devices can be configured on an IP network to have a static IP address: it will remain she same even if you restart your device.

As an IPv4 address consists of 4 Bytes (=32 bits), there are 232 possible IP addresses which is just under 4.3 billions IP addresses. Though this seems like a large number, we are reaching a stage where we are running out of unique IP addresses. Remember, every device (router, computer, smartphone, smartwatch, smart TV, smart speaker, etc.) connected to the Internet will have its own IP address and there are nearly 8 billions human beings on planet Earth. This is the reason why the Internet is progressively upgrading to the next generation of IP addresses: IPv6…

IPv6 Addresses

To overcome the issue of the Internet running out of unique IPv4 addresses, a new format was introduced. IPv6 addresses consist of 16 Bytes (=128 bits). They are expressed in hexadecimal using 8 blocks of 2 Bytes (4 hexadecimal digits) separated by colons e.g.:

IPv6:

With 128 bits per IP address, we can generate 2128 unique IP addresses. That’s 340,282,366,920,938,463,463,374,607,431,768,211,456 IP addresses, more than enough to give each grain of sand on planet Earth a unique IP address!!!

MAC Addresses

A MAC address consists of 6 Bytes of Data, expressed in hexadecimal, separated using colons. e.g.

MAC Address:

A MAC Address is static and unique for a device. It cannot change. It is hardcoded into the device by the manufacturer when the device is built. (A bit like the chassis number of a car!)

Networking equipment such as routers and switches use IP addresses and/or MAC addresses to direct traffic between computers/devices on the network.

URL: Uniform Resource Locator

A live website is hosted/stored on a webserver and consists of different files such as HTML pages, png graphics, jpg pictures, gif animations and other multimedia files (mp3 audio clips, mp4 movie clips, pdf documents etc.). These files are stored on the web server within a root folder and other subfolders. A URL is used to request a specific file (resource) stored on a web server.

A URL is used to request/locate a specific resource stored on a web server. It consists of:

  • The protocol used to access the web page: either HTTP or HTTPs,
  • The Domain Name to identify the web server,
  • Optional: Folder/Sub-folder structure: If the resource/file you are trying to access is not on the root folder of the website but in a sub-folder,
  • Optional: File name: the file name and extension of the file you are requesting. If the filename is not provided, the server will return the index.html file if it exists.
URL

Error 404: Page Not Found

When a URL points towards a file that cannot be located or simply does not exist on the webserver, a 404 error message is returned to the web browser!

error-404

Domain Name Server

In order to connect to a website, your web-browser needs to know the IP address of the webserver where the website is hosted. However, IP address are tricky to remember (for human beings). This is why domain names were invented! Domains names such as 101computing.net or amazon.com are easy to remember. When the user types a domain name in the address bar of the browser, the browser automatically contacts a DNS server on the Internet. The DNS server will then lookup for the matching IP address for this domain name and return it to the web-browser. The web-browser will then be able to contact the webserver to request a specific page:

DNS-Domain-Name-Server

In a way, we could say that a Domain Name Server is the equivalent of of the phone book that we used to consult when we had the name of someone we wanted to call but did not know their actual phone number. We would lookup for their name in the phone book to retrieve their phone number. Similarly, a Domain Name Server is used to lookup a domain name to find its IP address!

Python Task #1

Write a python program to generate and output:

  • A random IPv4 address,
  • A random IPv6 address,
  • A random MAC address.

Python Task #2

Write a python program that asks the user to enter a URL. The program will then extract and output the following components of the URL:

  • Protocol,
  • Domain Name,
  • Folder Structure,
  • File name.
unlock-access

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area
Tagged with:

Using a Trace Table on a Low Level Program

cpu-chipIn the following set of challenges, we will use a trace table to demonstrate the impact of the FDE cycle on the main registers:

  • Program Counter (PC)
  • Memory Address Register (MAR)
  • Memory Data Register (MDR)
  • Current Instruction Register (CIR)
  • Accumulator (ACC)

Note that the following program are all based on the LMC language and are hence based on direct addressing.

To complete this task, you need to understand what happens inside the CPU at each stage of the FDE cycles. For instance:

  • A the start of the Fetch stage of the FDE cycle, the PC contains the address of the next instruction to be Fetched. So the value of the PC is copied to the MAR so that the instruction can be retrieved from memory. The instruction stored at this MAR address will be stored in the MDR and immediately copied to the CIR.
  • The PC is then automatically incremented by 1.
  • What happens during the Execute stage of the FDE cycle will depend on the instruction itself.
  • It may be that more data may be loaded from memory using the MAR and MDR (e.g. LDA, ADD, SUB instructions).
  • It may be that the PC will be overridden by a BRP, BRZ or BRA instruction.
  • The Accumulator may also be overwritten by an input value (INP), the result of executing a calculation (ADD, SUB) or of loading data from memory (LDA).

Challenge #1Challenge #2Challenge #3

Challenge #1:


When tracing the following algorithm we will use the following input values:

  • First input: 5
  • Second input: 4
  1. INP
  2. STA 99
  3. INP
  4. ADD 99
  5. OUT

Trace Table


We have started to complete the trace table for the first two FDE cycles of this program. Your task is to complete this trace table for the whole program.
 FDE StagePCMARMDRCIRACCOutput?
– RESET –00000
Fetch10INPINP0
Execute10INPINP5
Fetch21STA 99STA 995
Execute2995STA 995


Challenge #2:


When tracing the following algorithm we will use the following input values:

  • First input: 5
  • Second input: 4
  1. INP
  2. STA 99
  3. INP
  4. STA 98
  5. SUB 99
  6. BRP 08
  7. LDA 99
  8. BRA 09
  9. LDA 98
  10. OUT

Trace Table


We have started to complete the trace table for the first two FDE cycles of this program. Your task is to complete this trace table for the whole program.
 FDE StagePCMARMDRCIRACCOutput?
– RESET –00000
Fetch10INPINP0
Execute10INPINP5
Fetch21STA 99STA 995
Execute2995STA 995


Challenge #3:


When tracing the following algorithm we will use the following input value:

  • First input: 3
  1. INP
  2. STA 99
  3. LDA 99
  4. SUB one
  5. STA 99
  6. OUT
  7. BRP 3
  8. HLT
  9. one DAT 1

Trace Table


We have started to complete the trace table for the first two FDE cycles of this program. Your task is to complete this trace table for the whole program.
 FDE StagePCMARMDRCIRACCOutput?
– RESET –00000
Fetch10INPINP0
Execute10INPINP3
Fetch21STA 99STA 993
Execute2993STA 993


Tagged with:

A Level Computer Science Revision

Getting ready for your A Level Computer Science exam? Test our knowledge by answering all the following questions:
A Level Computer Science RevisionOpen in New Window

Debugging and refining an algorithm – Q&A

Question 1[4 marks]
Zara has created the following program in her computer science lesson. The aim of this program is to find out if the user is old enough to vote or not, the voting age being 18 years old. If the user is too young to vote, the program will calculate and output in how many years the user will be allowed to vote!

Here is her Python code:
#Voting Age Checker
a = int(input("How old are you?"))

if a<=18:
  print(You can vote!")
else:
  y = 18 - a
  print("You will be allowed to vote in " + str(y) + " years!")

Zara made two errors in her code. A syntax error and a logic error. Identify these two errors and explain how these could be fixed.
Syntax Error:

Logic Error:

Question 2[2 marks]
Explain the difference between a logic error and a syntax error.
Question 3[3 marks]
In order to test her program, Zara is designing a test plan. She wants to use specific input values to complete three types of tests:
  • Normal/Valid Test
  • Boundary/Borderline/Extreme Test
  • Erroneous Test
Identify three input values that Zara could use in her test plan.
  • Valid/Normal Test Data: 

  • Boundary Test Data: 

  • Erroneous Test Data: 

Question 4[2 marks]
Identify two purposes of testing.
Question 5[2 marks]
Identify two ways, Zara could use to make her code easier to understand and maintain.
Question 6[5 marks]
Zara would like to create a function using her code. The function should be called checkVotingAge(). It should
  • take one parameter (the age of the user as an integer value),
  • output the messages as it currently does
  • return a Boolean value as to whether the user is allowed to vote or not.
Rewrite Zara’s code into a function.
unlock-access

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Refining Algorithms – Q&A

Question 1[3 marks]
Somjay has created the following program in his computer science lesson. The aim of this program is to generate and display five random “lucky” numbers every time this program is executed.

Here is his Python code:
print("Your five lucky numbers are...")

number = random.randint(1,100)
print(number)
number = random.randint(1,100)
print(number)
number = random.randint(1,100)
print(number)
number = random.randint(1,100)
print(number)
number = random.randint(1,100)
print(number)


Somjay has received feedback from his teacher who asked him to rewrite his code using iteration. Rewrite this code to take into consideration the feedback Somjay received from his teacher.
Question 2[3 marks]
Somjay is investigating a method to save all the numbers from a list into a text file, one number per line. He has typed the following code to do so:
list = [4, 6, 12, 98, 57, 32, 31, 6]
for i in range (0,len(list)):
       file = open("stats.txt","a")   # "a" -> append mode
       file.write(list[i])
       file.close()

His teacher believes this code is not as efficient as it could be, especially if the list of numbers was to increase. He believes this code could easily be refined to minimise the number of times the text file is opened and closed when the code is run. Rewrite this code to improve its efficiency based on this feedback.
Question 3[4 marks]

Somjay is now focusing on a piece of code that should ask the user to enter a star rating (a value between 0 and 5) and display an error message if the star rating is invalid.

Here is Somjay’s code:
rating = int(input("Enter a rating between 1 and 5"))

if rating < 0:
  print("This rating is to low...")
elif rating > 5:
  print("This rating is too high!")
else:
  print("This rating is valid!")

Somjay would like to refine this code so that the computer keeps asking the user to enter a rating until a valid rating is being entered. He believes this could be done using a while loop.

Refine this code to meet Somjay’s requirement.
Save / Share Answers as a link
unlock-access

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Discount Price Calculator – Q&A

Question 1[10 marks]
Oksana has created the following program in her computer science lesson. The aim of this program is to calculate the price after discount of a list of products bought by a customer.

Here is her Python code:
#Discount Price Calculator
def calculateDiscount(price,percentageDiscount):
  discount = price * percentageDiscount / 100
  discount = round(discount,2)
  return discount

#Main Program  
item = input("Enter the name of the item to buy? or X to quit!")
while item!="X":
  itemPrice=float(input("Enter a price for your item: £"))
  percentageDiscount = int(input("Enter a percentage discount for your item: %"))
  discount = calculateDiscount(itemPrice, percentageDiscount)
  newPrice = itemPrice - discount
  print("Discounter price: £" + str(newPrice))
  item = input("Enter the name of another item to buy? or X to quit!")


To help Oksana use the right terminology when annotating and explaining what her code does, you will need to answer the following 10 questions:

  1. What is the identifier of the subroutine defined in this code?
  2. Is this subroutine a procedure or a function? Why?
  3. How many parameters does this subroutine take?
  4. What programming construct is this subroutine based on: sequencing, selection or iteration?
  5. Which line of code will be executed first by the computer when you run this code?
  6. What programming construct is the main program based on: sequencing, selection or iteration?
  7. Can you identify three variables used in the main program?
  8. What is the data type of item?
  9. What is the data type of discount?
  10. On which line of code is string concatenation used?
1) 
2) 
3) 
4) 
5) 
6) 
7) 
8) 
9) 
10) 
Question 2[4 marks]
Without rewriting the above code, explain how Oksana could improve this code further to calculate and output the total discounted cost of all the items being bought by a customer?
Save / Share Answers as a link
unlock-access

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Mode Algorithm using a Hash Table

In this challenge we will compare two methods used to calculate the mode value of a list of numbers. In Maths, The mode is the value that appears most often in a set of data. For instance, considering the following list of numbers:

list = [14, 8, 25, 14, 32, 8, 8, 32, 7, 8]​

The mode is 8 as the value 8 appears 4 times. You will notice that it is easier to spot the mode of a list of numbers when the numbers are sorted. e.g.:
list = [7, 8, 8, 8, 8, 14, 14, 25, 32, 32]​

Method 1: Iterative Approach, using a sorted list

mode-iterative-apporach
Python Code:

Method 2: Using a hash table to store the frequency of each value

This method relies on the use of a hash table (a.k.a dictionary data strucutre) to store the frequency of each distinct value of the list.

mode-algorithm-using-hash-table
Python Code:

Your Task

Both of the above algorithm will return the mode of a list. However, on occasion, there could be more than one mode value: if there are multiple numbers that occur with equal frequency, and more times than the others in the set. For instance:

list = [7, 8, 8, 8, 8, 14, 14, 25, 30, 30, 30, 30, 32, 32]​

The above list is bimodal as it has two modes: 8 and 30.

Your task is to adapt both of the above algorithms to make sure they identify all the mode values from a given list of numbers.

Tagged with:

Job Scheduling Algorithms – Q&A

Question 1[20 marks]
One of the main purpose of the Operating System is to control the hardware and more specifically the CPU. The CPU performs all the jobs/processes requested by the different applications. A scheduler is a program of the Operating System that manages the amount of time that is allocated to each job that the CPU needs to process. To do so the scheduler keeps a list of all the jobs that need to be processed. This is called the job queue. The scheduler also uses a scheduling algorithm to determine in which order these jobs will be processed and the amount of processing time to allocate to each job.

The main job scheduling algorithms are:
  • FCFS: First Come First Served
  • Round Robin
  • Shortest Job First
  • Shortest Remaining Time First
  • Multilevel Feedback Queues
This question is based on the following job queue:
job-queue
For each of the following scheduling algorithms:
  1. Determine the order in which each job will be processed by the CPU (e.g. ABCD).
  2. Estimate the completion time for each job in the queue.
Current time: 01:00 (mm:ss) – Round Robin Time Slice: 1s
FCFS: ……………
    Job A: Completion time: 
    Job B: Completion time: 
    Job C: Completion time: 
    Job D: Completion time: 

Shortest Job First: ……………
    Job A: Completion time: 
    Job B: Completion time: 
    Job C: Completion time: 
    Job D: Completion time: 

Shortest Remaining Time First: ……………
    Job A: Completion time: 
    Job B: Completion time: 
    Job C: Completion time: 
    Job D: Completion time: 

Round Robin: ……………
    Job A: Completion time: 
    Job B: Completion time: 
    Job C: Completion time: 
    Job D: Completion time: 

Question 2[4 marks]
Some job scheduling algorithms can potentially lead to starvation? Out of the four algorithms listed in question 1, what algorithms can potentially lead to starvation? Explain what would cause this?
Save / Share Answers as a link
unlock-access

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Disk Scheduling Algorithms

A hard drive is a magnetic storage device consisting of several disks (a.k.a. platters) where data is stored.

hard-disk-platters-tracks-sectors

Each disk is divided into many concentric circular tracks. Each track contains several sectors where data is stored. When the Operating System stores a file on a hard drive, this file is split into several clusters. Each cluster will be stored across a few sectors. The typical size of a cluster on a Windows computer is 4KB.

When loading a file into memory, it is necessary to access all the sectors used by this file. This involves physical movement of the Hard Drive arm used to position the Read/Write head on the right track. Once the head is positioned on the right track, the sectors of this track can easily be reached as the disk is constantly rotating. Moving the arm from one track to another takes time which increases the overall seek time: the time taken to locate a specific piece of data stored on a hard disk.

Disk scheduling

Disk scheduling is done by the operating system to schedule Read/Write requests (a.k.a I/O requests) arriving for the disk.

When a file is loaded into memory, several sectors (and tracks) will need to be accessed. The operating system can use different disk scheduling algorithms to do so. In this post we will compare four main algorithms:

  • The FCFS Disk Scheduling Algorithm (First Come First Serve)
  • The SCAN Disk Scheduling Algorithm
  • The LOOK Disk Scheduling Algorithm
  • The SSTF Disk Scheduling Algorithm (Shortest Seek Time First)

FCFS Disk Scheduling Algorithm

Let’s consider a disk consisting of 100 concentric tracks (0-99) and let’s assume the Operating System needs to access sectors on the following tracks: [43,52,24,65,70,48,16,61]. And let’s assume the head is, to start with at track 20.

With a First Come First Served scheduling algorithm, the tracks will be accessed in the order they were requested. So the read/write head will be moving from its current position to track 43, then track 52 then track 24 and so on…

Looking at the above pattern we can estimate the seek time of this approach:

Seek Time = (Number of tracks crossed) x (Time to cross one track)

fcfs-disk-scheduling

So in this case, we can calculate the number of tracks crossed as follows:

Number of tracks crossed = |20-43| + |43-52| + |52-24| + |24-65| + |65-70| + |70-48| + |48-16| + |16-61| = 205

Seek Time = 205 x (Time to cross one track)

SCAN Disk Scheduling Algorithm

With a SCAN Disk Scheduling algorithm, the disk arm will not access the tracks in the order they were requested. Instead it will move in one direction and service the requests coming in its path. After reaching the end of disk (e.g. track 99), it will reverse its direction and again services the request arriving in its path. Due to the movement of the arm going all the way up and down the number of tracks, the algorithm is also known as elevator algorithm. The aim of this approach is to reduce the average seek time when accessing a list of sectors.
SCAN-Disk-Scheduling-Algorithm
In this case, using the same example as above: Starting Position: Track 20, list of tracks to access [43,52,24,65,70,48,16,61] we can calculate the number of tracks crossed as follows:

Number of tracks crossed = |20-99| + |99-16| = 162

Seek Time = 162 x (Time to cross one track)

On average this algorithm will reduce the overall seek time (compared to a FCFS Disk Scheduling algorithm.

LOOK Disk Scheduling Algorithm

The LOOK disk scheduling algorithm is an improved version of the SCAN disk scheduling algorithm. In this algorithm, instead of reaching the last track (e.g. track 99) before changing direction, this algorithms changes direction when it reaches highest (or lowest) track from the list of track to access.
Look-Disk-Scheduling-Algorithm
In this case, using the same example as above: Starting Position: Track 20, list of tracks to access [43,52,24,65,70,48,16,61] we can calculate the number of tracks crossed as follows:

Number of tracks crossed = |20-70| + |70-16| = 104

Seek Time = 104 x (Time to cross one track)

On average this algorithm will reduce the overall seek time (compared to both a FCFS Disk Scheduling algorithm and a SCAN Disk Scheduling algorithm).

SSTF Disk Scheduling Algorithm

With the Shortest Seek Time First algorithm, we once again do not necessary process the requests in order they arrived. Instead we all always process the request which is the closest to the current position (track number) of the head.
SSTF-Disk-Scheduling-Algorithm
In this case, using the same example as above: Starting Position: Track 20, list of tracks to access [43,52,24,65,70,48,16,61] we can calculate the number of tracks crossed as follows:

Number of tracks crossed = |20-24| + |24-16| + |16-70| = 66

Seek Time = 66 x (Time to cross one track)

On average this algorithm will reduce the overall seek time (compared to all the other 3 algorithms we investigated in this blog post).

You Task

Estimate the Seek Time for all 4 scheduling algorithms for the given track lists:

Starting Position Track List FCFS Disk Scheduling
Seek Time
SCAN Disk Scheduling
Seek Time
LOOK Disk Scheduling
Seek Time
SSTF Disk Scheduling
Seek Time
#1 50 [24,60,30,8,52]
#2 80 [70,60,10,20,40,30]
#3 40 [32,48,64,12,16,8,90]