Yapity Logo
No results matched your search

Algodat

lth edaf05

Algodat anteckningar (EDAF05, LTH)

Ludde127 2023-04-25
L

Föreläsning 1

Länkar

  1. labbar
  2. kursinnehåll/filer

Install on linux/mac

Info

Labbar är i E:Hacke och i Discord.

todo:readingadvice.pdf

  • 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.

Course purpose

Algorithms

  • 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.

Complexity

  • Time complexity
  • Complexity of problem
  • Problem complexity classes: P and NP and NPC
  • what to do if you cannot find an efficient algorithm.

Complexity Ordo

  • 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

  1. O(2**n): Selecting each subset of elements
  2. O(n!): All permutations of n objects.

Tenta information

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.

Matchings

  • 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.

Example

  • 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.

while p!= null {
  s <- take out the first element from p
  c <- the companies prefers the most and s has not yet applied 
    to
  if c has no student
    (s, c) becomes a pair
  else if c prefers s over its current student sc then
    remove the pair sc, c
    s,c becomes a pair instead
  else
    add it into the list again
}

  • Assume that a company can determine if it prefers s over sc in one operation.
  • How fast is the GS algorithm?
  • Each student has n companies in its list, we have n**2 possible pairs.
  • How are comparisons done?
  • Student number 4 is most preferred
  • The companies only stores at which position a student is at.
  • Thus the complexity is at most O(n**2).

Facts

  • A company is matched from the ponts a student first applies to
  • A company is matched with increasingly preferred students
  • A student is matched with decreasingly preferred companies
  • If a student is free there remains a company it has not applied to
  • Proof. assume in contradictions s is free and has already applied to all n companies. Since every company is matched all n students are also matched, which is a contradiction since we assumed s in c not matched and there are n students.
  • It will be a perfect matching!

  • Consider a matching S produced by GS
  • For a student s a company c is valid if (s, c) is a pair in a astable matching.
  • The best company c is the company most preferred bu s which is valid for it.
  • The GS algorithm produces the stable matching {(s, c) | c = best(s)}
  • The order does not matter to the matchings.

Is Gale-Shapley fair? No the company will always receive the worst possible student. It does however find the best company for the students.