Categories
Computer Science School

01 03

No progress today. I went to the store, played disc golf, installed 4 4-foot LED lights on my garage ceiling with my brother, and watched the movie Unbreakable with family.

Categories
Computer Science School

01 02

Performance

EECS1 – read 2, 3 of 19 chapters of Think Python. That sounds good until you realize it’s a remedial portion of the class. Also, I haven’t started the real reading in that class.

Intro to CS & Python – lectures 1, 2 of 12.

Extra – pseudo code for Huffman’s Algorithm (see Computation Structures notes from yesterday). I did this first thing in the morning and it already looks bad in light of some of what I learned today.

I dictated my written notes into my phone. The automated dictation software has issues. For instance, “new line” sometimes prints out “new line” and sometimes verbally commands a carriage return. “New paragraph” doesn’t seem to have this issue. “Colon” always prints “colon” despite “semicolon” working as a verbal command for “;”. “Paren” or “parenthesis” almost never gives me a “(” and I’ve never successfully commanded a close parenthesis “)”. Dictation was fine for prose, but unusable for lists and code. Fixing the dictation for lists and code takes longer than typing them.

Part of that may be due to using WordPress. Perhaps the text would be easier to work with in Word or Google docs and then I can transfer that to here. That would mean my process is (1) write notes, (2) dictate notes, (3) clean notes in a word processor, (4) copy notes here, (5) clean notes for web presentation. Alternatively, (1) type notes in WordPress.

***

What is Computation, Intro to CS and Python lecture #1

A program is a recipe.

  • Sequence of steps
  • Flow of control, determining when steps execute
  • A means of determining when to stop

Basic machine architecture 

  • Memory – stores programs and data.
  • CPU
    • Control unit – program counter, tells ALU what ops to do on what data, increments when ALU performs, accesses programs.
    • Arithmetic logic unit – does primitive operations / tests, accesses data, write data.
  • Input/output

Alan Turing proved you could do anything with the six primitives. The six primitives are move left, move right, read, right, scan, and do nothing. We can abstract methods to create new primitives, so modern languages have more primitives. Anything computable in one language is computable in another language.

Errors

  • Syntactic errors (e.g. 3″hi”) – easily caught
  • Static semantic errors (e.g. 3 + “hi”) – some languages check prior to running. These can cause unpredictable behavior.
  • No semantic errors, but different meaning than user intends
    • Program crashes
    • Program runs forever
    • Program returns “incorrect” answer

 A program is a sequence of definitions and commands. It evaluates definitions and executes commands. These are the tests and operations from basic machine architecture.

Programs manipulate data objects. Objects have types defining allowable operations for that type. Objects are scalar or non-scalar. Scalar examples: int, float, bool, NoneType. You can use type parentheses parentheses to see an object’s type. You can convert objects from one type to another (float(3) converts integer to float, int(3.9) truncates a float to the integer 3, str(3) converts 3 to “3”).  Such conversion is called casting.

Operaters
+ → sum, concatenation for strings
– → difference
* → product, repetition for a number of times for strings (“Ho ” * 3 is “Ho Ho Ho “)
/ → division (always a float)
% → modulus
** → power (^ in some languages, the ^ is a bitwise operator in Python)
= → bind a value to a variable. Variables are case sensitive in Python!
# → comment a line
// → floor division, it rounds the result down (result is an integer)

Bitwise operaters
x<<y → x is suffixed by y zeroes. Equivalent to x*2**y.
x>>y → x is shifted right y places. Equivalent to x//2**y.
x&y → (and) for each bit, if x & y are 1, 1, else 0.
x|y → (or) for each bit, if either x or y are 1, 1, else 0.
~x → bitwise complement of x. 01 = 10.
x^y → bitwise exclusive or (xor). Flip a bit in x if bit in y is 1.

***

Branching and Iteration, Intro to CS and Python lecture #2

Input prints what is in quotes, user type something and presses enter, and the input is bound as a string to a variable.

text = input("Type a string.")
print(text)

