Defragmentation Algorithm

Posted on July 6, 2017 by Administrator Posted in Computer Science, Computing Concepts, Python - Advanced, Python Challenges

File Allocation Table (FAT System)

A file allocation table (FAT) is a table that an operating system maintains on a hard disk that provides a map of the clusters (the basic units of logical storage on a hard disk) that a file has been stored in. When you write a new file to a hard disk, the file is stored in one or more clusters that are not necessarily next to each other; they may be rather widely scattered over the disk. A typical cluster size is 2,048 bytes, 4,096 bytes, or 8,192 bytes.

Defragmentation?

When a file is accessed, the Operating System uses the FAT table to identify all the clusters that need to be accessed to retrieve the content of the file. The more scattered the clusters are the longer it will take for the Operating System and Hard drive to retrieve the content of the file. This is why, if you hard drive is based on a FAT systems, it is recommended to use a defragmentation utility to try to reorganise how all the files are stored by trying to move the content of clusters of a single file into consecutive clusters. Defragmenting your hard drive once every six months should hence have a positive impact on the performance of your computer.

On this graphic, each square represents a cluster of the hard drive and each colour represents a file.

Did you know?

With the introduction of more powerful computers and operating systems, as well as the development of more complex file systems for them, FAT is no longer the default file system for usage on Microsoft Windows computers.

FAT file systems are still commonly found on floppy disks, flash and other solid-state memory cards and modules (including USB flash drives), as well as many portable and embedded devices such as digital cameras.

Defragmentation Algorithm

The File Allocation Table is a linked list where each entry contains the cluster number, the file name and a pointer to identify the next cluster used by the file.

Cluster #	File Name	Pointer
0	File A	1
1	File A	2
2	File A	5
3	File B	4
4	File B	x
5	File A	6
6	File A	x
…	…	…

Let’s check this Python trinket to see how the File Allocation Table was implemented using a Python list of lists.

Challenge 1: Hard Drive Stats

Assuming that the standard cluster size is 4KB, complete the displayStats() procedure to:

Calculate and display the total size of the hard drive (in KB).
Calculate and display the total used space of the hard drive (in KB).
Calculate and display the total free space of the hard drive (in KB).
Calculate and display the total used space of the hard drive as a percentage of the total disk space.

Challenge 2: Defragmentation Algorithm

Your challenge consists of completing this code by writing the code for defragmentation() procedure that will group all the clusters of a file into consecutive clusters.

Tagged with: array, List

Catch Me If You Can

Posted on July 4, 2017 by Administrator Posted in Block Programming, Computer Science, Scratch

In this challenge we will create a three-player game using Scratch.

One player (the yellow ball) will be chased by two other players the red player and the blue player.

The red player will use the arrow keys to control their sprite.
The blue player will use the “WASD” keys to control their sprite.
The yellow player will use the mouse pointer to control their sprite.

The game will use two score variables one for the red player, one for the blue player. At the start of the game both scores will be initialized to 0. Every time a player collides with the ball their score will be incremented by 1. The ball will then be randomly moved on screen by resetting its x and y coordinates.

Scracth Code

To implement this game you will have to create three sprites and use the code provided below:

Red SpriteBlue SpriteYellow Sprite

The Red Sprite, called Red Dot, will be controlled using the arrow keys:

The Blue Sprite, called Blue Dot, will be controlled using the WASD keys:

The Yellow Sprite, called the Ball, will be controlled using the mouse pointer. it will also have a collision detection algorithm to detect if the ball has been caught by either the red sprite or the blue sprite.

Extension Task: Adding Walls/Platforms

To make this game more interesting we will add walls/obstacles that the red player, the blue player and the yellow ball will have to avoid when moving around.

Step 1: The StageRed SpriteBlue SpriteYellow Ball

Using a plain colour create a background for the stage by adding walls:

Adapt the script of your red sprite so that it cannot go through the walls:

Adapt the script of your yellow sprite so that it cannot go through the walls:

Tagged with: Block Programming, Scratch

Recursive Tree Challenge

Posted on June 30, 2017 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges

Look at the code provided below use to draw a tree using a recursive function.

Recursive Function

A recursive function is an alternative to using iteration. A function is a recursive function if:

It includes a call to itself,
It has a stopping condition to stop the recursion.

In the code given below the drawTree() function is a recursive function because:

It includes a call to itself (on line 10 and also on line 13)
It has a stopping condition on line 7 (it will stop recursing when level reaches 0)

Your Challenge

Tweak the code provided above to create different versions of recursive trees. You could investigate having three branches per node instead of two or using some random attributes so that the tree becomes less symmetrical.

Mixed Numbers Challenge

Posted on June 27, 2017 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

Before completing this challenge we need to revise some Maths concepts.

Fraction = numerator / denominator

In Maths a fraction consists of two numbers: a numerator and a denominator.

What is an improper fraction?

An improper fraction is a fraction where the numerator is greater than or equal to the denominator.

For instance:
⁷⁄₄, ¹²⁄₁₀, ²¹⁄₃ are all improper fractions.

What is a proper fraction?

