Exam

Question 1

Answer 1

Question 2

Answer 2

Question 3

Answer 3

Question 4

Answer 4

• Run the jobs in decreasing order of finishing time f_i

Question 5

Answer 5

Question 6

Answer 6

Question 7

Answer 7

Question 8

Answer 8

Question 9

Exchange argument

Answer 9

• Does not decrease optimality
• e.g, in EEF, it still contains an disjoint set of intervals when exchanging the leftmost intervals from set O (optimal set) and A (algorithm set)

Question 10

Answer 10

Question 11

Answer 11

Question 12

Answer 12

Question 13

Answer 13

Question 14

Answer 14

Question 15

Answer 15

Question 16

Answer 16

Question 17

Answer 17

Question 18

Answer 18

Question 19

Answer 19

Question 20

Answer 20

Question 21

Answer 21

Question 22

Answer 22

Question 23

Answer 23

Question 24

Answer 24

Question 25

Question 26

Answer 26

• Show how to swap
  
  • In case of interval scheduling, swap the two leftmost solutions from optimal and algorithms
• Show how the swap doesnt decrease optimality
  
  • In case of interval scheduling, since the interval has EEF, this does not intersect other intervals in the optimal set, hence its also an optimal solution

Question 27

Answer 27

Question 28

Answer 28

Question 29

Answer 29

Question 30

Answer 30

Question 31

Answer 31

Question 32

Answer 32

Question 33

Answer 33

Question 34

Answer 34

Question 35

Answer 35

Question 36

Answer 36

Question 37

Answer 37

Question 38

Answer 38

Question 39

Answer 39

Question 40

Answer 40

Question 41

Answer 41

Question 42

Answer 42

Question 43

Answer 43

Question 44

Answer 44

Question 45

Answer 45

Question 46

Answer 46

Question 47

Answer 47

Question 48

Answer 48

Question 49

Answer 49

Question 50

Answer 50

Question 51

Answer 51

Question 52

Answer 52

Question 53

Answer 53

Question 54

Answer 54

Question 55

Answer 55

Question 56

Answer 56

Question 57

Answer 57

Question 58

Answer 58

Question 59

Answer 59

Question 60

Answer 60

Question 61

Answer 61

Question 62

Answer 62

Answer 63

OPT(j)= max(v_j + OPT(P(j)), OPT(j -1))

we define PU), for an interval j, to be the
largest index i < j such that intervals i and j are disjoint

Question 64

Definitions

Give definition of Dynamic programming

Answer 64

• Solve problem by solving sub instance of problem

For a given instance of a problem, we consider certain sub-instances
that grow incrementally. For each of these sub-instances it suffices to keep one optimal solution (because, by an exchange argument, no other solution can lead to a better final solution for the entire instance). The optimal values are then computed step by step on the growing sub-instances. A “recursive” formula specifies how to compute the optimal value from the previously computed optimal values for smaller sub-instances. However, it is not applied recursively, rather, the values are stored in an array, and calculations happen in a for-loop.

Question 65

What are the topics in the course

Answer 65

1. Time complexity, O Notation
2. Greedy
3. Dynamic programming
4. Searching, divide and conquer
5. Reduction, NP completness
6. DAG’s and graph properties

Question 66

Give stay ahead argument for Interval scheduling

Answer 66

Algorithm has the option to choose candidate j_r as its solution

Question 67

Types of greedy problem

Answer 67

• Picking out a subset (interval scheduling)
  
  • Then use exchange argument
• Give an ordering
  
  • Use “swapping” argument where you swap the order of the elements

Question 68

Unroll the following recurrence 2T(n/2) + O(n)

Answer 68

Question 69

What are some characteristics of algorithms

Answer 69

• Looping
  
  • Looping through the whole input, O(n) complexity
  • No looping in algorithm refers to constant time i.e, O(1)
• Elementary operations
  
  • Arithemtic operations
  • If conditions - adding/mdulitplication, querying etc… indexing
  • Indexing/querying database or array

Question 70

Answer 70

Question 71

Answer 71

Question 72

Answer 72

Question 73

Answer 73

Question 74

Answer 74

Question 75

Answer 75

Question 76

Answer 76

Question 77

Answer 77

Question 78

Answer 78

Question 79

Answer 79

Question 80

Answer 80

Question 81

Answer 81

Question 82

Answer 82

Question 83

Answer 83

Question 84

Answer 84

Question 85

Answer 85

Question 86

Answer 86

Question 87

Answer 87

Question 88

Answer 88

Question 89

Answer 89

Question 90

Answer 90

Question 91

Answer 91

Question 92

Answer 92