If you want the input as another type, cast it as that type.

num = float(input("Enter a number."))
print(num)

Comparing (tests)

i > j #compares strings lexicographically
i >= j
i < j
i <= j
i == j
i != j

Boolean operators: not, and, or.

Control flow through branching (and here I thought if statements were nothing special).

if:
else:

if <condition for case 1>:
elif <condition for case 2>:
elif <condition for case 3>:
else:

Control flow through iteration (loops). Loops and if statements pay close attention to the indentation. If it’s not indented (4 spaces by convention), it’s not in the loop or part of the if statement.

while <condition>:
    Indented code
    More indented code
Code not in the while loop

#This:

n = 0
while n < 5:
    print(n)
    n = n + 1

#is equivalent to this:

for n in range(5):
    print(n)

Range(start, stop, step) 
Stop is the only required argument; start defaults to zero and step defaults to one. If provided two arguments, the function interprets them as the start and stop. The for loop continues until stop minus one. The arguments must be integers.

Break ends the loop it is found in.

For loops

  • known number of iterations
  • uses a counter
  • can be written as a while loop

While loops

  • unbounded number of iterations
  • can use a counter, but must initialize before the loop and increment it in the loop
  • not all loops can be written as for loops

If you enter into an infinite loop, try Ctrl + C.
“\n” starts a new line in text.

***

Think Python, CH 3

Functions
function(argument)
Arguments are assigned to variables called parameters. Variables and parameters are local. Void functions don’t return anything; return functions do. 

Modules contain collections of related functions.

import math
import [module]
math.pi
math.[math function]

# Instead of
    import math
    print(math.pi)
# you can 
    from math import pi
    print pi
# or get everything from the math module
    from math import *
    print pi

Define a new function using def. First line is the header, the rest is the body.

def print_lyrics()
    print("Somewhere over the rainbow...")

Flow of execution does not necessarily flow from top to bottom. As functions must be defined before they are executed, each may serve as a detour from the top down flow. Reading programs following the flow of execution is smoother than reading at top to bottom.

Stack diagrams.  Shown in a coding block for the fixed-width font.  Stack diagrams track variables and their values across modules and functions.  

<module>
    line1 "homage" #think the French pronunciation
    line2 "to orange"
function1()
    part1 "homage"
    part2 "to orange"
    part3 "and Omaha"
function2()
...

Functions help by:

  • Dividing things up so you can name a function, its arguments, and its variables. This makes reading and debugging easier.
  • Eliminating repetitive code.
  • Allowing you to build pieces and assemble them into a whole.
  • Allowing you to reuse well-designed code in other programs.

Python doesn’t recognize tabs, so if your text editor isn’t converting the tabs to spaces, it’ll have run errors.

When debugging, ensure you are calling the most recently debugged version of the program and not the original bugged program.

Categories
Computer Science School

01 01 – Starting CS

I want to study computer science because

  • I’d like to write a stock trading program (I’ve been told this is so common that it’s a banned topic in some machine learning classes)
  • I’d like to write a chat bot that helps depressed people
  • I’d like to write a program that analyzes potential legislation through giving unique words (likely pork if it mentions a location) and giving the frequency of other words
  • I’d like to write a program that systematically aggregates and translates from non-English sources
  • I’d like to know programming because it can improve the quality of life for anything else I do
  • I’d like to program for a living because it seems like it would pay more than being an auditor.

To this end, I’m going to utilize MIT’s Open Course Ware. Yesterday I found a list of courses at https://ocw.mit.edu/courses/find-by-topic/#cat=engineering&subcat=computerscience. This list was daunting. I want to take 107 courses, about twice what a lot of degrees would require. (5 courses per semester * 8 semesters = 40 courses, 6 * 8 = 48 courses.) The amount to be consumed is a problem.

My advantages are manifold. I’m not taking the traditional courses in-person. I can drop a class if I don’t think it will be useful. I can proceed at my own pace. I can retake the tests. In some courses, I can take multiple midterm tests from different semesters if I feel like I need the practice. We will see if the advantages can surmount the number of courses I’d like to take.

