Algorithm homework

I finally had the time to finish this homework as well.

 

Linear search

LinearSearch(x,items) searches the items for the given item . The algorithm starts at the first position in items and iterates over each item while comparing with x. If the one item equals the item x, the algorithm the position of this item, otherwise -1.

  1. Init index variable to zero(0)
  2. Iterate over items and compare the i-th element of items with x
  3. increase the index variable by one and start over with 2
  4. if the i-th item and x are equal return the i otherwise -1

Heapsort

Heapsort(items) is a function to sort a collection of items by using a tree datastructure. The passed items are transformed in a tree-based datastructure with a defined order. Each tree-node is either smaller or equal to his parent node. Next we create a sorted region by removing the largest element in the tree(the root) and inserting this into a array. By repeating this step the sorted array is created and henceforth the tree is shrinked.

  1. create a binary tree from the given array
  2. iterate over the tree and move the root of the tree to a array, the sorted array
  3. update the remaining tree to create a new tree with the root as the largest element
  4. by repeating step you create a sorted array
  5. as soon as the heap is empty we are finished

SelectionSort

SelectionSort(items) is a in-place sort algorithm, which means the items are not moved to different arrays or other structures. It finds the smallest element in the items collection and swaps it with a specified different element.

  1. finding the smallest element in the array
    1. find minimum from start to end
  2. swap the found element with the first element
  3. find the next smallest element in the array
    1. not all elements has to be concerned because the smallest element is on position 0 already so we can start from 1
  4. swap the second smallest element with the second element
  5. repeat step 3 and 4 until we are at the end of the list

In terms of costs this algorithm has a runtime of O(n*n) which makes it inefficient for large lists.

Abstract and references

abstract

Modern real-time systems like, sensor driven home automation systems, automotiv board electronic and robotic application need to handle tasks and processes in a particular amount of time. It is important to react on periodic as well as on aperiodic tasks. For instance, handling the break system in a car is more important than handling the climatic control system. This work presents the current state of the art, how \rtos{s} approach these different problems. Furthermore different scheduling algorithm and their challenges are presented.

references

These reference are still in progress. It’s my first glance and there is still work to do. Currently I am using the  book from Audsley very intensivly.

 

  1. @inproceedings{audsley1991real,

title={Real-time scheduling: the deadline-monotonic approach},
author={Audsley, Neil C and Burns, Alan and Richardson, Mike F and Wellings, Andy J},
booktitle={in Proc. IEEE Workshop on Real-Time Operating Systems and Software},
year={1991},
organization={Citeseer}
}

cited by 585 others

2. @article{mohammadi2005scheduling,
title={Scheduling algorithms for real-time systems},
author={Mohammadi, Arezou and Akl, Selim G},
journal={School of Computing, Queens University},
year={2005},
publisher={Citeseer}
}

cited by 51 others

3. @article{balarin1998scheduling,
title={Scheduling for embedded real-time systems},
author={Balarin, Felice and Lavagno, Luciano and Murthy, Praveen and Sangiovanni-Vincentelli, Alberto},
journal={IEEE Design \& Test of Computers},
number={1},
pages={71–82},
year={1998},
publisher={IEEE}
}

cited by 137 others

4. @inproceedings{inam2011support,
title={Support for hierarchical scheduling in freertos},
author={Inam, Rafia and M{\”a}ki-Turja, Jukka and Sj{\”o}din, Mikael and Ashjaei, Seyed MH and Afshar, Sara},
booktitle={Emerging Technologies \& Factory Automation (ETFA), 2011 IEEE 16th Conference on},
pages={1–10},
year={2011},
organization={IEEE}
}

cited by 37  others

 

I know these are not the five requested references but they are most important for  me I guess.

