# Elementær diskret matematikk våren 2015

Recap notes.recap.pdf

List of chapters that is required:
1.1-4;
2.1-5;
3.1-3;
4.1-2;
5.1-8;
6.1-3;
7.1-4;
11.1-5;
12.1-3;
13.1-2

Will update notes from recap week soon.

## Forelesningslogg

• Recap week We will go through the stuffs in the book and I will list all the important things you need know. BTW, I will repeat the things in April 7's lecture. So no worries if you miss it.
• 09. April 4.7-9.pdf We presented two algorithms concerning minimal spanning trees. The important principle is that optimizing locally resulting global optimization.
• 07. April We went through shortest path algorithm. Since not many people came today (and maybe it should be holiday…), I will go through this part during recaps.
• 26. mars 3.26.pdf We continue the analysis of algorithms. We also mentioned binary numbers, which play an important role in computer science.
• 24. mars 3.24.pdf We study the complexity, i.e. how to measure the growing speed of a function. Common Big-Oh forms are const, log, linear, quadratic, polynomial, exp and factorial.
• 19. mars 3.19.pdf We recall the depth and breadth first search and go through rooted trees with some examples. We end up with sorting algorithm.
• 17. mars Vi fullførte kapittel 11 (Eulers formel for planare grafer, duale grafer, kort om graf-fargelegging, Hamilton-veier), og startet på kapittel 12 om trær, og kom oss gjennom dybde først-søk og bredde først-søk.
• 12. mars Først gjorde vi ferdig kapittel 11.2, og så snakket vi om regulære grafer, Euler-veier (med bevis for hovedteoremet) og startet på planare grafer, til og med Kuratowskis teorem. Neste gang starter vi med resten av 11.4 og 11.5.