commit 9aab798e75913d9374f54998b5589a2c06726857
parent 687944929926077b86170dea30e501224caaf435
Author: Andrew <andrewlaack1@gmail.com>
Date: Mon, 11 Nov 2024 15:56:15 -0600
took some notes on dsa
Diffstat:
4 files changed, 29 insertions(+), 3 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -75,9 +75,9 @@ Ch 5 (Hashing)
Ch 6 (Information Theory and Data Compression)
- InformationTheory
- - Codeword
+ - [Codeword](Codeword.md)
- [BinaryCode](BinaryCode.md)
- - Entropy (define with probabilities (H(X) instead of IC(X)))
+ - [Entropy](Entropy.md)
- [InformationContent](InformationContent.md)
- RootedTree
diff --git a/BinaryCode.md b/BinaryCode.md
@@ -5,6 +5,6 @@ Ch 6
## Notes
-**Definition:** A binary code for S is a function from S -> {0,1} * .
+**Definition:** A binary code for S is a function c from S -> {0,1} * .
Basically, this is the function to encode elements of S to binary.
diff --git a/Codeword.md b/Codeword.md
@@ -0,0 +1,10 @@
+:cs: :data-structures:
+# Codeword
+
+Ch 6
+
+## Notes
+
+**Definition:** A codeword is an element c(x) where c is a binary code and x is a message.
+
+Remember, a binary code is defined as c : S -> {0,1}\*.
diff --git a/Entropy.md b/Entropy.md
@@ -0,0 +1,16 @@
+:data-structures: :cs:
+# Entropy
+
+Ch 6
+
+## Notes
+
+**Definition:** Entropy is the average number of bits communicated by one message if message hoarding is allowed.
+
+Entropy of a finite set of messages is denoted as H(X).
+
+Formula:
+
+$H(X) = -\sum_{x\in S} P(x)log_2(P(x))$
+
+X is an ordered pair (S,P) where S is a finite set of messages and P is a function from S -> [0,1] S.T. P(x) = Probability of x for all x in S.
