Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms - TIN093 > Exam > Flashcards

Exam Flashcards

1
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q
A
  • Run the jobs in decreasing order of finishing time f_i
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q
A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q
A
38
Q
A
39
Q
A
40
Q
A
41
Q
A
42
Q
A
43
Q
A
44
Q
A
45
Q
A
46
Q
A
47
Q
A
48
Q
A
49
Q
A
50
Q
A
51
Q
A
52
Q
A
53
Q
A
54
Q
A
55
Q
A
56
Q
A
57
Q
A
58
Q
A
59
Q
A
60
Q
A
61
Q
A
62
Q
A
63
Q
A

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
Q

Definitions

Give definition of Dynamic programming

A
  • 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
Q

What are the topics in the course

A
  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
Q

Give stay ahead argument for Interval scheduling

A

Algorithm has the option to choose candidate j_r as its solution

67
Q

Types of greedy problem

A
  • 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
Q

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

A
69
Q

What are some characteristics of algorithms

A
  • 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
Q
A
71
Q
A
72
Q
A
73
Q
A
74
Q
A
75
Q
A
76
Q
A
77
Q
A
78
Q
A
79
Q
A
80
Q
A
81
Q
A
82
Q
A
83
Q
A
84
Q
A
85
Q
A
86
Q
A
87
Q
A
88
Q
A
89
Q
A
90
Q
A
91
Q
A
92
Q
A

Algorithms - TIN093 (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions