Skip to content

Commit e8410c9

Browse files
lijqhslijqhs
committed
update notes Mon Jun 20 18:14:58 EDT 2022
1 parent 947d39b commit e8410c9

File tree

7 files changed

+920
-21
lines changed

7 files changed

+920
-21
lines changed

‎.gitignore

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
*.war
1616
*.nar
1717
*.ear
18-
*.zip
18+
# *.zip
1919
*.tar.gz
2020
*.rar
2121

‎part-I/readme.md

Lines changed: 171 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -524,6 +524,14 @@ Examples of data structures developed in the book [*Algorithms, 4th Edition, Rob
524524
| ternary search trie | 5.3 | TST | three links per node |
525525

526526

527+
528+
<br/>
529+
<div align="right">
530+
<b><a href="#top">↥ back to top</a></b>
531+
</div>
532+
<br/>
533+
534+
527535
### 2.3. Analysis of Algorithms
528536

529537
**Reasons to analyze algorithms**:
@@ -597,6 +605,14 @@ Total memory usage for a data type value:
597605

598606
*Deep memory usage*: If array entry or instance variable is a reference, add memory (recursively) for referenced object.
599607

608+
609+
<br/>
610+
<div align="right">
611+
<b><a href="#top">↥ back to top</a></b>
612+
</div>
613+
<br/>
614+
615+
600616
### 2.4. Union-Find
601617

602618
We shall consider three different implementations, all based on using the site-indexed `id[]` array, to determine whether two sites are in the same connected component.
@@ -832,6 +848,14 @@ private static void exch(Comparable[] a, int i, int j)
832848

833849
See more: [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms).
834850

851+
852+
<br/>
853+
<div align="right">
854+
<b><a href="#top">↥ back to top</a></b>
855+
</div>
856+
<br/>
857+
858+
835859
### 3.1. Selection sort
836860

837861
- In iteration `i`, find index min of smallest remaining entry.
@@ -873,6 +897,14 @@ public class Selection
873897

874898
**Data movement is minimal**. Linear number of exchanges.
875899

900+
901+
<br/>
902+
<div align="right">
903+
<b><a href="#top">↥ back to top</a></b>
904+
</div>
905+
<br/>
906+
907+
876908
### 3.2. Insertion sort
877909

878910
- In iteration `i`, swap `a[i]` with each larger entry to its left.
@@ -922,6 +954,14 @@ e.g.: `A E E L M O T R X P S`
922954
**Proposition**. For partially-sorted arrays, insertion sort runs in linear time.
923955
> *Pf*. Number of exchanges equals the number of inversions. (number of compares = exchanges + (N – 1).)
924956
957+
958+
<br/>
959+
<div align="right">
960+
<b><a href="#top">↥ back to top</a></b>
961+
</div>
962+
<br/>
963+
964+
925965
### 3.3. Shellsort
926966

927967
Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of array entries that are far apart, to produce partially sorted arrays that can be efficiently sorted, eventually by insertion sort.
@@ -981,6 +1021,14 @@ public class Shell {
9811021
> - Average-case performance?
9821022
9831023

1024+
1025+
<br/>
1026+
<div align="right">
1027+
<b><a href="#top">↥ back to top</a></b>
1028+
</div>
1029+
<br/>
1030+
1031+
9841032
### 3.4. Shuffling
9851033

9861034
*Goal*. Rearrange array so that result is a uniformly random permutation.
@@ -1211,6 +1259,14 @@ private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
12111259
}
12121260
```
12131261

1262+
1263+
<br/>
1264+
<div align="right">
1265+
<b><a href="#top">↥ back to top</a></b>
1266+
</div>
1267+
<br/>
1268+
1269+
12141270
### 4.3. Bottom-up mergesort
12151271

12161272
Bottom-up mergesort consists of a sequence of passes over the whole array, doing `sz-by-sz` merges, starting with `sz` equal to `1` and doubling `sz` on each pass. The final subarray is of size `sz` only when the array size is an even multiple of `sz` (otherwise it is less than `sz`).
@@ -1282,6 +1338,14 @@ Lower bound may not hold if the algorithm has information about:
12821338

12831339
*Digital properties of keys*. We can use digit/character compares instead of key compares for numbers and strings.
12841340

1341+
1342+
<br/>
1343+
<div align="right">
1344+
<b><a href="#top">↥ back to top</a></b>
1345+
</div>
1346+
<br/>
1347+
1348+
12851349
### 4.5. Comparator
12861350

12871351
Comparator interface: sort using an *alternate order*.
@@ -1488,6 +1552,14 @@ public class Quick
14881552

14891553
*Proposition*. Quicksort is not stable.
14901554

1555+
1556+
<br/>
1557+
<div align="right">
1558+
<b><a href="#top">↥ back to top</a></b>
1559+
</div>
1560+
<br/>
1561+
1562+
14911563
### 5.4. Quicksort: practical improvements
14921564

14931565
*Insertion sort small subarrays.*
@@ -1527,6 +1599,14 @@ private static void sort(Comparable[] a, int lo, int hi)
15271599
}
15281600
```
15291601

1602+
1603+
<br/>
1604+
<div align="right">
1605+
<b><a href="#top">↥ back to top</a></b>
1606+
</div>
1607+
<br/>
1608+
1609+
15301610
### 5.5. Selection
15311611

15321612
*Goal*. Given an array of *N* items, find a `kth` smallest item.
@@ -1616,6 +1696,14 @@ public class Quick3way
16161696

16171697
Randomized quicksort with 3-way partitioning reduces running time from *linearithmic* to *linear* in broad class of applications.
16181698

1699+
1700+
<br/>
1701+
<div align="right">
1702+
<b><a href="#top">↥ back to top</a></b>
1703+
</div>
1704+
<br/>
1705+
1706+
16191707
### 5.7. Sorting applications
16201708

16211709
Sorting algorithms are essential in a broad variety of applications:
@@ -1774,6 +1862,14 @@ Order of growth of running time for priority queue with N items:
17741862
| ordered array | N | 1 | 1 |
17751863
| goal | log N | log N | log N |
17761864

1865+
1866+
<br/>
1867+
<div align="right">
1868+
<b><a href="#top">↥ back to top</a></b>
1869+
</div>
1870+
<br/>
1871+
1872+
17771873
### 6.5. Binary heaps
17781874

17791875
*Binary tree*. Empty or node with links to left and right binary trees.
@@ -2183,6 +2279,14 @@ public class FrequencyCounter
21832279
}
21842280
```
21852281

2282+
2283+
<br/>
2284+
<div align="right">
2285+
<b><a href="#top">↥ back to top</a></b>
2286+
</div>
2287+
<br/>
2288+
2289+
21862290
### 8.2. Ordered symbol tables
21872291

21882292
In typical applications, keys are *Comparable* objects, so the option exists of using the code `a.compareTo(b)` to compare two keys a and b.
@@ -2262,6 +2366,7 @@ private class Node
22622366
private Key key;
22632367
private Value val;
22642368
private Node left, right;
2369+
22652370
public Node(Key key, Value val)
22662371
{
22672372
this.key = key;
@@ -2276,16 +2381,16 @@ private class Node
22762381
public class BST<Key extends Comparable<Key>, Value>
22772382
{
22782383
private Node root;
2279-
private class Node
2280-
{ /* see previous slide */ }
2281-
public void put(Key key, Value val)
2282-
{ /* see next slides */ }
2283-
public Value get(Key key)
2284-
{ /* see next slides */ }
2285-
public void delete(Key key)
2286-
{ /* see next slides */ }
2287-
public Iterable<Key> iterator()
2288-
{ /* see next slides */ }
2384+
2385+
private class Node { }
2386+
2387+
public void put(Key key, Value val) { }
2388+
2389+
public Value get(Key key) { }
2390+
2391+
public void delete(Key key) { }
2392+
2393+
public Iterable<Key> iterator() { }
22892394
}
22902395
```
22912396