***

Zipf’s law: the idea that the 2nd most frequently used word appears 1/2 as often as the most frequently used word, the 3rd most frequently used word appears 1/3 as often as the most frequently used word, etc. Generalized, the eponymous law states the Nth frequent word appears 1/N as often as the most frequently used word where N !< 2. As “the” is the most frequent word in English, its frequency would then seem to be important.

According to https://www.english-corpora.org/coca/, the frequency of “the” in the COCA (Corpus Of Contemporary American English) is 50,066,305. https://corpus.byu.edu/coca/compare-bnc.asp lists the millions of words in each genre and these add up to 575 million. 50066305 / 575000000 = 0.0870718347826087. 1 / .0870718347826087 = 11.484770046441414. So about every 12th word is “the”.

The Vsauce video on Zipf’s law says the frequency is more like 6%, so about every 16th word is “the”. That video also states the most frequent 100 words account for about half of all words in a work. A word used only once in a work is a “hapax legomenon”. Quizzaciously was, at the time the video was posted, a Google hapax legomenon.

Hapax legomenon are important because they constitute the gist of the message couched in the most frequent words. Additionally, they can make up a significant portion of a work. It stands to reason deep conversation might similarly be better defined not by frequency but by infrequency.

***

The Alt code for capital sigma (signifying summation) is Alt + 228. Σ!

***

Today I am starting with Introduction to Electrical Engineering and Computer Science 1. There is a Python Tutorial section which seems to be an indication I should know a certain amount of Python. I don’t know Python. They point to Think Python: How to Think Like a Computer Scientist by Allen B. Downey. Another resource is the official tutorial. Having read the introduction to both, I’m proceeding with Think Python because it seems more user-friendly.

I read chapter 1 of 19 chapters.

***

Computation Structures, 1 Basics of Information

Information resolves uncertainty about a fact or circumstance. The amount of uncertainty resolved, the more information conveyed. Claude Shannon defines information as I(xi) = log2(1 / pi) where discrete random variable X has N possibilities with P probabilities. (1 / pi) is the probability of a specific instance of information and log2 ensures the information is represented in bits, that is, the number of bits required to encode the information.

Common case: faced with N equally probable cases, you receive data narrowing cases to M choices. The probability such data is sent is M * (1 / N). I(data) = log2( 1 / (M * (1 / N)) ) = log2(N / M) bits.

Common case examples:

  • Coin flip => N=2 & M=1. log2(2/1) = 1 bit.
  • A drawn card’s suit => N=4 & M=1. log2(4/1) = 2 bits.
  • Roll of 2 dice => N=36 (the dice are different colors) & M=1. log2(36/1) = 5.17 bits. This represents the most efficient encoding scheme possible.
  • [mine] roll of 2 identical dice => N=21 & M=1. log2(21/1) = 4.39 bits. I did not find a calculator that worked for this, so I’m using Google to type things like “log2(21)”.

Entropy is the average information received in each datum received regarding X. That is, H(X) = E(I(X)) = Σpi * log2(1 / pi) where H is entropy, E is the expected value (the average), and I is the information. In other words, multiply each datum’s information in bits by the datum’s likelihood and add the products.

Entropy provides a yardstick to measure average bits used in an encoding scheme. If on average the encoding scheme uses less than the entropy, the scheme is not resolving uncertainty. If on average the encoding scheme uses more than the entropy, the scheme may be inefficient. The entropy should be just over H(X), the scheme communicating everything it needs to as efficiently as possible.

Encoding is an unambiguous mapping between bit strings and the set of possible data. There are fixed length and variable length encoding. Variable length encoding can be represented as a binary tree. An example would be to compress text wherein certain words occur more frequently than others.

