Rabin Karp and Boyer Moore implemented for byte data

This is a another assignment from the University. I’m posting this here mostly because there’s not much examples or proofs of these methods in the internet that’s understandable(I have to agree that the Boyer Moore explaination in the report must need some work to be done by the reader, but that’s because we were limited in page count for explainations).

This implementation features string matching on any data given, its alphabet size is 256(unlike other implementations found on the internet).

Download PDF

Download Source

Advertisements

NewMalloc – Assignment

This is an assignment done for the OS module at the university. The assignment was to make a replacement for malloc/free library functions, by using an array. Since the problem statement did not ask for brk support, there is no support for brk system call(may be in the future). This package contains 3 testers and the NewMalloc routines. The three testers are,

1. My infamous AVL tree benchmark – Adding, removing and finding elements from AVL tree using malloc for all memory it requires.

Glib Default malloc

ADDING 10000 strings
ADD 14706us
AVG LOOKUP 0.653400us
REMOVE 0.5 4711us
ADD 0.5 6558us

NewMalloc

ADDING 10000 strings
ADD 17638us
AVG LOOKUP 1.217400us
REMOVE 0.5 7596us
ADD 0.5 8927us

Tested on Ubuntu 11.10

2. malloctest – A malloc tester that makes random allocations and write to them and free them at random.

3. simpletest – A simple test, includes basic tests for malloc and free.

Download

How to build:  ‘make’, it’ll make all three tests. This project should build on any platform that supports a *Standard* C compiler, including Windows if and only if you use a standard C compiler.

UPDATE: fixed function names to xmalloc and xfree, due to crashing on function redirection.