Datenstrukturen

und Algorithmen

Introduction

Jens Krüger
 Lecture
Prof. Dr. Jens Krüger

Gebäude LE, Raum 304

Tel.: +49 203 379 2687
Email: [Link]@[Link]
Web: [Link]

Exercises
Mohamed Abdelmagied and Torben Karl

LE 120 & LC 137

2
 Moodle ID: 38796
Password: Knibbelbilder

• To login use an email address you check frequently

• Slides and exercises will be provided via moodle

• Important information about the course is posted on moodle

3
 COVIDAG
H P C High
Performance
Computing
Center of Visual Data Analysis and Computer Graphics

Winter Summer
Grundlegende Programmiertechniken Grundlegende Programmiertechniken

Datenstrukturen und Algorithmen

Scienti c Visualization

Advanced Image Synthesis Computer Graphics

Seminars, Bachelor and Master Projects

fi
Seminar: How to Deliver an Engaging Computer Science Speech
Registration & Kick-off Meeting: Do. 06 April, 12:00, LF 125 5
Robert Sedgewick, Kevin Wayne
Algorithms
Pearson, [Link]

Ottmann, Thomas, Widmayer, Peter

Algorithmen und Datenstrukturen
Spektrum Theoretische Informatik

Charles E. Leiserson, Clifford Stein,

Thomas H. Cormen, und Ronald L. Rivest
Algorithmen - Eine Einführung
Oldenbourg Verlag
6
7
Take Notes!

7
Take Notes!
Slides are not a script!

7
[Link]
8
[…] Fried found a signi cant, negative relationship
between in-class laptop use and course grade.
Follow-up correlational analysis also revealed that
higher levels of laptop use were associated with
lower student-reported levels of attention, lecture
clarity, and understanding of the course material.

Fried, C. B. (2008). In-class laptop use and its effects

on student learning. Computers & Education, 50(3),
906–914. 9
fi
10
 Ask Questions
here in the lecture, in moodle, with DuckDuckGo/Google/Bing ...,

10
11
Study in teams!

11
12
Exercise

12
 Exercises
Starting: April 11th

Wednesday 10-12 LE 120

Wednesday 16-18 LE 120
Thursday 10-12 LE 120
Thursday 16-18 LE 120
Friday 12-14 LC 137
Friday 14-16 LE 120
13
14
Datenstrukturen
und Algorithmen

Introduction

Jens Krüger
16
17
17
 Topics
topic data structures and algorithms

data types stack, queue, bag, union- nd, priority queue

sorting quicksort, mergesort, heapsort, radix sorts

searching BST, red-black BST, hash table

graphs BFS, DFS, Prim, Kruskal, Dijkstra

strings KMP, regular expressions, tries, data compression

advanced B-tree, k-d tree, suf x array, max ow

18
fi
fi
fl
Why participate in this class?

19
Why participate in this class?
r s e
c o u
t h e r ! “
e e d e l o
u n a c h
” Yo u B
r y o
f o
19
• Internet. Web search, packet routing, distributed le sharing, …

• Biology. Human genome project, protein folding, …

• Computers. Circuit layout, le system, compilers, …

• Computer graphics. Movies, video games, virtual reality, …

• Security. Cell phones, e-commerce, voting machines, …

• Multimedia. MP3, JPG, DivX, HDTV, face recognition, …

• Social networks. Recommendations, news feeds, advertisements, …

• Physics. N-body simulation, particle collision simulation, …

20
fi
fi
”handicraft work“

21
 Motivation

Why, Programming (for Engineers)? 22

 Motivation

Why, Programming (for Engineers)? 22

Software Errors

23
Software Errors

23
1962: Mariner 1
Cost: $18.5 million

Disaster:
Mariner 1 rocket diverted from ight path
Mission Control destroyed it after 293 seconds

Cause:
A programmer incorrectly transcribed a
handwritten formula into computer code,
missing a single superscript bar.

24
fl
1996: Ariane 5
Cost: $500 million

Disaster:
Self destruct after 39 seconds

Cause:
Guidance computer tried to convert the sideways rocket
velocity from 64-bits to a 16-bit format An over ow error
resulted. The guidance system shut down, control passed
to an identical redundant unit, which also failed because
it was running the same algorithm. Code „worked“ on the
slower Ariane 4 rocket and (Guidance data was not even
needed/used, only used to align system before launch)

