1
00:00:00,789 --> 00:00:03,260
welcome back I hope that you

2
00:00:03,260 --> 00:00:06,549
yeah were able to get the RSL bed after
this

3
00:00:06,549 --> 00:00:09,730
a.m. long sequence an

4
00:00:09,730 --> 00:00:12,960
and what we did in the first part of
this lecture

5
00:00:12,960 --> 00:00:16,010
is take the description

6
00:00:16,010 --> 00:00:19,420
the informal description of the
expression a

7
00:00:19,420 --> 00:00:24,130
problem astoria the expression problem
up to come down problem

8
00:00:24,130 --> 00:00:27,710
expression problem is something
completely different again Google that

9
00:00:27,710 --> 00:00:28,260
and

10
00:00:28,260 --> 00:00:31,949
again you can spend years trying to
solve the expression problem

11
00:00:31,949 --> 00:00:35,540
but we are trying to solve the Condon
problem here

12
00:00:35,540 --> 00:00:39,050
and what we did is re constructed

13
00:00:39,050 --> 00:00:42,120
a brute-force solution where

14
00:00:42,120 --> 00:00:45,920
regis gender aidid's all possible
expressions

15
00:00:45,920 --> 00:00:49,750
and then checked weathered a satisfied

16
00:00:49,750 --> 00:00:53,680
the rules of the game what we're going
to do

17
00:00:53,680 --> 00:00:56,930
now is your gun going to try to check

18
00:00:56,930 --> 00:01:01,270
if we can avoid to generate

19
00:01:01,270 --> 00:01:04,930
and invalid expressions up front

20
00:01:04,930 --> 00:01:08,630
okay and our hope is that this rule

21
00:01:08,630 --> 00:01:12,430
definitely gives a perfect performance
improvement big us

22
00:01:12,430 --> 00:01:16,689
you know there's only I'm you now quite
a small fraction

23
00:01:16,689 --> 00:01:22,259
of all the possible expressions are
valid and

24
00:01:22,259 --> 00:01:26,689
and so the way we're going to do that is
we're going to look at

25
00:01:26,689 --> 00:01:30,350
bears of expressions and their

26
00:01:30,350 --> 00:01:34,509
values K so is the expression

27
00:01:34,509 --> 00:01:39,729
and this is the value so we carry around
both this symbolic representation of the

28
00:01:39,729 --> 00:01:40,640
expression

29
00:01:40,640 --> 00:01:43,899
and the numeric representation of the
expression

30
00:01:43,899 --> 00:01:46,990
and what we want is we want to have a

31
00:01:46,990 --> 00:01:51,210
function that fuses together

32
00:01:51,210 --> 00:01:55,009
degeneration and the evaluation

33
00:01:55,009 --> 00:01:58,200
of the expressions so this is the

34
00:01:58,200 --> 00:02:01,869
result evaluating the expression and
that is the

35
00:02:01,869 --> 00:02:05,670
result of generating the expression but
we needed

36
00:02:05,670 --> 00:02:09,539
the result of evaluating the expression
to check

37
00:02:09,539 --> 00:02:14,040
whether it satisfied and the constraints
of the game

38
00:02:14,040 --> 00:02:16,790
K so that's what we're going to do we're
going to try

39
00:02:16,790 --> 00:02:19,920
to define a function that will combine

40
00:02:19,920 --> 00:02:24,160
the generation and evaluation and

41
00:02:24,160 --> 00:02:27,740
the way we can do that ish as follows:

42
00:02:27,740 --> 00:02:31,000
if three want to find the results

43
00:02:31,000 --> 00:02:36,250
for the empty nest well that's the empty
nest when we want to

44
00:02:36,250 --> 00:02:42,030
generate the combination of expressions
and their values

45
00:02:42,030 --> 00:02:45,140
for single-a meshed well what do we do

46
00:02:45,140 --> 00:02:48,320
we did what we did before be and

47
00:02:48,320 --> 00:02:52,120
generate expression we know its value

48
00:02:52,120 --> 00:02:55,709
but this is only valid remember when

49
00:02:55,709 --> 00:02:58,760
the and number was greater than 0

