Labbar är i E:Hacke och i Discord.
- 10 lectures - 6 labbar
- Man kan boka munta när man vill om man är klar med alla labbar.
- Finns videos på videos.
- Convexa höljen är inte längre med i kursen.
- Greedy algorithms - make decisions on limited info.
- Graph search - graph search algorithms
- Dynamic programming - avoid duplicated work, caching etc
- Divide and conquer - split work into smaller chunks
- Network flow -
- Linear programming - inequalities and maximizing function
- Integer linear programming - only integer solutions, results are only integers.
- Time complexity
- Complexity of problem
- Problem complexity classes: P and NP and NPC
- what to do if you cannot find an efficient algorithm.
- Which of f(n) = 124*n and g(n) = 52*n**3 are in O(n**2)
- Only f since with large n, we have g(n) >= c * n**2
Examples of algorithms
- If it has polynomial running time it is regarded as efficient
- O(log n): searching in a sorted array
- O(n+m): visiting all n nodes in a graph with m edges
- O(nlogn):sorting an array
- O(n**2): two for loops
Quiz: You have points in a plane and want to find a pair of points with minimal distance. How can you do that?
You could use two for-loops. For each point find the distance to every other point. O(n**2). This is efficient according to theory. It is too slow in practice for large number of points. If 10**9 points it would take years.
If dividing the field into subfields it would take seconds instead of years (Divide and conquer).
Examples of inefficient algorithms
- O(2**n): Selecting each subset of elements
- O(n!): All permutations of n objects.
Frågor kring rimlighet eller vilka algoritmer man kan använda för att lösa problemen. Fråga att förklara för en 4a åring kring hur man gör något. Man får inte använda svåra ord från denna kursen då utan bara enkla ord.
- given two sets X and Y.
- A matching M is a set of pairs (x, y) such that each (x, y) is in only one pair.
- Matchings can be used for many things:
- university admissions: n students and n places at universities
- medical training: n medical students and n internships
- not so realistic but lab 1 is about summer jobs: students and companies.
- The size of M may be less than n.
- if all are matched it is called a perfect matching.
- Assume each company has exactly one job offer.
- Each company has a preferred list of students sorted in descending order and similarly for students.
- We assume a student s applies to a company c which answeres ues or no if yes then s, c becomes matched temporarily in a pair.
- If later another student applies to c1 and it says yes, a new pair is created and the old no longer exists.
- How can we create a perfect matching with no pairs wanting to split?
If U contains two pairs who want to split U is called an unstable matching. A stable matching is a perfect matching with no unstable pairs.
How does it work? - How do we find a stable matching?
procedure GS(S, C)
S is a set of n students and C is a set of n companies , add each studnet s to al list p.