Fixed length encoding assumes equal probability of the characters (or other piece of information). Similarly, for unknown probabilities and lacking contravening evidence of their equality, the programmer defaults to fixed length encoding. Thus a binary tree for a fixed length encoding scheme would have all the termini at the same height of the tree, otherwise it would be a variable length encoding scheme. Fixed length encoding allows random access, meaning the user can access the Nth character of a string via {(N-1) * [binary tree height] + 1}. The entropy for fixed length encoding is Σ(1/N)log2( 1 / (1/N) ) = log2(N) bits. So for the ASCII 128 characters, that’s 7 bits. Sure enough, log2(128) = 7.

Hexadecimal is often represented by preceding the number with a 0x, e.g. 0x7D1.

N-bit numbers. The highest order bit is the “sign bit” with 0 being positive and 1 being negative. The most negative number is 10…000?! So negative numbers are from opposite land? Yep, it seems a negative number for a “two’s complement value” is its bitwise complement and add 1. The C representation of bitwise complement is ~X where X is the things you want the bitwise complement of.

Huffman’s Algorithm problem: “given a set of symbols and their probabilities, construct an optimal variable length encoding”. Huffman’s Algorithm: (1) starting with the two least probable symbols, create a subtree. (2) Continue to make subtrees using the two least probable symbols or subtrees. Evaluate subtrees’ likelihoods as the sum of their symbols’ likelihoods. (3) Stop when the last symbol has been used. The result is an optimal constructed from the bottom up.

Huffman’s Algorithm need not be applied to single symbols. It can be applied to pairs of symbols or any other length desired. It can also apply to words.

The professor mentions the LZW algorithm. It’s a phenomenal algorithm, but I don’t understand it yet. I did take an hour or two to mess around with Huffman’s Algorithm. I think I’ve got it.

Hamming distance is the number of bits required to change one valid code word to another valid code word. For instance, if a coin flip is encoded to a single bit, the Hamming distance between heads and tails is 1, so a single bit error is undetectable. If the Hamming distance between to code words is zero, they are the same. If the minimum Hamming distance in an encoding scheme is 2, a single bit error can no longer go undetected.

A simple way of increasing Hamming distance is to add even or odd parity to the code words. For instance, if coin flips are encoded as 1 for heads and 0 for tails, adding an even parity bit to the end would give 11 and 00. If a parity check is run and the word isn’t even, an error has occurred. A two bit error would go undetected. To detect E errors, the minimum Hamming distance must be E + 1.

To correct E errors, set code words a minimum of 2E+1 Hamming distance apart. This is required so that no corruption of E magnitude will change any code word into any other code word’s possible corrupted versions.

I don’t think this was an hour long, but it took hours to digest it and type notes. There are 21 lectures, so this would take about 21 days. At first this seemed way too slow, but if you bank on about 120 days in a semester and divide by 6 courses, that’s 20 days per course.

***

Python commands used

  • help() – brings up a help utility
  • [in help()] “keywords” – brought up keywords help could help with
  • [in help()] quit – quits help utility
  • import random – imports the random module
  • random.randint(70, 80) – provides a random integer between 70 and 80, inclusive
  • import math – imports the math module (you get the idea)
  • math.sqrt(4) – gives the square root of 4
  • import calendar
  • calendar.HTMLCalendar(firstweekday=0) – makes a file at a given hexadecimal address. I tried to find said file by looking at files created today. Forgot that I reinstalled python today. I can try again tomorrow.
  • print(“Hello, world!”) – a traditional first step

Categories
Uncategorized

Another Test Post

This is a test of several things.

First, I want to be able to post outside of the blogging portion, so does this become its own thing, or is it going to be part of the blog? I placed it first under pages instead of posts.

Second, this beige, or slight pink in the preview area is awful. So I’m going to change to maybe black background and lime green and see if I find that more palatable. Okay, the preview allows the paragraphs to have the background and text colors I desire. However, it looks like the overall site design trumps page background. Hmm.

I’m not sure how to change the overall settings. I’m also not sure why the indentation for this paragraph is different. : /

Third, checking if there’s anything that spots incorrectly spelled words. Soe going to missspell a few things. The preview area does indeed have the squiggly red underlining for misspellings.

Categories
Uncategorized

Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!