Elementær diskret matematikk våren 2015

Recap notes.recap.pdf

List of chapters that is required:

Will update notes from recap week soon.


  • 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.
2018-04-04, Hallvard Norheim Bø