@@ -2336,6 +2441,14 @@ private Node put(Node x, Key key, Value val)
23362441
Worst-case height is *N*. (exponentially small chance when keys are inserted in random order)
23372442

23382443

2444+
2445+
<br/>
2446+
<div align="right">
2447+
<b><a href="#top">↥ back to top</a></b>
2448+
</div>
2449+
<br/>
2450+
2451+
23392452
### 9.2. Ordered operations
23402453

23412454
#### 9.2.1. Minimum and maximum
@@ -2653,6 +2766,14 @@ Direct implementation is complicated, because:
26532766

26542767
*Bottom line*. Could do it, but there's a better way.
26552768
2769+
2770+
<br/>
2771+
<div align="right">
2772+
<b><a href="#top">↥ back to top</a></b>
2773+
</div>
2774+
<br/>
2775+
2776+
26562777
### 10.2. Left-leaning red-black BSTs
26572778
26582779
#### 10.2.1. Definition
@@ -2825,6 +2946,14 @@ private Node put(Node h, Key key, Value val)
28252946
\* exact value of coefficient unknown but extremely close to 1
28262947
28272948
2949+
<br/>
2950+
<div align="right">
2951+
<b><a href="#top">↥ back to top</a></b>
2952+
</div>
2953+
<br/>
2954+
2955+
2956+
28282957
### 10.3. B-trees
28292958
28302959
@@ -2966,6 +3095,14 @@ Sweep vertical line from left to right.
29663095
29673096
*Bottom line*. Sweep line reduces 2d orthogonal line segment intersection search to 1d range search.
29683097
3098+
3099+
<br/>
3100+
<div align="right">
3101+
<b><a href="#top">↥ back to top</a></b>
3102+
</div>
3103+
<br/>
3104+
3105+
29693106
### 11.3. kd trees
29703107
29713108
Kd tree. Recursively partition k-dimensional space into 2 halfspaces.
@@ -3119,6 +3256,14 @@ Key idea. Suppose particle is far, far away from cluster of particles.
31193256
Running time per step is *N log N*.
31203257

31213258

3259+
<br/>
3260+
<div align="right">
3261+
<b><a href="#top">↥ back to top</a></b>
3262+
</div>
3263+
<br/>
3264+
3265+
3266+
31223267
### 11.4. Interval search trees
31233268

31243269
*1d interval search*. Data structure to hold set of (overlapping) intervals.
@@ -3453,6 +3598,14 @@ Note: see [this video on Youtube](https://www.youtube.com/watch?v=3mu47FWEuqA) f
34533598
*Load balancing*. After M tosses, expect most loaded bin has *Θ ( log M / log log M )* balls.
34543599

34553600

3601+
<br/>
3602+
<div align="right">
3603+
<b><a href="#top">↥ back to top</a></b>
3604+
</div>
3605+
<br/>
3606+
3607+
3608+
34563609
### 12.2. Collisions
34573610

34583611
**Collision**. Two distinct keys hashing to same index.
@@ -3601,6 +3754,14 @@ for search hits and search misses (or inserts), respectively.
36013754
\* under uniform hashing assumption
36023755

36033756

3757+
<br/>
3758+
<div align="right">
3759+
<b><a href="#top">↥ back to top</a></b>
3760+
</div>
3761+
<br/>
3762+
3763+
3764+
36043765
### 12.3. Context
36053766

36063767
#### 12.3.1. Algorithmic complexity attacks

0 commit comments

Comments
 (0)