25
fl
1982: CIA plants a software
bug in Soviet Pipeline
Cost: Millions of dollars, signi cant
damage to Soviet economy

Disaster:
„The largest man-made non-nuclear
explosion in history“

Cause:
Soviets buy Canadian software to control
gas pipelines CIA discovered the purchase
and sabotaged the software so that it
would pass Soviet inspection but fail in
operation.
26
fi
 1985: Therac-25
Cost: Three people dead, three
people critically injured

Disaster:
Therac-25 delivers lethal dose of
radiation to patients

Cause:
multiple design bugs lead to a
number of different accidents
(missing hardware locks, race
conditions, over ows, ...)
27
fl
 2015: Dreamliner
Cost: Millions of dollars ?

Disaster: nothing (luckly)

Cause:
[..] a Model 787 airplane that has been powered
continuously for 248 days can lose all alternating current
(AC) electrical power due to the generator control units
(GCUs) simultaneously going into failsafe mode.

Signed 32 Bit over ow (increment every 1/100 second):

231
= 248,55134815 days
100 ⋅ 60 ⋅ 60 ⋅ 24

28
fl
29
GPT Lecture Videos

30
Object Oriented Programming (OOP)
in Python
Dates in Python

import random

day = [Link](1,28)
month = [Link](1,12)
year = [Link](1900,2100)

print(day,".", month,".", year,sep="")

32
 Dates in Python
import random

day = []
month = []
year = []

for i in range(100):
day += [[Link](1,28)]
month += [[Link](1,12)]
year += [[Link](1900,2100)]

for i in range(len(day)):
print(day[i],".", month[i], ".", year[i],sep="")

33
 Dates in Python
import random

class Date:
def __init__(self, day, month, year):
[Link] = day
[Link]= month
[Link] = year

dates = []
for i in range(100):
d = [Link](1,28)
m = [Link](1,12)
y = [Link](1900,2100)
dates += [Date(d,m,y)]

for date in dates:

print([Link],".",[Link],".",[Link],sep="")

34
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

35
 Eine Datum Klasse
Schlüsselwort class
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

35
 Eine Datum Klasse
Schlüsselwort class
import random Bezeichner der neuen Klasse
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

35
 Eine Datum Klasse
import random __init__-Methode
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

36
 Eine Datum Klasse
import random __init__-Methode
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)__init__-Methode
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

37
 Eine Datum Klasse
import random self-Parameter
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

38
 Eine Datum Klasse
import random self-Parameter
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = [] self-Parameter
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

38
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

39
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = [] Zugriff auf die Objektdaten

for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

39
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = [] Zugriff auf die Objektdaten

for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

Zugriff auf die Objektdaten 39

 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

daten = []

for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print(datum)

40
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

def tagImJahr(self):
monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
if ([Link] > 2): monatsTage+= 28
if ([Link] > 3): monatsTage+= 31
if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

daten = []

for i in range(100):
daten += [Datum([Link](1,28), [Link](1,12),
[Link](1900,2100))]

for datum in daten:

print(datum)
print([Link]())

41
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

def tageImFeb(self):
if [Link] % 4 == 0 and ([Link] % 100 != 0 or [Link] % 400 == 0):
return 29
else:
return 28

def tagImJahr(self):
monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
if ([Link] > 2): monatsTage+= [Link]()
if ([Link] > 3): monatsTage+= 31
if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

daten = []

for i in range(100):
daten += [Datum([Link](1,28), [Link](1,12),
[Link](1900,2100))]

for datum in daten:

print(datum)
print([Link]())

42
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

def __tageImFeb(self):
if [Link] % 4 == 0 and ([Link] % 100 != 0 or [Link] % 400 == 0):
return 29
else:
return 28

def tagImJahr(self):
monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
if ([Link] > 2): monatsTage+= self.__tageImFeb()
if ([Link] > 3): monatsTage+= 31
if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

daten = []

for i in range(100):
daten += [Datum([Link](1,28), [Link](1,12),
[Link](1900,2100))]

for datum in daten:

print(datum)
print([Link]())

