Tutorial by Examples

First simple Example: You have a ticket automat which gives exchange in coins with values 1, 2, 5, 10 and 20. The dispension of the exchange can be seen as a series of coin drops until the right value is dispensed. We say a dispension is optimal when its coin count is minimal for its value. Let M ...

We have a set of jobs J={a,b,c,d,e,f,g}. Let j in J be a job than its start at sj and ends at fj. Two jobs are compatible if they don't overlap. A picture as example: The goal is to find the maximum subset of mutually compatible jobs. There are several greedy approaches for this problem: Earli...

There are numerous problems minimizing lateness, here we have a single resource which can only process one job at a time. Job j requires tj units of processing time and is due at time dj. if j starts at time sj it will finish at time fj=sj+tj. We define lateness L=max{0,fj-dh} for all j. The goal is...

The caching problem arises from the limitation of finite space. Lets assume our cache C has k pages. Now we want to process a sequence of m item requests which must have been placed in the cache before they are processed.Of course if m<=k then we just put all elements in the cache and it will wo...