50
00:02:58,760 --> 00:03:01,870
so now we can put this test right here

51
00:03:01,870 --> 00:03:06,080
and the rest of the gods is now

52
00:03:06,080 --> 00:03:10,130
fairly obvious where we just do exactly
the same

53
00:03:10,130 --> 00:03:13,360
except that we recursively call results

54
00:03:13,360 --> 00:03:17,230
okay and and then

55
00:03:17,230 --> 00:03:20,620
we still have to define the combine
function here

56
00:03:20,620 --> 00:03:23,780
that will do the same thing that will
kinda check

57
00:03:23,780 --> 00:03:27,350
weather D result are fell it so here is

58
00:03:27,350 --> 00:03:31,200
combine its exactly the same

59
00:03:31,200 --> 00:03:35,220
as our previous combine function accepts

60
00:03:35,220 --> 00:03:39,519
that now we also check weathered the
results are valid

61
00:03:39,519 --> 00:03:43,019
you see that we can do that because we
are now

62
00:03:43,019 --> 00:03:47,010
carrying around a pair of the expression
and its value

63
00:03:47,010 --> 00:03:50,610
and that allows us to check HERE whether

64
00:03:50,610 --> 00:03:54,010
the result is valid as we are generating

65
00:03:54,010 --> 00:03:57,730
these new expressions some it's got a
small

66
00:03:57,730 --> 00:04:00,780
an change am but its

67
00:04:00,780 --> 00:04:05,620
to quite dramatic so here's the new
function that solves the condom problem

68
00:04:05,620 --> 00:04:09,090
am and it's just a.m. using

69
00:04:09,090 --> 00:04:12,900
this new results a function here so we
take all the choices

70
00:04:12,900 --> 00:04:16,549
we calculate the results given the east
and then

71
00:04:16,549 --> 00:04:20,160
we check rather the result is the wrong

72
00:04:20,160 --> 00:04:26,310
that we want and this case every run
this now

73
00:04:26,310 --> 00:04:30,220
its about ten times faster so it's now
an

74
00:04:30,220 --> 00:04:33,280
you know for hundreds of a second

75
00:04:33,280 --> 00:04:38,840
and also this guy here which used to be
a mother wasn't 43 seconds

76
00:04:38,840 --> 00:04:42,930
is now down to three and a half seconds
and

77
00:04:42,930 --> 00:04:46,150
this is fabulous this is really fabulous

78
00:04:46,150 --> 00:04:50,580
can we do even better

79
00:04:50,580 --> 00:04:54,080
can we do even better and we can

80
00:04:54,080 --> 00:04:57,970
biggest we have now eliminated

81
00:04:57,970 --> 00:05:01,210
generating invalid expressions

82
00:05:01,210 --> 00:05:05,320
because me we're generating the
expressions with their results it said

83
00:05:05,320 --> 00:05:06,639
we could always check

84
00:05:06,639 --> 00:05:09,940
whether they were okay but they're still

85
00:05:09,940 --> 00:05:13,630
cemeteries that we're not using okay

86
00:05:13,630 --> 00:05:17,320
biggest really every have X times why

87
00:05:17,320 --> 00:05:22,099
thats basically the same ardent
basically dead is the same

88
00:05:22,099 --> 00:05:25,210
as white I'm check so we don't have to
generate

89
00:05:25,210 --> 00:05:28,599
both of these to results

90
00:05:28,599 --> 00:05:33,039
and if we happened to multiply number by
WAM

91
00:05:33,039 --> 00:05:37,060
we might as well just use X okay

92
00:05:37,060 --> 00:05:40,470
so if we use these properties we will
eliminate

93
00:05:40,470 --> 00:05:44,889
you now we won't be using the
expressions here on the left

94
00:05:44,889 --> 00:05:48,659
because they are considered to be the
same

95
00:05:48,659 --> 00:05:52,110
as the expressions on the right so
hopefully

96
00:05:52,110 --> 00:05:55,860
we can reduce the search space

97
00:05:55,860 --> 00:05:59,270
fordice and that's what we'll do

98
00:05:59,270 --> 00:06:03,349
and the next part so take a small break

99
00:06:03,349 --> 00:06:04,389
and all season