43
 [Link]
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr
[Link] def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])
import random
import Datum
def __tageImFeb(self):
daten = [] if [Link] % 4 == 0 and ([Link] % 100 != 0 or [Link] % 400 == 0):
return 29
for i in range(100): else:
t = [Link](1,28) return 28
m = [Link](1,12)
j = [Link](1900,2100) def tagImJahr(self):
daten += [[Link](t,m,j)] monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
for datum in daten: if ([Link] > 2): monatsTage+= self.__tageImFeb()
print(datum) if ([Link] > 3): monatsTage+= 31
print([Link]()) if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

44
 [Link]
import random

class Datum:
def __init__(self, tag, monat, jahr):
self.__tag = tag
self.__monat= monat
self.__jahr = jahr

def tag(self):
return self.__tag

def monat(self):
return self.__monat

def jahr(self):
return self.__jahr

def __repr__(self):
return str(self.__tag) + "." + str(self.__monat) + "." + str(self.__jahr)

def __hash__(self):
return hash((self.__tag, self.__monat, self.__jahr))

[Link] def __eq__(self, other):

if other == None: return False
if type(self) != type(other): return False
if self.__tag != other.__tag: return False
if self.__monat != other.__monat: return False
if self.__jahr != other.__jahr: return False
from Datum import Datum return True

daten = [] def __lt__(self, other):

if other == None: return False
for i in range(100): if type(self) != type(other): return False
daten += [[Link]()] if self.__jahr < other.__jahr: return True
if self.__jahr > other.__jahr: return False
[Link]() if self.__monat < other.__monat: return True
if self.__monat > other.__monat: return False
for datum in daten: return self.__tag < other.__tag
print(datum)
print([Link]()) @classmethod
def ZufallsDatum(cls):
jahr = [Link](1900,2100)
monat = [Link](1,12)
tag = [Link](1,cls.__maxTageImMonat(monat, jahr))
return cls(tag,monat,jahr)

@staticmethod
def __maxTageImMonat(monat,jahr):
if monat == 1: return 31
elif monat == 2:
if jahr % 4 == 0 and (jahr % 100 != 0 or jahr % 400 == 0):
return 29
else:
return 28
elif monat == 3: return 31
elif monat == 4: return 30
elif monat == 5: return 31
elif monat == 6: return 30
elif monat == 7: return 31
elif monat == 8: return 31
elif monat == 9: return 30
elif monat == 10: return 31
elif monat == 11: return 30
else: return 31

def tagImJahr(self):
monatsTage = 0;
for m in range(1,self.__monat):
monatsTage += self.__maxTageImMonat(m,self.__jahr)
return self.__tag + monatsTage
45
 Dates in Python
import random

class Date:
def __init__(self, day, month, year):
[Link] = day
[Link]= month
[Link] = year

def output(self):
print([Link],".",[Link],".",[Link],sep="")

dates = []
for i in range(100):
d = [Link](1,28)
m = [Link](1,12)
y = [Link](1900,2100)
dates += [Date(d,m,y)]

for date in dates:

[Link]()

46
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

47
 Eine Datum Klasse
Schlüsselwort class
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

47
 Eine Datum Klasse
Schlüsselwort class
import random Bezeichner der neuen Klasse
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

47
 Eine Datum Klasse
import random __init__-Methode
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

48
 Eine Datum Klasse
import random __init__-Methode
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)__init__-Methode
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

49
 Eine Datum Klasse
import random self-Parameter
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

50
 Eine Datum Klasse
import random self-Parameter
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = [] self-Parameter
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

50
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = []
for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

51
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = [] Zugriff auf die Objektdaten

for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

51
 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

daten = [] Zugriff auf die Objektdaten

for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print([Link],".",[Link],".",[Link],sep="")

Zugriff auf die Objektdaten 51

 Eine Datum Klasse
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

daten = []

for i in range(100):
t = [Link](1,28)
m = [Link](1,12)
j = [Link](1900,2100)
daten += [Datum(t,m,j)]

for datum in daten:

print(datum)

52
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

def tagImJahr(self):
monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
if ([Link] > 2): monatsTage+= 28
if ([Link] > 3): monatsTage+= 31
if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

daten = []

for i in range(100):
daten += [Datum([Link](1,28), [Link](1,12),
[Link](1900,2100))]

for datum in daten:

print(datum)
print([Link]())

53
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

def tageImFeb(self):
if [Link] % 4 == 0 and ([Link] % 100 != 0 or [Link] % 400 == 0):
return 29
else:
return 28