Homework – Part 5

  • We live in the era of Big Data with storage and transmission capacity measured not just in terabytes but in petabytes (where peta- denotes a quadrillion or a thousand trillion). Data collection is constant and even insidious, with every click and every “like” stored somewhere for something. This book reminds us, that data is anything but “raw” that we shouldn’t think of data as a natural resource but as a cultural one, that needs to be generated protected and interpreted. The book’s essays describe eight episodes in the history of data from the predigital to the digital. Together, they address such issues as the ways that different kinds of data and different domains of inquiry, are mutually defining how data are variously “cooked” in the processes of their collection and use and conflicts, over what can or can’t be “reduced” to data. Contributors discuss the intellectual history of data, as a concept describe early financial modeling and some unusual sources for astronomical data; discover the prehistory of the database in newspaper clippings and index cards and consider contemporary “dataveillance” of our online habits as well as the complexity of scientific data curation.
  • During succession, ecosystem development occurs but in the long term absence of catastrophic disturbance a decline phase eventually follows. We studied six long term chronosequences in Australia, Sweden, Alaska, Hawaii and New Zealand for each the decline phase was associated with a reduction in tree basal area and an increase in the substrate nitrogen to phosphorus ratio, indicating increasing phosphorus limitation over time. These changes were often associated with reductions in litter decomposition rates, phosphorus release from litter and biomass and activity of decomposer microbes. Our findings suggest that the maximal biomass phase reached during succession cannot be maintained in the long term absence of major disturbance and that similar patterns of decline occur in forested ecosystems spanning the tropical temperate and boreal zones.
  • Facebook’s Graph API, is an API for accessing objects and connections in Facebook’s social graph. To give some idea of the enormity of the social graph underlying Facebook, it was recently announced that Facebook has 901 million users and the social graph consists of many types beyond just users. Until recently, the Graph API provided data to applications in only a JSON format. In 2011 an effort was undertaken to provide the same data in a semantically enriched RDF format containing Linked Data URIs. This was achieved, by implementing a flexible and robust translation of the JSON output to a Turtle output. This paper describes the associated design decisions, the resulting Linked Data for objects in the social graph and known issues.

Homework – Part 3

Warp drive research – a breakthrough

Interstellar travel is one of humanity biggest goals. To reach this goal Zefram Cochrane invented the warp-drive engine in 2063. But this is just a science-fiction dream as every Star Trek fan knew. But this idea is still maintained by very ambitious scientist on earth, with Harold ‘Sonny’ White at Johnson Space Center leading the way. He designed a experiment to distort the  spacetime around a obstacle in space. This is different from other ideas, because he does not want to accelerate the obstacle but bend the space time around it. This allows vehicles to reach planets in millions of light-years distance to be reached in a some weeks. Upon his idea a lot of enthusiasts have founded several organizations to support White with his idea. These organizations are driven by the idea to reach far planets that have been discovered over the past years. Not enough, theses planets considered to be habitable and may have potential of rudimentary life-forms.

One well-known problem that exists is the fact that there is no spacecraft able of traveling these distances. That’s because current technology is not capable of  ‘driving’  needed speed to reach planets in a fair amount of time. Despite these fact, even if there is a technology, there is a need for the fuel to power the spaceship. Traveling such distance would result in a huge amount of fuel needed. This huge amount of fuel would also result in a way heavier spaceship. So this is kind of paradoxon. Traveling far distance and high speed means more fuel, but more fuel means more weight to move.  So there is a need for different travel-engine. The most promising technology is the use of nuclear fusion energy. But, nuclear fusion is very complex process that is not even completely explored in reactors on earth. Despite this problem, traveling at high speed encounters other problems as well, like space dust that hits the spaceship with a high velocity or deceleration.

The need of space travel is necessary  due to the fact that in several years earth is just before extinction because of nuclear wars, pandemic, interstellar catastrophes etc. The only nearby candidate for this operation is mars, but it takes several hundred of years of climate engineering.

Homework – Part 2

Assignment 1: Done

Assignment 2:

1. urban Internet-of-things – a proof of concept for the smart city vision

2. random string testing – black-box test generation

assignment 3:

Scheduling Algorithm in Real-Time-Operating Systems e.g. FreeRTOS

Comparison of popular scheduling algorithm and a detailed view on the currently used and most optimized algorithm used in real time operating systems e.g. FreeRTOS.

Writing process for my bachelor thesis

