Exam Flashcards
(92 cards)
1
Q
A
2
Q
A
3
Q
A
4
Q
A
- Run the jobs in decreasing order of finishing time f_i
5
Q
A
6
Q
A
7
Q
A
8
Q
A
9
Q
Exchange argument
A
- 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)
10
Q
A
11
Q
A
12
Q
A
13
Q
A
14
Q
A
15
Q
A
16
Q
A
17
Q
A
18
Q
A
19
Q
A
20
Q
A
21
Q
A
22
Q
A
23
Q
A
24
Q
A
25
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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
64
# Definitions
Give definition of Dynamic programming
* 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.
65
What are the topics in the course
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
66
Give *stay ahead* argument for Interval scheduling
Algorithm has the option to choose candidate j\_r as its solution
67
Types of greedy problem
* Picking out a subset (interval scheduling)
* Then use exchange argument
* Give an ordering
* Use “swapping” argument where you swap the order of the elements
68
Unroll the following recurrence 2T(n/2) + O(n)
69
What are some characteristics of algorithms
* 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
