CS260

Question 1

What is an algorithm?

Answer 1

Its a procedure used to solve a problem or perform a computation

Question 2

What do we intend for algorithms to be able to do?

Answer 2

Solve any instance of a class of problems eg. solve a list no matter the order
Solve for inputs of different size
May guarantee to give the correct answer with a proof
May have mathematical limits on whats possible

Question 3

Why do we analyze algorithms?

Answer 3

This is because we want to measure the cost of an algorithm. This is usually quantified using the running time which is a function expressed in terms of an input size n.

Question 4

Whats the mathematical proof for a polytime algo?

Answer 4

It states that for c>0 and d>0 on every input size N the max number of steps taken by a poly time algo is cN^d where d is the degree and c constant

Question 5

What is average case running time

Answer 5

Obtain bound on running time of algorithm on a random input as a function of input size N

Question 6

What is the desirable scaling property

Answer 6

It states that when the input size doubles the algo should slow down by a constant factor c=2^d
The algorithm ispolytime if the above is true

Question 7

What are the exceptions to the general rule of thumb that poly algos are efficient and exponential inefficent?

Answer 7

1.When poly algos have high coffiencients this is impractical but can help reveal something about problem
2.Some of the worst case running times r rare for certain exponential algos.

Question 8

What is stable matching?

Answer 8

Stable matching is an economic theory in which there are two parties that need to be paired together.The aim is to have have no unstable pairs and ensure that every participant is satisfied with their pairing.

Question 9

What is an unstable pair?

Answer 9

Suppose we have a man m and women w.If man m prefers w to his current matching and w prefers m to her current match.They may want to switch and defect.

Question 10

What type of system does a stable matching aim to make?

Answer 10

A self enforcing one meaning that acting in ones self interest does not destabilze the system

Question 11

What is a stable matching?

Answer 11

It is a perfect matching meaning everyone is matched bijectively and a stable matching.No incentive for a pair to undermine the assignment by defecting.

Question 12

Describe the Gale-Shapley algorithm

Answer 12

1.While there is a man m who is free and hasnt proposed to everyone.
2.Check if women w who is highest on m’s list prefers m to her current match if yes match the twoAnd make the other m free..Or if she is free match them.Else reject.

Question 13

What are the observations from the stable matching algorithm?

Answer 13

1.The man proposes in decreasing order meaning they get a worse and worse match.
2.The womens matches increase and her preferences go in ascending order.Once the women is matched she never gets unmatched

Question 14

What is the depth of set in interval partioning?

Answer 14

the depth of the set of open intervals is the maximum number of intervals that contain a given moment in time.

Question 15

Describe the interval partitioning algorithm.Whats the time complexity

Answer 15

1.Sort jobs by earliest starting time
2.Have a variable to keep track of number of classrooms used
3.Iterate through jobs and check to see if they overlap if yes assign a new classroom.And increment classroom variable.
4.If not assign current classroom.
Time complexity is O(nlogn) due to sorting

Question 16

Describe the proof for greedy being optimal for interval partioning

Answer 16

Claim:Greedy is optimal for interval partion
1.Let d be the number of classrooms allocated by greedy.
2.Suppose there is some job j that is allocated to classroom d.This means it was incompatible with d-1 classrooms.
3.These incompatibiles are caused by d-1 jobs finshing after sj
4.These jobs start no later than sj
5.So there are d jobs overlapping at sj+epsilon
6.Therefore we need atleast d classrooms.

Question 17

Describe the algo for minimizing max lateness

Answer 17

1.Sort Jobs in ascending order of deadlines.
2.Have time variable t equal to 0
3.Iterate through jobs and set interval to t+tj(processing time)
4.Set sj to t and fj to t+tj.
5.Set t to t +tj
6.Return sj,fj interval

Question 18

What is an inversion?

Answer 18

This is when given a schedule S where there i<j but j is scheduled before i.We swap the job to remove the inversion.

Question 19

What are 3/4 observations from the greedy algo that minimizes lateness?

Answer 19

1.The solution has no idle time
2.The solution has no inversions no idle time and is unique
3.If there are inversions they must be adjacent.