When writing my bachelor thesis there was a major lack of how to schedule my time. So I actually decided to write something when I found some time. Most problem I want to address is the fact that there was no(no) experience how to write a scientific document.

What did i like about writing the thesis?:

Actually about the writing I didn’t liked it at all. I only loved the topic because I am totally into operating systems and that was the only thread I was able to grab on while writing. I loved to dig into the topic but I hated to write about it an super scientific manor.

what were the DIFFICULTIES?:

Most difficult part was to find the way to start the thesis. Even more complicated was to write it in a correct scientific way. This is meant regarding the citation process, the depth of the topic and the golden thread for the thesis.

do you like the result?:

I don’t like the textual result at all. I love the implementation and the result of the design but the the thesis is not all is not a good result for my perspective.

It’s written in a too casual manor and not scientific enough and this was also a big critics point of the professor who guided me a lot.

Quick abstract for bachelor thesis

The following text represents a quick abstract of what I have done in my bachelor thesis.


Developing a mini-operating system for a arm926 processor

Motivation and goals

In modern mobile phones, embedded systems and daily used devices mini processors are built in. These processors are responsible for all the hard/software communication with the device. Having a fine grained control over these resources is very important for modern systems. With these thesis I present a small approach towards a mini operating systems for these kind of processors and environments. The goal is to show that it is possible to implement a operating-like system on these small devices with limited computation power as well as other limited resources like memory etc.

 

introduction to state-of-the-art processors

In common devices like mobile phones, coffee-brewer, washer etc. a lot of different processors are assembled. Shortly I want to show the most commonly used ones.

Version Example Usage
ARMv4 ARM8 Gameboy Advanced, Nintendo DS
ARMv5 ARM926 Palm Tungsten
ARMv8 ARM-Cortex-A50 Mobilephones,Tablets

This is just a short extract of the commonly used ones.

Difference between risc and cisc processors

Out there are two different big processor architectures produces by the big processor manufacturer. The difference between those two architectures is how the processors process the commands. The RISC(Reduced Instruction Set Computer) has less complex instruction compared to the CISC(Complex Instruction Set Computer). Less instructions means the processor can be designed in a very efficient way. This is important if one think of the field of application. In embedded systems there is only less room for the hardware, so an efficient design is on of the most important facts.

design

When thinking of implementing a operating system there is one major fact that has to face with high attention. The design is the most important part in an operating system. In this part I want to share the approach how the mini-operating system is designed.

First of all there is the kernel. The kernel is responsible for all the communication either with the connected hardware or the inter-process communication with all the resources like memory and task management. The kernel is piece of software sitting directly behind the hardware abstraction layer. Is the system booted the kernel takes control over everything.

Controlled by the kernel there is the scheduler. This piece of software is responsible for the task/process management within the operating system. The scheduler is implemented as a simple round robin scheduler. This one is commonly used by simple operating systems and is totally feasible for this approach.

Followed by the kernel there are devices like output and input devices(keyboard, display etc.)

detailed design

All the booting process and all the low level processing was done with assembler. This is obviously though because assembler is a very efficient and close-to-the-hardware language. You can access regions of memory directly, enter specific operating modes without using complex workarounds. After the system is booted the kernel takes control and prepares all the pre-configured tasks for execution. These task are very rudimentary tasks compared to modern tasks. This designed was chosen due to the lack of time at the end.

The scheduler now takes control and schedules all the task in an round robin procedure. Each task has a predetermined amount of time to do his work. If not finished in this given time the next task is on the turn.

The memory management unfortunately was a process that was faced too less time and I missed to implement everything. So the mini operating system for this thesis has a fixed amount of memory and all tasks also have fixed amounts of memory, stack memory as well as heap memory.

conclusion

Writing an operating system is a very complex task. Writing an operating system for modern and old embedded devices is an even more complicated task. New problems arise like memory management issues, limited processing capacities, scheduling issues and more. But it could be shown that it is possible to implement a small extract of an operating system with the smallest capabilities. It has to be said that still work has to be done to built a full and flexible operating system for embedded systems.