-
Notifications
You must be signed in to change notification settings - Fork 0
/
dsa_21_traversal.html
824 lines (765 loc) · 39.4 KB
/
dsa_21_traversal.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
<!Doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
<link href="css/fontawesome-free-6.2.1-web/css/all.css" rel="stylesheet">
<script src="lib/colorbrewer.v1.min.js" charset="utf-8"></script>
<script src="lib/colorStringStandalone.js" charset="utf-8"></script>
<script type="text/javascript" src="lib/jquery-2.2.4.min.js"></script>
<title>Design & Analysis: Algorithms</title>
<meta name="description" content="CS4851/6851 GSU class">
<meta name="author" content="Sergey M Plis">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
<link rel="stylesheet" href="dist/reset.css">
<link rel="stylesheet" href="dist/reveal.css">
<!-- Code syntax highlighting -->
<link rel="stylesheet" href="plugin/highlight/monokai.css" id="highlight-theme">
<!-- <link rel="stylesheet" href="lib/css/zenburn.css"> -->
<link rel="stylesheet" href="css/custom.css">
<link rel="stylesheet" href="dist/theme/aml.css" id="theme">
<!-- Printing and PDF exports -->
<script>
var link = document.createElement( 'link' );
link.rel = 'stylesheet';
link.type = 'text/css';
link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.scss';
document.getElementsByTagName( 'head' )[0].appendChild( link );
</script>
<script type="module" src="js/wc_code/wc-code.js"></script>
<!--Popup Window CSS-->
<style media="screen">
*,*:before,*:after{
padding: 0;
margin: 0;
box-sizing: border-box;
}
.popup{
background-color: #fdf6e3;
width: 80%;
padding: 30px 40px;
position: absolute;
transform: translate(-50%,-50%);
left: 50%;
top: 50%;
border-radius: 8px;
font-family: "Poppins",sans-serif;
display: none;
z-index: 1000;
text-align: left;
max-height: 90%;
overflow: scroll;
}
.popup button{
display: block;
margin: 0 0 20px auto;
background-color: transparent;
font-size: 30px;
color: #fdf6e3;
background: #03549a;
border-radius: 100%;
width: 40px;
height: 40px;
border: none;
outline: none;
cursor: pointer;
}
</style>
</head>
<body>
<div class="reveal">
<!-- In between the <div="reveal"> and the <div class="slides">-->
<!-- <header style="position: absolute; top: 10px; left: 100px; z-index: 500; font-size:100px;background-color: rgba(0,0,0,0); text-align: center !important"></header> -->
<!-- In between the <div="reveal"> and the <div class="slides">-->
<!-- Any section element inside of this container is displayed as a slide -->
<div class="slides">
<section>
<section data-background="figures/marvel_social_graph.png" data-background-size="cover">
<p>
<h2 style="text-shadow: 10px 10px 10px #002b36; color: #fdf6e3;">Design & Analysis: Algorithms</h2>
<h2 style="text-shadow: 10px 10px 10px #002b36; color: #fdf6e3;">21: Graphs and Traversals</h2>
<p>
</section>
<section data-fullscreen>
<h3>Schedule</h3>
<row style="width: 100%">
<col50>
<table style="font-size:14px">
<tr>
<th>#</th>
<th>date</th>
<th>topic</th>
<th>description</th>
</tr>
<tr><td>1</td>
<td> 09-Jan-2023 </td>
<td> Introduction and Introductions </td>
<td> </td>
</tr>
<tr><td>2</td>
<td> 11-Jan-2023 </td>
<td> Basics of Algorithm Analysis </td>
<td> </td>
</tr>
<tr style='background-color: #FBEEC2;'><td> </td><td> 16-Jan-2023 </td><td> <em>Holiday</em> </td><td> </td></tr>
<tr><td> 3 </td><td> 18-Jan-2023 </td><td> Asymptotic Analysis </td><td> hw1 </td></tr>
<tr><td> 4 </td><td> 23-Jan-2023 </td><td> Recurrence Relations: Substitution </td><td> </td></tr>
<tr><td> 5 </td><td> 25-Jan-2023 </td><td> Recursion Trees and the Master Theorem </td><td> </td></tr>
<tr><td> 6 </td><td> 30-Jan-2023 </td><td> Recurrence Relations: Annihilators </td></td></td><td> </td></tr>
<tr><td> 7 </td><td> 1-Feb-2023 </td><td> Recurrence Relations: Transformations </td><td> hw2, hw1 <i class="fa-solid fa-calendar-check"></i> </td></tr>
<tr><td> 8 </td><td> 6-Feb-2023 </td><td> Heap & Invariants</td><td> </td></tr>
<tr><td> 9 </td><td> 8-Feb-2023 </td><td> Queue & Qsort </td><td> </td></tr>
<tr><td> 10 </td><td> 13-Feb-2023 </td><td> Analyzing RQsort </td><td> </td></tr>
<tr><td> 11 </td><td> 15-Feb-2023 </td><td> Comparison-based Sorting Analysis </td><td> hw3, hw2 <i class="fa-solid fa-calendar-check"></i> </td></tr>
<tr><td> 12 </td><td> 20-Feb-2023 </td><td> Dictionary</td><td> </td></tr>
<tr><td> 13 </td><td> 22-Feb-2023 </td><td> Open Address Hashing & Refresher </td><td> </td></tr>
<tr style='background-color: #E5DDCB;'><td> 14 </td><td> 27-Feb-2023 </td><td> Midterm exam </td><td> <em>midpoint</em> </td></tr>
<tr><td> 15 </td><td> 1-Mar-2023 </td><td> Binary Search Trees I </td><td> </td></tr>
<tr><td> 16 </td><td> 6-Mar-2023 </td><td> Binary Search Trees II </td><td>hw4, hw3 <i class="fa-solid fa-calendar-check"></i> </td></tr>
<tr><td> 17 </td><td> 8-Mar-2023 </td><td> Balanced Binary Search Trees </td><td> </td></tr>
</table>
</col50>
<col50>
<table style="font-size:16px; vertical-align: top;">
<tr>
<th>#</th>
<th>date</th>
<th>topic</th>
<th>description</th>
</tr>
<tr style='background-color: #FBEEC2;'><td> </td><td> 13-Mar-2023 </td><td> <em>Spring Break<em> </td><td> </td></tr>
<tr style='background-color: #FBEEC2;'><td> </td><td> 15-Mar-2023 </td><td> <em>Spring Break<em> </td><td> </td></tr>
<tr><td> 18 </td><td> 20-Mar-2023 </td><td> Dynamic Programming I </td><td> </td></tr>
<tr><td> 19 </td><td> 22-Mar-2023 </td><td> Dynamic Programming II </td><td> </td></tr>
<tr><td> 20 </td><td> 27-Mar-2023 </td><td> Dynamic Programming III </td><td> hw5, hw4 <i class="fa-solid fa-calendar-check"></i> </td></tr>
<tr><td> 21 </td><td> 29-Mar-2023 </td><td> Greedy Algorithms </td><td></td></tr>
<tr style='background-color: #E0E4CC;'><td> 22 </td><td> 3-Apr-2023 </td><td> Graphs and Traversals </td><td> <i class='fa fa-map-marker' style='color: #FA6900;'></i> </td></tr>
<tr><td> 23 </td><td> 5-Apr-2023 </td><td> Graphs: spanning trees </td><td> </td></tr>
<tr><td> 24 </td><td> 10-Apr-2023 </td><td> </td><td> hw6, hw5 <i class="fa-solid fa-calendar-check"></i> </td></tr>
<tr><td> 25 </td><td> 12-Apr-2023 </td><td> </td><td> </td></tr>
<tr><td> 26 </td><td> 17-Apr-2023 </td><td> </td><td> </td></tr>
<tr><td> 27 </td><td> 19-Apr-2023 </td><td> </td><td> </td></tr>
<tr><td> 28 </td><td> 24-Apr-2023 </td><td> </td><td> hw6 <i class="fa-solid fa-calendar-check"></i> </td></tr>
<tr style='background-color: #E5DDCB;'><td> 29 </td><td> 26-Apr-2023 </td><td> Final exam </td><td> </td></tr>
<tr style='color: #ccd5d8ff;'><td> 30 </td><td> 2-May-2022 </td><td> </td><td> </td></tr>
<tr style='color: #ccd5d8ff;'><td> 31 </td><td> 4-May-2022 </td><td> </td><td> </td></tr>
</table>
</col50>
</row>
</section>
<section data-background="figures/attendance.svg" data-background-size="contain" >
</section>
<section>
<h3>Outline of the lecture</h3>
<ul>
<li class="fragment roll-in"> Introduction and history
<li class="fragment roll-in">
<li class="fragment roll-in">
<li class="fragment roll-in">
</ul>
</section>
</section>
<section>
<section data-background="figures/roman_graph.jpeg" data-background-size="cover" data-background-transition="zoom">
<h1 style="text-shadow: 10px 10px 10px #002b36; color: #fdf6e3;">Introduction</h1>
</section>
<section data-background="figures/stranger_things_map_graph.jpeg">
<ul style="text-shadow: 10px 10px 10px #002b36; color: #fdf6e3;">
<li class="fragment roll-in">Recall that a graph is a pair of sets $(V, E)$.
<li class="fragment roll-in">We call $V$ the vertices of the graph
<li class="fragment roll-in">$E$ is a set of vertex pairs which we call the edges of the
graph.
<li class="fragment roll-in">In an undirected graph, the edges are unordered pairs of
vertices and in a directed graph, the edges are ordered pairs.
<li class="fragment roll-in">We assume that there is never an edge from a vertex to itself
(no self-loops) and that there is at most one edge from any
vertex to any other (no multi-edges)
<li class="fragment roll-in">$|V|$ is the number of vertices in the graph and $|E|$ is the
number of edges
</ul>
</section>
<section>
<h3>History: Roman roads (1st century AD)</h3>
<ul>
<li class="fragment roll-in"> Roman Road Networks ($400,000$ km) - itineraria (1st century)<br>
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); width: 130%; margin-left: -150px;" class="stretch" width="120%" src="figures/roman_graph.jpeg" alt="roads">
</ul>
</section>
<section>
<h3>History: Genealogy (Romans BC, 9th century AD) </h3>
<ul>
<li style="list-style: none;"> Genealogy (legal computation in church)
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); width: 110%; margin-left: -50px; margin-top: -10px;" class="stretch" src="figures/genealogy_case.png" alt="Genealogy">
<blockquote style="background-color: #93a1a1; color: #fdf6e3; width:100%; text-align:left; font-size: 20pt; width: 110%; margin-left: -50px; margin-top: -30px;" class="fragment roll-in stretch" >
Tirius and Theburga marry and have a son Gaius, after which Tirius dies; Theburga then marries Lothar, bears him a son, and dies; finally, Lothar and Bertha marry and have a daughter Gemma. Can Gaius’s son legally marry Gemma’s daughter?<br>
</blockquote>
</ul>
</section>
<section>
<h3>History: physics</h3>
<ul>
<li class="fragment roll-in"> 1600s Pierre Varignon -<em> Maxwell-Cremona</em> diagrams
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1);" width="100%" src="figures/force_diagram.png" alt="Physics">
</ul>
</section>
<section>
<h3>Other examples</h3>
<ul>
<li class="fragment roll-in"> Board games (since antiquity)
<li class="fragment roll-in"> Convex Polyhedra
<li class="fragment roll-in"> Star patterns (East Asia 7th century CE)
<li class="fragment roll-in"> Knight's tours by al-Adli and others 9th century
<li class="fragment roll-in"> Mazes (Giovanni Fontana circa 1420)
<li class="fragment roll-in"> Path problems (Euler's Konigsburg bridges)
<li class="fragment roll-in"> Telegraph and other communication networks
<li class="fragment roll-in"> Electrical circuits
<li class="fragment roll-in"> Social networks
<li class="fragment roll-in"> Internet
</ul>
</section>
<section>
<h2>Definitions 1/4</h2>
<ul>
<li class="fragment roll-in"> A <b>graph</b> is a pair of sets $(V, E)$, where
<li class="fragment roll-in"> $V$ is an arbitrary non-empty finite set, whose elements are called <b>vertices</b> or <b>nodes</b>, and
<li class="fragment roll-in"> $E$ is a set of <em>pairs</em> of elements of $V$ called <b>edges</b>
<li class="fragment roll-in"> In an <b>undirected</b> graph edges are unordered pairs
<li class="fragment roll-in"> In a <b>directed</b> graph edges are ordered pairs $\vec{u}\rightarrow\vec{v}$
<li class="fragment roll-in"> In $\vec{u}\rightarrow\vec{v}$ we call $\vec{u}$ the <b>tail</b> and $\vec{v}$ the <b>head</b>
<li class="fragment roll-in"> How many edges are possible given $V$ vertices
<ul>
<li class="fragment roll-in"> In an <b>undirected</b> graph <span class="fragment roll-in"> $0\leq E \leq {|V| \choose 2}$</span>
<li class="fragment roll-in"> In a <b>directed</b> graph <span class="fragment roll-in"> $0\leq E \leq |V|(|V|-1)$</span>
</ul>
</ul>
</section>
<section>
<h2>Definitions 2/4</h2>
<ul>
<li class="fragment roll-in"> Nodes connected by an edge are <b>neighbors</b> also <b>adjacent</b>
<li class="fragment roll-in"> Number of neighbors of a node is its <b>degree</b>
<li class="fragment roll-in"> In $\vec{u}\rightarrow\vec{v}$ $\vec{u}$ is a <b>predecessor</b> (also <b>parent</b>) of $\vec{v}$
<li class="fragment roll-in"> In $\vec{u}\rightarrow\vec{v}$ $\vec{v}$ is a <b>successor</b> (also <b>child</b>) of $\vec{u}$
<li class="fragment roll-in"> <b>in-degree</b> of a node is its number of parents
<li class="fragment roll-in"> <b>out-degree</b> of a node is its number of children
</ul>
</section>
<section>
<h2>Definitions 3/4</h2>
<ul>
<li class="fragment roll-in"> $G^\prime = (V^\prime, E^\prime)$ is a <b>subgraph</b> of $G=(V,E)$ if $V^\prime \subseteq V$ and $E^\prime \subseteq E$
<li class="fragment roll-in"> A <b>proper subgraph</b> any $G^\prime$ subgraph of $G$, $G^\prime \ne G$
<li class="fragment roll-in"> A <b>walk</b> is a sequence of vertices where each adjacent pair is connected by an edge in $G$
<li class="fragment roll-in"> A walk is a <b>path</b> if it visits a vertex at most once
<li class="fragment roll-in"> Any $\vec{u}$ and $\vec{v}$ in $G$ are <b>reachable</b> if there's a walk between them in $G$
<li class="fragment roll-in"> An undirected graph is <b>connected</b> if every vertex is reachable from every other vertex
<li class="fragment roll-in"> <b>Components</b> are maximal connected subgraphs
</ul>
</section>
<section>
<h2>Definitions 4/4</h2>
<ul style="font-size: 26pt; margin-top: -50px;">
<li class="fragment roll-in"> A walk is <b>closed</b> if start and end points are the same
<li class="fragment roll-in"> A <b>cycle</b> is a closed walk that enters and leaves each vertex at most once
<li class="fragment roll-in"> An undirected graph is <b>acyclic</b> if no subgraph is a cycle (also called <b>forests</b>)
<li class="fragment roll-in"> A <b>tree</b> is a conected acyclic graph
<li class="fragment roll-in"> A <b>spanning tree</b> is a subgraph that is a tree that contains every node in $G$
<li class="fragment roll-in"> A <b>directed walk</b>: $v_0\rightarrow v_1\rightarrow v_2\rightarrow \cdots\rightarrow v_\ell$
<li class="fragment roll-in"> A directed graph is <b>strongly connected</b> if every vertex is reachable fron every other vertex
<li class="fragment roll-in"> An <b>acyclic</b> graph does not contain directed cycles
<li class="fragment roll-in"> Directed acyclic graphs are called <b>dags</b>
</ul>
</section>
<section data-vertical-align-top data-background="figures/planar_graph_Jeff.svg" data-background-size="contain" >
<h2>planar graphs</h2>
</section>
<section>
<h2>Planar graphs</h2>
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); width: 120%; margin-left: -50px; margin-top: -10px;" class="stretch" src="figures/planar_graph_Jeff.svg" alt="planar graphs">
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); width: 120%; margin-left: -50px; margin-top: -10px;" class="stretch" src="figures/planar_graphs_source_Jeff.svg" alt="planar graphs">
</section>
<section data-vertical-align-top data-background="figures/edit_distance_dependency_Jeff.svg" data-background-size="contain" >
<h2 class="fragment roll-in" style="text-shadow: 10px 10px 10px #002b36; color: #fdf6e3;">Edit distance: dependency graph</h2>
</section>
<section data-vertical-align-top data-background="figures/Hanoi_tower_graph_Jeff.svg" data-background-size="contain" >
<h2 class="fragment roll-in">Hanoi tower: board game graph</h2>
</section>
</section>
<section>
<section data-background="figures/colorful_graph.png" data-background-size="contain">
<h1 style="text-shadow: 10px 10px 10px #002b36; color: #fff3e3;">Data Structures</h1>
</section>
<section data-vertical-align-top data-background="figures/adjacency_list_example1_Jeff.svg" data-background-size="contain" >
<h2 class="fragment roll-in">Adjacency list</h2>
<div class="slide-footer">
"Attentive students might notice that despite is name, an adjacency list is not a list. This nomenclature is an example of the Red Herring Principle: In computer science, as in mathematics, a red herring is neither necessarily red nor necessarily a fish." Jeff Erickson
</div>
</section>
<section data-vertical-align-top data-background="figures/adjacency_array_Jeff.svg" data-background-size="contain" >
<h2 class="fragment roll-in">Adjacency array</h2>
</section>
<section data-vertical-align-top data-background="figures/adjacency_matrix_Jeff.svg" data-background-size="contain" >
<h2 class="fragment roll-in">Adjacency matrix</h2>
</section>
<section data-vertical-align-top data-background="figures/computational_complexity_list_vs_matrix.svg" data-background-size="contain" >
<h2 class="fragment roll-in">Comparison</h2>
</section>
</section>
<section>
<section data-background="figures/depth_and_breadth2.png" data-background-size="contain">
<h1 style="margin-left: -200px; width: 80%;">Whatever first search</h1>
</section>
<section data-vertical-align-top data-background="figures/dfs_search_Jeff.svg" data-background-size="contain" >
<h2 class="fragment roll-in">depth first search</h2>
</section>
<section>
<h3>depth first search (pseudo)code</h3>
<pre class="python" style="width: 100%; font-size: 18pt;"><code data-trim data-noescape data-line-numbers>
def rec_dfs(G, s, S=None):
if S is None: S = set() # Initialize the history
S.add(s) # We've visited s
for u in G[s]: # Explore neighbors
if u in S: continue # Already visited: Skip
rec_dfs(G, u, S) # New: Explore recursively
return S # For testing
</code></pre>
<pre class="python fragment roll-in" style="width: 100%; font-size: 18pt;"><code data-trim data-noescape data-line-numbers>
def iter_dfs(G, s):
S, Q = set(), [] # Visited-set and queue
Q.append(s) # We plan on visiting s
while Q: # Planned nodes left?
u = Q.pop() # Get one
if u in S: continue # Already visited? Skip it
S.add(u) # We've visited it now
Q.extend(G[u]) # Schedule all neighbors
yield u # Report u as visited
</code></pre>
</section>
<section data-vertical-align-top data-background="figures/whatever_first_search_Jeff.svg" data-background-size="contain" >
</section>
<section>
<h2>whatever first search (pseudo)code</h2>
<row>
<col60>
<pre class="python fragment roll-in" style="width: 100%; font-size: 18pt;"><code data-trim data-noescape data-line-numbers>
def whateverfirst(G, s, qtype=set):
S, Q = set(), qtype()
Q.add(s)
while Q:
u = Q.pop()
if u in S: continue
S.add(u)
for v in G[u]:
Q.add(v)
yield u
</code></pre>
</col60>
<col40 class="fragment roll-in">
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); width: 100%;" class="stretch" src="figures/whatever_first_search_Jeff.svg" alt="planar graphs">
</col40>
</row>
</section>
<section>
<h2></h2>
<blockquote style="background-color: #93a1a1; color: #fdf6e3; font-size: 42px; width: 100%; text-align: left" class="fragment roll-in"><b>Lemma</b> <code>WhateverFirstSearch(s)</code> marks every vertex reachable from $s$ and only those vertices. The set of all pairs $(v,\mbox{parent}(v))$ with $\mbox{parent}(v) \ne \emptyset$ defines a spanning tree of the component containing $s$. </blockquote>
<div class="fragment roll-in">
<blockquote style="text-align: left; background-color: #93a1a1; color: #fdf6e3; font-size: 30px; width: 100%; margin-bottom: -20px;"><i class="fa-regular fa-square"></i><b>Proof sketch</b></blockquote>
<blockquote style="background-color: #eee8d5; width: 100%; font-size: 36px;">
<ul>
<li class="fragment roll-in"> Argue by induction on the shortest-path distance from $s$ to $v$ that the algorithm marks every node.
<li class="fragment roll-in"> Prove by induction on the order in which vertices are marked the every $v$ can be traced to $s$ by going back to the parent.
<li class="fragment roll-in"> Every node except $s$ has a unique parent, $E = V - 1$, which means it is a tree.
</ul>
</blockquote>
</div>
</section>
<section data-vertical-align-top data-background="figures/whatever_first_visit_all_Jeff.svg" data-background-size="contain" >
</section>
<section>
<h2>Analysis</h2>
<ul>
<li class="fragment roll-in"> Runtime depends on the data structure
<li class="fragment roll-in"> Let $T$ be the time to ins./del. an item in/from a bag
<li class="fragment roll-in"> For loop executes exactly once for each marked vertex, at most $V$ times ($\dagger$)
<li class="fragment roll-in"> Each edge is put in the bag either once in a <b>directed</b> graph or twice in an <b>undirected</b> ($\star\star$)
<li class="fragment roll-in"> Cannot take more from bag that we put in ($\star$), i.e. at most $2E+1$ times
<li class="fragment roll-in"> $O(V+ET)$
</ul>
</section>
<section>
<h2>Whatever first variants</h2>
<row>
<col60>
<pre class="python fragment roll-in" style="width: 98%; font-size: 18pt;"><code data-trim data-noescape data-line-numbers>
def whateverfirst(G, s, qtype=set):
S, Q = set(), qtype()
Q.add(s)
while Q:
u = Q.pop()
if u in S: continue
S.add(u)
for v in G[u]:
Q.add(v)
yield u
</code></pre>
<ul>
<li class="fragment roll-in"> Stack: depth-first search
<li class="fragment roll-in"> Queue: breadth-first search
<li class="fragment roll-in"> Priority queue: best-first search
</ul>
</col60>
<col40>
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); width: 100%;" class="stretch" src="figures/depth_and_breadth2_column.png" alt="planar graphs">
</col40>
</row>
</section>
<section data-vertical-align-top data-background="figures/dfs_bfs_example.svg" data-background-size="contain" >
<h2 class="fragment roll-in">whatever first</h2>
</section>
</section>
<section>
<section data-background="figures/spanning_tree_transparent.gif" data-background-size="cover">
<h1 style="text-shadow: 10px 10px 10px #002b36; color: #fdf6e3;">Minimum Spanning Trees</h1>
</section>
<section>
<h2>more definitions</h2>
<ul>
<li class="fragment roll-in">A <b>cycle</b> is a path that starts and ends at the same vertex
and has at least one edge
<li class="fragment roll-in">A graph is <b>acyclic</b> if no subgraph is a cycle. Acyclic graphs
are also called <b>forests</b>
<li class="fragment roll-in">A <b>tree</b> is a connected acyclic graph. It’s also a connected
component of a forest.
<li class="fragment roll-in">A <b>spanning tree</b> of a graph $G$ is a
subgraph that is a tree and also contains every vertex of $G$. A graph
can only have a spanning tree if it’s connected
<li class="fragment roll-in">A <b>spanning forest</b> of $G$ is a collection of spanning trees, one
for each connected component of $G$
</ul>
</section>
<section>
<h2>Minimum spanning tree problem</h2>
<ul>
<li class="fragment roll-in">Suppose we are given a connected, undirected weighted graph
<li class="fragment roll-in">That is a graph $G = (V, E)$ together with a function $w : E \rightarrow \RR$ that assigns a weight $w(e)$ to each edge $e$. (We assume
the weights are real numbers)
<li class="fragment roll-in">Our task is to find the <b>minimum spanning tree</b> of $G$, i.e., the
spanning tree $T$ minimizing the function
$$
w(T) = \underset{e\in T}{\sum}w(e)
$$
</ul>
</section>
<section data-background="figures/MST_JeffE.svg" data-background-size="contain">
</section>
<section>
<h2>Generic <alert>MST</alert> Algorithm</h2>
<img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1); width: 130%; margin-left: -150px;" class="stretch" width="120%" src="figures/generic_MST.png" alt="roads">
</section>
<section>
<h2>Safe Edges</h2>
<ul>
<li class="fragment roll-in">A <em>cut$(S, V − S)$</em> of a graph $G = (V, E)$ is a partition of $V$
<li class="fragment roll-in">An <em>edge</em>$(u, v)$ crosses the cut$(S, V −S)$ if one of its endpoints
is in $S$ and the other is in $V − S$
<li class="fragment roll-in">A cut respects a set of edges $A$ if no edge in $A$ crosses the
cut.
<li class="fragment roll-in">An edge is a <em>light edge</em> crossing
a cut if its weight is the minimum of any edge crossing the cut
</ul>
</section>
<section>
<blockquote style="background-color: #93a1a1; color: #fdf6e3; font-size: 42px; width: 100%; text-align: left" class="fragment roll-in"><b>Theorem</b> Let $G = (V, E)$ be a connected, undirected graph with a realvalued weight function $w$ defined on $E$. Let $A$ be a subset of
$E$ that is included in some minimum spanning tree for $G$. Let
$(S, V − S)$ be any cut of $G$ that respects $A$ and let $(u, v)$ be a
light edge crossing $(S, V − S)$. Then edge $(u, v)$ is safe for $A$
</blockquote>
</section>
<section>
<blockquote style="background-color: #93a1a1; color: #fdf6e3; font-size: 42px; width: 100%; text-align: left" class="fragment roll-in"><b>Corollary</b> Let $G = (V, E$) be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of
$E$ that is included in some minimum spanning tree for $G$, and
let $C = (V_c, E_c)$ be a connected component (tree) in the forest
$G_A = (V, A)$. If $(u, v)$ is a light edge connecting $C$ to some other
component in $G_A$, then $(u, v)$ is safe for $A$
</blockquote>
<blockquote style="text-align: left; background-color: #93a1a1; color: #fdf6e3; font-size: 30px; width: 100%; margin-bottom: -20px;"><i class="fa-regular fa-square"></i><b>Proof</b></blockquote>
<blockquote style="background-color: #eee8d5; width: 100%; font-size: 36px;">
<ul>
<li class="fragment roll-in"> The cut $(V_C , V − V_C )$
respects $A$, and $(u, v)$ is a light edge for this cut. Therefore
$(u, v)$ is safe for $A$.
</ul>
</blockquote>
</section>
<section>
<h2>Two MST algorithms</h2>
<ul>
<li class="fragment roll-in">There are two major MST algorithms, Kruskal’s and Prim’s
<li class="fragment roll-in">In Kruskal’s algorithm, the set $A$ is a forest. The safe edge
added to $A$ is always a least-weighted edge in the graph that
connects two distinct components
<li class="fragment roll-in">In Prim’s algorithm, the set $A$ forms a single tree. The safe
edge added to $A$ is always a least-weighted edge connecting
the tree to a vertex not in the tree
</ul>
</section>
<section>
<h2>Kruskal's algorithm</h2>
<ul>
<li class="fragment roll-in">Q: In Kruskal’s algorithm, how do we determine whether or
not an edge connects two distinct connected components?
<li class="fragment roll-in">A: We need some way to keep track of the sets of vertices
that are in each connected components and a way to take
the union of these sets when adding a new edge to A merges
two connected components
<li class="fragment roll-in">What we need is the data structure for maintaining disjoint
sets (aka Union-Find)
</ul>
</section>
<section>
<pre class="python stretch" style="width: 100%; font-size: 18pt;" class="stretch"><code data-trim data-noescape data-line-numbers>
def find(C, u):
if C[u] != u:
C[u] = find(C, C[u]) # Path compression
return C[u]
def union(C, R, u, v):
u, v = find(C, u), find(C, v)
if R[u] > R[v]: # Union by rank
C[v] = u
else:
C[u] = v
if R[u] == R[v]: # A tie: Move v up a level
R[v] += 1
def kruskal(G):
E = [(G[u][v],u,v) for u in G for v in G[u]]
T = set()
C, R = {u:u for u in G}, {u:0 for u in G} # Comp. reps and ranks
for _, u, v in sorted(E):
if find(C, u) != find(C, v):
T.add((u, v))
union(C, R, u, v)
return T
</code></pre>
</section>
<section data-background="figures/kruskal_example_JeffE.svg" data-background-size="contain">
</section>
<section>
<h2>Correctness?</h2>
<ul>
<li class="fragment roll-in">Correctness of Kruskal’s algorithm follows immediately from
the corollary
<li class="fragment roll-in">Each time we add the lightest weight edge that connects two
connected components, hence this edge must be safe for $A$
<li class="fragment roll-in">This implies that at the end of the algorith, $A$ will be a MST
</ul>
</section>
<section>
<h2>Runtime?</h2>
<ul>
<li class="fragment roll-in">The runtime fo the Kruskal’s algorithm will depend on the implementation of the disjoint-set data structure. We’ll assume
the implementation with union-by-rank and path-compression which has amortized cost of $\log^∗ n$
</ul>
</section>
<section>
<h2>Runtime?</h2>
<ul>
<li class="fragment roll-in">Time to sort the edges is $O(|E| \log |E|)$
<li class="fragment roll-in">Total amount of time for the $|V|$ Make-Sets and up to $|E|$ Set-Unions is $O((|V | + |E|) log^∗ |V |)$
<li class="fragment roll-in">Since $G$ is connected, $|E| \geq |V|−1$ and so $O((|V|+|E|) log^∗ |V|) = O(|E|\log|E|)$
<li class="fragment roll-in">Total amount of additional work done in the for loop is just $O(E)$
<li class="fragment roll-in">Thus total runtime is $O(|E|\log|E|)$
<li class="fragment roll-in">Since $|E|\leq |V|^2$, we can rewrite as $O(|E|\log|V|)$
</ul>
</section>
<section>
<h2></h2>
<ul>
</ul>
</section>
<section>
<h2></h2>
<ul>
</ul>
</section>
<section>
<h2></h2>
<ul>
</ul>
</section>
<section>
<h2></h2>
<ul>
</ul>
</section>
<section>
<h2></h2>
<ul>
</ul>
</section>
<section>
<h2></h2>
<ul>
</ul>
</section>
</section>
<section>
<h2>See you</h2>
Monday April $18^{th}$
</section>
</div>
</div>
<script src="dist/reveal.js"></script>
<!-- <link rel="stylesheet" href="lib/css/monokai.css"> -->
<script src="plugin/highlight/highlight.js"></script>
<script src="plugin/math/math.js"></script>
<script src="plugin/chalkboard/plugin.js"></script>
<script src="plugin/notes/notes.js"></script>
<script src="plugin/zoom/zoom.js"></script>
<script src="plugin/menu/menu.js"></script>
<script type="text/javascript">
// Event start load section on slide
Reveal.addEventListener('slidechanged', function(event) {
//-- check if current slide with code
var sectionID = Reveal.getCurrentSlide().id;
if(sectionID === "code.1") {
document.getElementById("div4code.1").style.display = "block";
} else {
document.getElementById("div4code.1").style.display = "none"
}
});
</script>
<script>
// Full list of configuration options available at:
// https://github.com/hakimel/reveal.js#configuration
let notes = document.querySelectorAll('aside.notes');
notes.forEach(n => {
let html = n.innerHTML;
html = html.trim().replace(/\n/g, '<br/>');
n.innerHTML = html;
});
Reveal.initialize({
// history: true,
hash: true,
margin: 0.01,
minScale: 0.01,
maxScale: 1.23,
menu: {
themes: true,
openSlideNumber: true,
openButton: false,
},
customcontrols: {
slideNumberCSS : 'position: fixed; display: block; right: 90px; top: auto; left: auto; width: 50px; bottom: 30px; z-index: 31; font-family: Helvetica, sans-serif; font-size: 12px; line-height: 1; padding: 5px; text-align: center; border-radius: 10px; background-color: rgba(128,128,128,.5)',
controls: [
{ icon: '<i class="fa fa-caret-left"></i>',
css: 'position: fixed; right: 60px; bottom: 30px; z-index: 30; font-size: 24px;',
action: 'Reveal.prev(); return false;'
},
{ icon: '<i class="fa fa-caret-right"></i>',
css: 'position: fixed; right: 30px; bottom: 30px; z-index: 30; font-size: 24px;',
action: 'Reveal.next(); return false;'
}
]
},
chalkboard: {
boardmarkerWidth: 1,
chalkWidth: 2,
chalkEffect: 1,
slideWidth: Reveal.width,
slideHeight: Reveal.height,
toggleNotesButton: false,
toggleChalkboardButton: false,
//src: "chalkboards/chalkboard_em2.json",
readOnly: false,
theme: "blackboard",
eraser: { src: "plugin/chalkboard/img/sponge.png", radius: 30},
},
math: {
mathjax: 'https://cdn.jsdelivr.net/gh/mathjax/[email protected]/MathJax.js',
config: 'TeX-AMS_SVG-full',
// pass other options into `MathJax.Hub.Config()`
TeX: {
Macros: {
RR: '\\mathbb{R}',
PP: '\\mathbb{P}',
EE: '\\mathbb{E}',
NN: '\\mathbb{N}',
vth: '\\vec{\\theta}',
loss: '{\\cal l}',
hclass: '{\\cal H}',
CD: '{\\cal D}',
def: '\\stackrel{\\text{def}}{=}',
pag: ['\\text{pa}_{{\cal G}^{#1}}(#2)}', 2],
vec: ['\\boldsymbol{\\mathbf #1}', 1],
set: [ '\\left\\{#1 \\; : \\; #2\\right\\}', 2 ],
bm: ['\\boldsymbol{\\mathbf #1}', 1],
argmin: ['\\operatorname\{arg\\,min\\,\}'],
argmax: ['\\operatorname\{arg\\,max\\,\}'],
prob: ["\\mbox{#1$\\left(#2\\right)$}", 2],
floor: ["\\lfloor #1 \\rfloor",1]
},
loader: {load: ['[tex]/color']},
extensions: ["color.js"],
tex: {packages: {'[+]': ['color']}},
svg: {
fontCache: 'global'
}
}
},
plugins: [ RevealMath, RevealChalkboard, RevealHighlight, RevealNotes, RevealZoom, RevealMenu ],
});
Reveal.configure({ fragments: true }); // set false when developing to see everything at once
Reveal.configure({ slideNumber: true });
//Reveal.configure({ history: true });
Reveal.configure({ slideNumber: 'c / t' });
Reveal.addEventListener( 'darkside', function() {
document.getElementById('theme').setAttribute('href','dist/theme/aml_dark.css');
}, false );
Reveal.addEventListener( 'brightside', function() {
document.getElementById('theme').setAttribute('href','dist/theme/aml.css');
}, false );
</script>
<style type="text/css">
/* 1. Style header/footer <div> so they are positioned as desired. */
#header-left {
position: absolute;
top: 0%;
left: 0%;
}
#header-right {
position: absolute;
top: 0%;
right: 0%;
}
#footer-left {
position: absolute;
bottom: 0%;
left: 0%;
}
</style>
<!-- // 2. Create hidden header/footer -->
<div id="hidden" style="background; display:none;">
<div id="header">
<div id="header-left"><h4>CS4520</h4></div>
<div id="header-right"><h4>Algorithms</h4></div>
<div id="footer-left">
<!-- <img style="border:0; box-shadow: 0px 0px 0px rgba(150, 150, 255, 1);" width="100" -->
<!-- src="figures/flowchart.png" alt="robot learning"> -->
</div>
</div>
</div>
<script type="text/javascript">
// 3. On Reveal.js ready event, copy header/footer <div> into each `.slide-background` <div>
var header = $('#header').html();
if ( window.location.search.match( /print-pdf/gi ) ) {
Reveal.addEventListener( 'ready', function( event ) {
$('.slide-background').append(header);
});
}
else {
$('div.reveal').append(header);
}
</script>
</body>
</html>