-
Notifications
You must be signed in to change notification settings - Fork 45
/
Copy pathalgorithm.html
1507 lines (1367 loc) · 62.7 KB
/
algorithm.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
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Algorithm Design Techniques - The Checklist</title>
<link href="https://api.fontshare.com/v2/css?f[]=nunito@400&f[]=bebas-neue@400&display=swap" rel="stylesheet">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.3/css/all.min.css"
integrity="sha512-iBBXm8fW90+nuLcSKlbmrPcLa0OT92xO1BIsZ+ywDWZCvqsWgccV3gFoRBv0z+8dLJgyAHIhR35VZc2oM/gI1w=="
crossorigin="anonymous" referrerpolicy="no-referrer" />
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css">
<link rel="icon" href="./resources/Yellow Abstract Cooking Fire Free Logo.png" />
<link rel="stylesheet" href="styles.css">
<link rel="stylesheet" href="dark-mode.css">
<link rel="stylesheet"
href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.4.0/styles/atom-one-dark.min.css" />
<link rel="stylesheet" href="scrollbar.css">
</head>
<body>
<header>
<h1>
<a href="index.html">The Checklist</a>
</h1>
</header>
<nav>
<!-- may use this thing later -->
<!-- <ul><li><a href="checklist1.html">Checklist 1</a></li><li><a href="checklist2.html">Checklist 2</a></li></ul> -->
<!-- Add more checklists here -->
<!-- dark mode elements -->
<button class="dark-mode-toggle">
<i class="sun-icon"></i>
<i class="moon-icon"></i>
</button>
</nav>
<main>
<section class="checklist">
<h2>Algorithm Design Techniques</h2>
<ul>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<!-- section start -->
<div class="section-title">
<label class="section-title-label"> What are the various algorithm design techniques? <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<ul>
<li>Brute Force</li>
<li>Greedy Algorithms</li>
<li>Divide-and-Conquer, Decrease-and-Conquer</li>
<li>Dynamic Programming</li>
<li>Reduction / Transform-and-Conquer</li>
<li>Backtracking and Branch-and-Bounding</li>
</ul>
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Brute Force Algorithm <span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu --> The brute force algorithm is an approach that comes directly
to our minds after viewing a problem. This is usually a straightforward approach based on the problem
statement. We could use this approach to solve problems with small-sized datasets. Let me give you an
example. Let's say you want to find the shortest path from your home to your school. The brute force
solution in this case would be to consider every possible combination of roads and intersections to reach
your destination. However, this method is highly inefficient, especially if there are a lot of roads.
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Examples of Brute force algorithms <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<ul>
<li>Bubble-Sort</li>
<li>Selection-Sort</li>
<li>Sequential search in an array</li>
<li>Computing pow(a, n) by multiplying a, n times</li>
<li>Convex hull problem</li>
<li>String matching</li>
<li>Exhaustive search: Travelling salesman, Knapsack</li>
</ul>
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Greedy Algorithm <span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu --> Greedy algorithms are used to solve optimization problems.
These problems usually involve finding the maximum or minimum of something from the given data. In a greedy
algorithm, we find the solution through a sequence of steps. At each step, a choice is made that is locally
optimal. What does "locally optimal" mean? First, we take a small part of the provided data, and then we
find the optimal solution within that data. After that, we'll again take some data and repeat the process.
Finding the optimal solution within the data we've considered is called locally optimal.
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Some examples of greedy algorithms <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<ul>
<li>Minimal spanning tree: Prim's algorithm, Kruskal's algorithm</li>
<li>Dijkstra's algorithm for the single-source shortest path problem</li>
<li>Greedy algorithm for the Knapsack problem</li>
<li>The coin exchange problem</li>
<li>Huffman trees for optimal encoding</li>
</ul>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Divide-and-Conquer, Decrease-and-Conquer <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p>
<strong>Divide-and-Conquer Algorithms:</strong>
</p>
<ol>
<li> First, we divide the problem into similar subproblems. </li>
<li> Then, we solve each one of these subproblems individually. </li>
<li> Finally, we combine the results of the subproblems to produce the desired result. </li>
</ol>
<p>
<strong>Divide-and-Conquer vs. Decrease-and-Conquer:</strong>
</p>
<p> In divide and conquer, the size of the problem is reduced by a factor (half, one third, etc.), while in
decrease and conquer, the size of the problem is reduced by a constant. </p>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Some examples of divide-and-conquer algorithms <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<ol>
<li>Merge-Sort algorithm (using recursion)</li>
<li>Quick Sort algorithm (using recursion)</li>
<li>Computing the length of the longest path in a binary tree (using recursion)</li>
<li>Computing Fibonacci numbers (using recursion)</li>
<li>Quick-Hull</li>
</ol>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Some examples of decrease-and-conquer algorithms <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text"> JavaScript is a programming language that adds interact <ol>
<li>Computing pow(a, n) by calculating pow(a, n/2) using recursion.</li>
<li>Binary search in a sorted list (using recursion)</li>
<li>Searching in BST</li>
<li>Insertion-Sort</li>
<li>Graph traversal algorithms (DFS and BFS)</li>
<li>Topological sort</li>
<li>Warshall’s algorithm (using recursion)</li>
<li>Permutations (Minimal change approach, Johnson-Trotter algorithm)</li>
<li>Computing a median</li>
<li>Topological sorting</li>
<li>Fake-coin problem (Ternary search)</li>
</ol>ivity and functionality to web pages, enabling features like forms and animations. </div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Dynamic Programming <span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p>
<strong>Divide and Conquer:</strong>
</p>
<p> In divide and conquer, many times the recursively solved subproblems can result in the same computation
being performed multiple times. This problem arises when identical problems occur repeatedly in a
recursion. </p>
<p>
<strong>Dynamic Programming:</strong>
</p>
<p> Dynamic programming is used to avoid this issue by storing the results of subproblems in a table and
referring to that table to check if we have already calculated the solution to a subproblem before
computing it again. </p>
<p> Dynamic programming is a bottom-up technique in which the smaller subproblems are solved first, and the
results of these are used to find the solution for larger subproblems. </p>
</li>
<!-- Add more Web Development here -->
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Some examples of Dynamic programming are: <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<ol>
<li>Fibonacci numbers computed by iteration.</li>
<li>Warshall's algorithm for transitive closure implemented by iterations.</li>
<li>Floyd's algorithm for all-pairs shortest paths.</li>
</ol>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Reduction / Transform-and-Conquer <span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> These methods work as a two-step process. First, the problem is transformed into a different problem
that is already known to us, i.e., a problem for which we already know the optimal solution. Then the
problem is solved. </p>
<p> The most common type of transformation is the sorting of an array. </p>
<p> For example, in a given list of numbers, find the two closest numbers. In the brute-force solution, we
would find the distance between each element in the array and keep track of the pair with the minimum
distance. In this approach, the total time complexity is O(n^2). In the Transform and Conquer solution, we
first sort the array in O(n log n) time and then find the closest numbers by scanning the array in another
single pass with time complexity O(n). Thus, the total time complexity is O(n log n). </p>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Some examples of Transform and Conquer <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<ol>
<li>Gaussian elimination</li>
<li>Heaps and Heapsort</li>
</ol>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Backtracking <span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> Have you seen the modern lock with a 3-digit password, where the numbers range from 1 to 9? If you don't
have the exact password for the lock, you need to test every combination until you find the right one. You
would go from something like "111" to "112" and so on until you reach "999". In this case, what you are
doing is called backtracking. </p>
<p> Suppose the lock produces a click sound anytime you come across a correct digit. If we can listen to
this sound, it will help you reach the goal much faster. These functions are called Pruning functions or
Bounding functions. </p>
<p> Backtracking is a method in which a solution is found by searching through a large but finite number of
states. With some pruning or bounding functions, we can narrow down our search. </p>
<p> For all problems (like NP-hard problems) for which there does not exist any other efficient algorithm,
we use the backtracking algorithm. </p>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Components of backtracking problems <span
class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p>
<strong>Key Components of the Algorithm:</strong>
</p>
<ul>
<li>Initial state</li>
<li>Target/Goal state</li>
<li>Intermediate states</li>
<li>Path from the initial state to the target/goal state</li>
<li>Operators to get from one state to another</li>
<li>Pruning function (optional)</li>
</ul>
<p> The algorithm starts with the construction of a state tree, whose nodes represent the states. The root
node is the initial state, and one or more leaf nodes will be our target state. Each edge of the tree
represents some operation. The solution is obtained by searching the tree until a target is found. </p>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Some real-life problems where you could use the backtracking approach
<span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p>
<strong>Three Monks and Three Demons:</strong>
</p>
<p> There are three monks and three demons on one side of a river. You want to move all of them to the other
side using a small boat. The boat can carry only two persons at a time. If, on any shore, the number of
demons is more than the number of monks, the demons will eat the monks. How can we move all of these
people to the other side of the river safely? </p>
<p>
<strong>The Farmer's Dilemma:</strong>
</p>
<p> There is a farmer who has a goat, a cabbage, and a wolf. If the farmer leaves the goat with the cabbage,
the goat will eat the cabbage. If the farmer leaves the wolf alone with the goat, the wolf will kill the
goat. How can the farmer move all his belongings to the other side of the river? </p>
<p>
<strong>Jug Problem:</strong>
</p>
<p> You are given two jugs, a 4-gallon one and a 3-gallon one. There are no measuring markers on the jugs. A
tap can be used to fill the jugs with water. How can you get 2 gallons of water in the 4-gallon jug? </p>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Branch-and-bound <span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<p> The branch and bound method is used when we can evaluate the cost of visiting each node using a utility
function. At each step, we choose the node with the lowest cost to proceed further. Branch-and-bound
algorithms are implemented using a priority queue. In branch and bound, we traverse the nodes in a
breadth-first manner. </p>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> A* Algorithm <span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> A* is an extension of the branch and bound approach. In A*, we select the path with the shortest length
from the start to the goal. The total length is estimated as the length traversed so far plus a heuristic
estimate of the remaining distance from the goal. </p>
<p> Branch-and-bound will always find an optimal solution, which is the shortest path. A* will also find an
optimal solution if the heuristic is accurate. Choosing a good heuristic is the most crucial aspect of the
A* algorithm. </p>
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> 0/1 Knapsack Problem<span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> Given N items where each item has some weight and profit associated with it and also given a bag with
capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag
such that the sum of profits associated with them is the maximum possible.
<br>
<strong>Note</strong>: The constraint here is we can either put an item completely into the bag or cannot
put it at all [It is not possible to put a part of an item into the bag].
</p>
<pre style="text-align: left">
<code>
/* A Naive recursive implementation of
0-1 Knapsack problem */
#include <bits/stdc++.h>
using namespace std;
// A utility function that returns
// maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Returns the maximum value that
// can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more
// than Knapsack capacity W, then
// this item cannot be included
// in the optimal solution
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
// Driver code
int main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);
cout << knapSack(W, weight, profit, n);
return 0;
}
</code>
</pre>
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Knapsack fractional Problem<span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> Given the weights and profits of N items, in the form of {profit, weight} put these items in a knapsack
of capacity W to get the maximum total profit in the knapsack. In Fractional Knapsack, we can break items
for maximizing the total value of the knapsack.
<br>
<pre style="text-align: left">
<code>
// C++ program to solve fractional Knapsack Problem
#include <bits/stdc++.h>
using namespace std;
// Structure for an item which stores weight and
// corresponding value of Item
struct Item {
int profit, weight;
// Constructor
Item(int profit, int weight)
{
this->profit = profit;
this->weight = weight;
}
};
// Comparison function to sort Item
// according to profit/weight ratio
static bool cmp(struct Item a, struct Item b)
{
double r1 = (double)a.profit / (double)a.weight;
double r2 = (double)b.profit / (double)b.weight;
return r1 > r2;
}
// Main greedy function to solve problem
double fractionalKnapsack(int W, struct Item arr[], int N)
{
// Sorting Item on basis of ratio
sort(arr, arr + N, cmp);
double finalvalue = 0.0;
// Looping through all items
for (int i = 0; i < N; i++) {
// If adding Item won't overflow,
// add it completely
if (arr[i].weight <= W) {
W -= arr[i].weight;
finalvalue += arr[i].profit;
}
// If we can't add current Item,
// add fractional part of it
else {
finalvalue
+= arr[i].profit
* ((double)W / (double)arr[i].weight);
break;
}
}
// Returning final value
return finalvalue;
}
// Driver code
int main()
{
int W = 50;
Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << fractionalKnapsack(W, arr, N);
return 0;
}
</code>
</pre>
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label"> Matrix Chain Multiplication<span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> Given the dimension of a sequence of matrices in an array arr[], where the dimension of the ith matrix
is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices together
such that the total number of element multiplications is minimum.
<br>
<pre style="text-align: left">
<code>
#include <bits/stdc++.h>
using namespace std;
// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1 . . . n
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int mini = INT_MAX;
int count;
// Place parenthesis at different places
// between first and last matrix,
// recursively calculate count of multiplications
// for each parenthesis placement
// and return the minimum count
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
mini = min(count, mini);
}
// Return minimum count
return mini;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, N - 1);
return 0;
}
</code>
</pre>
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label">Fenwick Tree<span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure used for efficiently
performing two primary operations on an array of values: updating a value and calculating the prefix sum
(cumulative sum) of a range of values. It was developed by Peter Fenwick in 1994 and is particularly
useful when you need to frequently update elements in an array and calculate cumulative sums or ranges.
<br>
<pre style="text-align: left">
<code>
// C++ code to demonstrate operations of Binary Index Tree
#include <iostream>
using namespace std;
/* n --> No. of elements present in input array.
BITree[0..n] --> Array that represents Binary Indexed Tree.
arr[0..n-1] --> Input array for which prefix sum is evaluated. */
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum(int BITree[], int index)
{
int sum = 0; // Initialize result
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse ancestors of BITree[index]
while (index>0)
{
// Add current element of BITree to sum
sum += BITree[index];
// Move index to parent node in getSum View
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val)
{
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse all ancestors and add 'val'
while (index <= n)
{
// Add 'val' to current node of BI Tree
BITree[index] += val;
// Update index to that of parent in update View
index += index & (-index);
}
}
// Constructs and returns a Binary Indexed Tree for given
// array of size n.
int *constructBITree(int arr[], int n)
{
// Create and initialize BITree[] as 0
int *BITree = new int[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;
// Store the actual values in BITree[] using update()
for (int i=0; i<n; i++)
updateBIT(BITree, n, i, arr[i]);
// Uncomment below lines to see contents of BITree[]
//for (int i=1; i<=n; i++)
// cout << BITree[i] << " ";
return BITree;
}
// Driver program to test above functions
int main()
{
int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(freq)/sizeof(freq[0]);
int *BITree = constructBITree(freq, n);
cout << "Sum of elements in arr[0..5] is "
<< getSum(BITree, 5);
// Let use test the update operation
freq[3] += 6;
updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[]
cout << "\nSum of elements in arr[0..5] after update is "
<< getSum(BITree, 5);
return 0;
}
</code>
</pre>
</div>
</li>
<li class="checklist-item">
<div class="section">
<div class="section-box">
<label class="section-box-label">
<input type="checkbox" class="checkbox" data-checklist="web-app">
<span class="checkmark"></span>
</label>
</div>
<div class="section-title">
<label class="section-title-label">Bellman ford Algorithm<span class="dropdown-arrow"></span>
</label>
</div>
</div>
<div class="hidden-text">
<!-- Hidden content for the drop-down menu -->
<p> The Bellman-Ford algorithm is a single-source shortest path algorithm used to find the shortest paths
from a source vertex to all other vertices in a weighted, directed graph, including graphs with negative
edge weights. It was developed by Richard Bellman and Lester Ford in the 1950s. This algorithm is more
versatile than Dijkstra's algorithm since it can handle graphs with negative edge weights and detect the
presence of negative cycles.
<br>
<pre style="text-align: left">
<code>
// A C++ program for Bellman-Ford's single source
// shortest path algorithm.
#include <bits/stdc++.h>
using namespace std;
// a structure to represent a weighted edge in graph
struct Edge {
int src, dest, weight;
};
// a structure to represent a connected, directed and
// weighted graph
struct Graph {
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges.
struct Edge* edge;
};
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple
// shortest path from src to any other vertex can have
// at-most |V| - 1 edges
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX
&& dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX
&& dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return; // If negative cycle is detected, simply
// return
}
}
printArr(dist, V);
return;
}
// Driver's code
int main()
{
/* Let us create the graph given in above example */
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
// add edge 1-4 (or B-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
// Function call
BellmanFord(graph, 0);
return 0;