def tagImJahr(self):
monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
if ([Link] > 2): monatsTage+= [Link]()
if ([Link] > 3): monatsTage+= 31
if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

daten = []

for i in range(100):
daten += [Datum([Link](1,28), [Link](1,12),
[Link](1900,2100))]

for datum in daten:

print(datum)
print([Link]())

54
import random

class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr

def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])

def __tageImFeb(self):
if [Link] % 4 == 0 and ([Link] % 100 != 0 or [Link] % 400 == 0):
return 29
else:
return 28

def tagImJahr(self):
monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
if ([Link] > 2): monatsTage+= self.__tageImFeb()
if ([Link] > 3): monatsTage+= 31
if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

daten = []

for i in range(100):
daten += [Datum([Link](1,28), [Link](1,12),
[Link](1900,2100))]

for datum in daten:

print(datum)
print([Link]())

55
 [Link]
class Datum:
def __init__(self, tag, monat, jahr):
[Link] = tag
[Link]= monat
[Link] = jahr
[Link] def __repr__(self):
return str([Link]) + "." + str([Link]) + "." + str([Link])
import random
import Datum
def __tageImFeb(self):
daten = [] if [Link] % 4 == 0 and ([Link] % 100 != 0 or [Link] % 400 == 0):
return 29
for i in range(100): else:
t = [Link](1,28) return 28
m = [Link](1,12)
j = [Link](1900,2100) def tagImJahr(self):
daten += [[Link](t,m,j)] monatsTage = 0;
if ([Link] > 1): monatsTage+= 31
for datum in daten: if ([Link] > 2): monatsTage+= self.__tageImFeb()
print(datum) if ([Link] > 3): monatsTage+= 31
print([Link]()) if ([Link] > 4): monatsTage+= 30
if ([Link] > 5): monatsTage+= 31
if ([Link] > 6): monatsTage+= 30
if ([Link] > 7): monatsTage+= 31
if ([Link] > 8): monatsTage+= 31
if ([Link] > 9): monatsTage+= 30
if ([Link] > 10): monatsTage+= 31
if ([Link] > 11): monatsTage+= 30
return [Link] + monatsTage

56
 [Link]
import random

class Datum:
def __init__(self, tag, monat, jahr):
self.__tag = tag
self.__monat= monat
self.__jahr = jahr

def tag(self):
return self.__tag

def monat(self):
return self.__monat

def jahr(self):
return self.__jahr

def __repr__(self):
return str(self.__tag) + "." + str(self.__monat) + "." + str(self.__jahr)

def __hash__(self):
return hash((self.__tag, self.__monat, self.__jahr))

[Link] def __eq__(self, other):

if other == None: return False
if type(self) != type(other): return False
if self.__tag != other.__tag: return False
if self.__monat != other.__monat: return False
if self.__jahr != other.__jahr: return False
from Datum import Datum return True

daten = [] def __lt__(self, other):

if other == None: return False
for i in range(100): if type(self) != type(other): return False
daten += [[Link]()] if self.__jahr < other.__jahr: return True
if self.__jahr > other.__jahr: return False
[Link]() if self.__monat < other.__monat: return True
if self.__monat > other.__monat: return False
for datum in daten: return self.__tag < other.__tag
print(datum)
print([Link]()) @classmethod
def ZufallsDatum(cls):
jahr = [Link](1900,2100)
monat = [Link](1,12)
tag = [Link](1,cls.__maxTageImMonat(monat, jahr))
return cls(tag,monat,jahr)

@staticmethod
def __maxTageImMonat(monat,jahr):
if monat == 1: return 31
elif monat == 2:
if jahr % 4 == 0 and (jahr % 100 != 0 or jahr % 400 == 0):
return 29
else:
return 28
elif monat == 3: return 31
elif monat == 4: return 30
elif monat == 5: return 31
elif monat == 6: return 30
elif monat == 7: return 31
elif monat == 8: return 31
elif monat == 9: return 30
elif monat == 10: return 31
elif monat == 11: return 30
else: return 31

def tagImJahr(self):
monatsTage = 0;
for m in range(1,self.__monat):
monatsTage += self.__maxTageImMonat(m,self.__jahr)
return self.__tag + monatsTage
57
 R EADING L IST :

1.5 U NION -F IND

h tt p : / / a l g s 4 . c s . p r i n c e t o n . e d u

58