James PK's Technical Journal

"Understanding Algorithms and Data Structures" by Brunskill and Turner was on the reading list of one the units on my CS course. It has some interesting chapters on searching. Although fairly basic in the scheme of things I found these basic sorting type fun to play around with.

Brunskill & Turner, pose some interesting questions along the way, such as how many comparisons are there?, how many swaps occur? , etc. They add a couple of interesting tweaks to get some performance lift. This is my rough take of the functions for those three search types.

Selection

void selection_sort(int numbers [],int size)
{
	int comparisions=0;
	int swap=0;
	for (int i=1;i < size;i++)
	{
		int i_min=i;
		for (int j=i+1; j < size;j++)
		{	
			++comparisions;
   			if (numbers[j] < numbers[i_min])
    				i_min =j;
		}
		if (i_min != i)
		{
			int temp=numbers[i_min];
			numbers[i_min]=numbers[i];
			numbers[i]=temp;	
			++swap;
		}
	}
	#cout comparisions & swaps
}

Bubble

void bubble_sort(int numbers [],int size)
{
	int comparisions=0;
	int swap=0;
	for (int i=0;i < size;i++)
		for (int j=0; j< size; j++)
		{
			++comparisions;
			if (numbers[j] > numbers[j+1])
			{	int tmp=numbers[j];
				numbers[j]=numbers[j+1];
				numbers[j+1] = tmp;
				++swap;
			}
		}
	#cout comparisions & swaps
}

Insertion

void insertion_sort(int numbers [],int size)
{
	int comparisons=0;
	int swap=0;
	for (int i=1;i < size;i++)
	{
		int pos=i;
		int val=numbers[i];
		while ( pos >0 && val < numbers[pos-1])
		{	numbers[pos]= numbers[pos-1];
			pos=pos-1;
			comparisons++;
		}
		numbers[pos]=val;
		swap++;
	}
	#cout comparisions & swaps
}

Results - Running the above, on a various sizes of arrays with random numbers, with the `time` command, unsurprising shows the insertion sort (it does *far* less comparisons than the other two approaches) as the winner.

Comments
1. I used an array to store the numbers, using a vector might have been an alternative.
2. Using the time command gives a *very* rough indication of performance - could do alot better by putting a timer around the function call and not the programme itself.
3. The arrays all used different sets random numbers - obliviously they would need to be the same across all three tests to have strong validity.

posted at: 00:00 | path: /cpp | permanent link to this entry

---

I recently encrypted a portable hard drive (a Verbatium "Store'n'Go" 500GB) for backups. I decided to use LUKS (Linux Unified Key Setup-on-disk-format), to encrypt an entire partition.

I found a couple of good references to Encrypt hard drives: Encrypting-your-usb-pen-drive-with-luks and Encrypting-USB-Sticks.

I created two partitions but only encrypted one of them.

NB The real device names have been modified (in case a copy & paste results has unexpected consequences).

Here are the steps I followed on Debian Wheezy.

1. Fill hard drive with random data (see above references).
2. Formating the hard drive with fdisk. I created two partitions on the dive using fdisk (making sure the device name is right).
   

   Device Boot      Start         End      Blocks   Id  System
   /dev/xyz1            2048   411043839   205520896   83  Linux
   /dev/xyz2       411043840   976773167   282864664   83  Linux
   

3. Made the file systems for the normal partition.
   

   root@sal:~# mkfs -t ext3 -L verbatim_0a -v /dev/xyz1 

4. Run cryptsetup, with the options, -y (verify passsphrase twice), (-h specify the passhrase hash), -v (verbose) -c (encryption method) -s (key length)
   

   root@sal:~# cryptsetup -yvh sha256 -c aes-xts-plain -s 256 luksFormat /dev/xyz2 

5. Open the device

   root@hal:~# cryptsetup luksOpen /dev/xyz2 verbatim_1b #note last argument is not a path
   Enter passphrase for /dev/xyz2: 
   

6. Make the file system for the encrypted partition
   

   root@sal:~# mkfs.ext3 /dev/mapper/verbatim_1b

7. Mount the device

root@hal:~# mount /dev/mapper/verbatim_1b /media/verbatim_1b

8. Copy/Rsync data - with the drive open and mounted, it should now be possible to copy/rsync data.
9. Unmount & close

root@hal:~# umount /media/verbatim_1b
root@hal:~# cryptsetup luksClose verbatim_1b

I found the status option handy;

root@hal:~# cryptsetup -v status verbatim_1b

See also;

man cryptsetup

posted at: 00:00 | path: /cryptography | permanent link to this entry

---

"Understanding Algorithms and Data Structures" by Brunskill and Turner was on the reading list of one the units on my CS course. It has some interesting exercises. Page 21 (in the chapter "Necessary Mathematics") has an exercise on sketching and comparing graphs for various mathematical functions. I thought I'd have a go at it with Python and Matplotlib (a Python library for graphs).

Using a combination of range and map (which applies a function to every item of an iterable), keeps the code fairly succinct:

---

#!/usr/bin/env python
import matplotlib.pyplot as plt 
import math_functions as mf 

functions=[mf.f,mf.g,mf.h,mf.j,mf.m,mf.n]

figure=plt.figure()
ax=figure.add_subplot(111) 

for i in functions:
 plt.plot(range(5), map(i,range(1,6)), 'o-', label=i.__name__)
 print i.__name__,map(i,range(1,6)) 

plt.legend(loc='upper left')
plt.ylabel('Y')
plt.xlabel('X')
ax.set_title("Excercises 2.1")
plt.show()

---

Image output:

posted at: 00:00 | path: /python | permanent link to this entry

---