A proper fraction is a fraction where the numerator is lower than to the denominator.

For instance:
⁷⁄₉, ¹²⁄₂₁, ³⁄₄ are all proper fractions.

What is a mixed number?

A mixed number is a number consisting of a whole number and a proper fraction.

For instance:
3¹⁄₂, 1³⁄₁₀, 21³⁄₄ are all mixed numbers.

Converting improper fractions into mixed numbers

We can easily convert an improper fraction into a mixed number by calculating the quotient and the remainder from the improper fraction.

Mixed number = Quotient ^Remainder⁄_Denominator

For instance: Let’s convert ¹¹⁄₄ into a mixed number

Step 1: Quotient (Whole Division): 11 DIV 4 = 2
Step 2: Remainder: 11 MOD 4 = 3

¹¹⁄₄ = 2 ³⁄₄

Quotient & Remainder in Python?

In Python you can use the // operator to calculate the quotient of a fraction and the % operator to calculate the remainder of a fraction.

For instance:

quotient = 11 // 4
remainder = 11 % 4

Python Challenge #1

Complete the code given below to convert an improper fraction into a mixed number by:

Check that the user has entered a numerator and a denominator for an improper fraction. (The numerator should be greater or equal to the denominator).
Calculate and display the mixed number corresponding to the given fraction.

Python Challenge #2

Create a Python script to convert a mixed number into an improper fraction.

Solution...

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

Text Alignment Challenge

Posted on June 26, 2017 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

This challenge focuses on the use of string manipulation techniques in order to format the output when printing text on the screen.

Step 1: Reverse Engineering

First look at the code provided above and use this code to answer the following questions:

Which line of code will be executed first by the computer when you run this code?
What data structure is used to store a selection of European capital cities?
What is the identifier of the procedure defined in this code?
How many parameters this procedure takes?
What programming construct is this procedure based on? Sequencing, Selection or Iteration?
What data will be stored in the itemLength variable?
What is the data type for this value: String, Boolean, Integer or Float?
What data will be stored in the spaces variable?
What is the data type for this value: String, Boolean, Integer or Float?
String concatenation is the act of joining two strings together (using the + sign). Which line of code is using string concatenation is this program?

Step 2: Complete the Code

Using a similar approach to the code given to implement the leftAlign procedure create two more procedures as follows:

rightAlign to display all the European capitals aligned to the right.
centerAlign to display all the European capitals centred on screen.

Step 3: Extension Task Task

-lorem ipsum.txt –
Write a Python program to read and display the content of the above text file:

Align to the left,
Align to the right,
Centred,
Justified,
Using Auto-hyphenation.

Solution...

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

Tagged with: String Manipulation

3D Printing – Name Badge

Posted on June 23, 2017 by Administrator Posted in Block Programming, Computer Science, Computing Concepts

One application of programming is to control 3D printers to create 3D models. Using a Block programming language you can create your own 3D models and export them in a format recognised by 3D Printers. In this blog you will create a 3D model of your name or initials using http://www.beetleblocks.com/.

We have To get you started we are showing the code that would be used to create two leetes: Letter C and letter A.

You will need to use a similar approach to create a 3D model of your initials or of your full name.

Letter C

Letter A

Students’s Code

Tagged with: 3D Printing, Coordinates

3D Printing: Bracelets

Posted on June 23, 2017 by Administrator Posted in Block Programming, Computer Science, Computing Concepts

One application of programming is to control 3D printers to create 3D models. Using a Block programming language you can create your own 3D models and export them in a format recognised by 3D Printers. In this blog we will create some bracelets using http://www.beetleblocks.com/.

We have made 2 Bracelets that you can easily reproduced and tweak to create your own bracelet.

Notice how both Bracelets use iteration (repeat block) which make the code very short and effective to produce a complex 3D model.

Bracelet #1

Bracelet #2

Tagged with: 3D Printing, Coordinates

Conway’s Game of Life

Posted on June 21, 2017 by Administrator Posted in Computer Science, Python - Advanced, Python Challenges

The “game” is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves, or, for advanced “players”, by creating patterns with particular properties.

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead, or “populated” or “unpopulated”. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overpopulation.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

You can read more about Conway’s Game of Life on wikipedia.

Python Implementation

Our Python implementation of Conway’s Game of Life lets you try different starting configurations as follows:

Option 1: Random configuration using a randomly generated 15×15 grid.
Option 2: The Glider Configuration.
Option 3: The Toad Configuration.
Option 4: The Beacon Configuration.
Option 5: The Pulsar configuration.

Your Challenge

Compete the code provided in the trinket above to add some additional configurations such as:

The Blinker
The Pentadecathlon
The Lightweight Spaceship

3D Staircase Challenge

Posted on June 21, 2017 by Administrator Posted in Block Programming, Computer Science, Computing Concepts

In this challenge you will use http://www.beetleblocks.com/ to create some 3D models to represent different types of staircases. I will use iteration (for loops) to make your code more effective and investigate the use of (x,y,z) coordinates to create your models.

Another approach for this challenge is to complete the following tasksheet to match the code with the corresponding 3D model: