Слайд 3Billboard – Problem
Test all existing subsets
2256 possibilities for the 16x16 board
☹
![Billboard – Problem Test all existing subsets 2256 possibilities for the 16x16 board ☹](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-2.jpg)
Слайд 4Billboard – Main Idea
What if we somehow knew the tapped tiles in
![Billboard – Main Idea What if we somehow knew the tapped tiles in the first row?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-3.jpg)
the first row?
Слайд 5Billboard – Main Idea
We can try what happens with the row
WOW! It
![Billboard – Main Idea We can try what happens with the row](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-4.jpg)
is easy to find the second one!
Слайд 6Billboard – Main Idea
We can try what happens with the row
WOW! It
![Billboard – Main Idea We can try what happens with the row](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-5.jpg)
is easy to find the second one!
Слайд 7Billboard – Main Idea
Let’s also do it…
The third row becomes evident
… and
![Billboard – Main Idea Let’s also do it… The third row becomes](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-6.jpg)
so on
Слайд 8Billboard – Solution
Ok, but how to find the first row?
We will try
![Billboard – Solution Ok, but how to find the first row? We](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-7.jpg)
all possibilities!
Approx. 216 * 162
Слайд 10Cell – Problem
Find a circle that covers most points
Center may not be
![Cell – Problem Find a circle that covers most points Center may](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-9.jpg)
in an existing point
? Solution will always touch 2 points
Слайд 11Cell – Simple Solution
Take all pairs, find a circle
Then all other points
![Cell – Simple Solution Take all pairs, find a circle Then all](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-10.jpg)
must be tested
? Time: n3 ☹
Слайд 12Cell –Solution
For each point, use “sweep” technique
Find „interesting angles“ and sort them
![Cell –Solution For each point, use “sweep” technique Find „interesting angles“ and sort them](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-11.jpg)
Слайд 13Cell –Solution
One sorting for each point
? Time: n2 . log n
Carefully with
![Cell –Solution One sorting for each point ? Time: n2 . log](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-12.jpg)
floating point numbers!
Слайд 15Hexagon – Idea
All combinations of 2 green points
![Hexagon – Idea All combinations of 2 green points](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-14.jpg)
Слайд 16Hexagon – Solution
Handle “special” cases
![Hexagon – Solution Handle “special” cases](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-15.jpg)
Слайд 17Hexagon –Solution II
Dynamic Programming
For all area subsets (16), find the best solution
![Hexagon –Solution II Dynamic Programming For all area subsets (16), find the](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-16.jpg)
using each parcel
Слайд 19Keys – Idea
Breadth-First search
Combination of position and keys (!)
4 keys => 16
![Keys – Idea Breadth-First search Combination of position and keys (!) 4 keys => 16 combinations](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-18.jpg)
combinations
Слайд 20Keys – Idea
Position (1,7) + Red Key
(1,8) + Red/Yellow
(1,6) + Red
![Keys – Idea Position (1,7) + Red Key (1,8) + Red/Yellow (1,6) + Red](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-19.jpg)
Слайд 22Logic – Problem
Problem? There is no problem
“Only” follow the connections
Compute logical operations
![Logic – Problem Problem? There is no problem “Only” follow the connections Compute logical operations](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-21.jpg)
Слайд 23Logic – Potential Pitfalls
Gates with no input
AND ? 1
OR ? 0
XOR ?
![Logic – Potential Pitfalls Gates with no input AND ? 1 OR](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-22.jpg)
0
Слайд 24Logic – Potential Pitfalls
Splitting and joining paths
=> We must remember, what has
![Logic – Potential Pitfalls Splitting and joining paths => We must remember,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-23.jpg)
already been computed
&
&
&
&
&
Слайд 25N: Numbers
10101010100101-2 = -10907
![N: Numbers 10101010100101-2 = -10907](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-24.jpg)
Слайд 26Numbers – Solution
TO decimal:
Use the formula in the problem statement
4257-10 = -4000
![Numbers – Solution TO decimal: Use the formula in the problem statement](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-25.jpg)
+ 200 – 50 + 7 = -3843
Слайд 27Numbers – Solution
FROM decimal:
Use remainders (modulo)
Careful with the negative numbers!
4237 mod 10
![Numbers – Solution FROM decimal: Use remainders (modulo) Careful with the negative](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-26.jpg)
= 7 -> 423
-423 mod 10 = 7 -> -43
43 mod 10 = 3 -> 4
-4 mod 10 = 6 -> -1
1 mod 10 = 1
-> 16377
Слайд 29Polygon – Problem
Find the order of polygon vertices
![Polygon – Problem Find the order of polygon vertices](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-28.jpg)
Слайд 30Polygon – Idea
Sort the vertices by their X coordinate
1
3
2
4
5
6
7
8
![Polygon – Idea Sort the vertices by their X coordinate 1 3](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-29.jpg)
Слайд 31Polygon – Idea
=> Find their horizontal neighbor
1
3
2
4
5
6
7
8
![Polygon – Idea => Find their horizontal neighbor 1 3 2 4 5 6 7 8](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-30.jpg)
Слайд 32Polygon – Idea
Sort by Y => vertical neighbor
1
5
3
7
4
6
2
8
![Polygon – Idea Sort by Y => vertical neighbor 1 5 3](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-31.jpg)
Слайд 33Polygon – Solution
Now, each vertex knows its neighbors
Start with the first, and
![Polygon – Solution Now, each vertex knows its neighbors Start with the first, and walk around](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-32.jpg)
walk around
Слайд 34Polygon – Solution
Count Left / Right turns
Left > Right ? => counter-clockwise
R
L
L
L
L
L
R
![Polygon – Solution Count Left / Right turns Left > Right ?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-33.jpg)
Слайд 37Sort – Problem
Naive approach – reverse in an array
Little bit better: remember
![Sort – Problem Naive approach – reverse in an array Little bit](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-36.jpg)
reversed
Quadratic time ? 100 0002 ☹
Слайд 38Sort – Another Approach
Double-linked list
Problem finding the „forward direction“
5
4
7
1
2
8
3
5
4
7
1
2
8
3
![Sort – Another Approach Double-linked list Problem finding the „forward direction“ 5](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-37.jpg)
Слайд 39Sort – Solution
Combined solution: use both
Linked list + array of reversed
The array
![Sort – Solution Combined solution: use both Linked list + array of](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-38.jpg)
time: O(rev_before)
After SQRT(n) steps: reorder
? n.SQRT(n) time
Слайд 40Sort – Solution II
Other possibilities - ???
Heap
Interval Trees
… ?
![Sort – Solution II Other possibilities - ??? Heap Interval Trees … ?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-39.jpg)
Слайд 42Water – Problem
Find the Center of Mass
Amount of water with the lowest
![Water – Problem Find the Center of Mass Amount of water with the lowest center](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-41.jpg)
center
Слайд 43Water – Idea
Split the glass into horizontal slices
Volume of one slice: π.r2.d
![Water – Idea Split the glass into horizontal slices Volume of one slice: π.r2.d](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-42.jpg)
Слайд 44Water – Solution
Center of Mass of the glass
Weighted average of all slices
![Water – Solution Center of Mass of the glass Weighted average of all slices](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-43.jpg)
Слайд 45Water – Solution
Add the water “slowly”
Center of water mass
![Water – Solution Add the water “slowly” Center of water mass](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-44.jpg)
Слайд 46Water – Solution
Combine both centers
(weighted average)
![Water – Solution Combine both centers (weighted average)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-45.jpg)
Слайд 47Water – Solution
Water reached the center ? => END!
(Linear time needed only)
![Water – Solution Water reached the center ? => END! (Linear time needed only)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/934951/slide-46.jpg)