Topics

Common programming concepts Data types There are two kinds of types: scalar and compound. Scalar types are types that are not “containers” and represent a single value, like integers, floating point numbers, and characters. Rust has four primitive scalar types: integers, floating-point numbers, Booleans, and characters. Rust’s integers can be signed or unsigned and signed integers are stored in two’s complement form. Rust’s default integer type is i32. isize or usize change depending on the computer’s architecture. ...

Setup Mostly following instructions from Real World OCaml. brew install opam opam init # Said "yes" to default config in .zshrc # Ran this as advised by opam. I assume it sets the default OCaml compiler as the current compiler. eval $(opam env --switch=default) # Install basic libraries used in the book. `base` is a standard library. `utop` is a top-level REPL opam install base utop

Camera notes Taiwan trip For overhead shots of food, it’s best to be as parallel to the subject as possible, preferably in both the x and y axes. In general, I need more practice shooting people. I’m not catching people at the right time to get a good reaction: They blinked or they don’t have a good expression. I need to work on framing better. I tend to keep things zoomed out; I need to fill the frame more often.

Introduction Algorithms are procedures to accomplish a specific task. They are ideas. Algorithms have three main attributes: correctness, simplicity, and efficiency Correctness is tricky to prove: Many have proposed algorithms that were later proven to be incorrect. Algorithms are always correct; heuristic solutions may give a suitable answer most of the time, but not always. Correctness Specify the input Specify the output Make sure output is well-defined Beware of a compound goals. Each part might be a good goal, but trying satisfy all at the same time can make things overly complicated. If in doubt, restrict the problem. It will make proving correctness easier. Counter-examples: the easiest way to prove incorrectness, but failing to find counter-examples does not prove correctness. A counter-example should be verifiable. Show what the proposed algorithm gives as output. Then show that there’s is a better answer. They should be simple, no extra bits. Finding good counter-examples is similar to writing good tests. But finding good counter-examples is not about exploring the whole domain. Think small. Confine the input space and exhaust all options. Look for weaknesses (e.g. If algorithm relies on finding the maximum, what happens if all values are equal?). Look for ties. Look at extreme cases: large, small, clustered, diffuse. Proof by induction is the most common way to prove an algorithm, especially recursively defined ones. Specify a boundary or base case Assuming several things are true, show that incrementally breaking the problem into related sub-problems, the output is true. Two common errors are bad base cases or assuming a proven algorithm can be applied to input that has not been proven yet. Summations are used often in algorithm analysis Arithmetic progressions e.g. The sum of the first n positive integers is $n(n+1)/2$ In general, if the term is quadratic, the sum will have a cubic order; a cubic term will have a sum that is a quartic order, etc. If the terms have a negative exponent, the sum converges to a constant. Geometric progressions If the base of each term is less than one, the summation always converges to a number. If the base is one or more, it diverges. When proving a summation by induction, the main step is to usually factor out the largest term, so that the inductive hypothesis can be substituted into the equation. Modeling problems Modeling your application in terms of well-defined data structures and algorithms is the most important step to finding a solution. ...

By Bjarne Stroustrup https://isocpp.org/tour Much of today’s existence relies on software. C++ was designed to write quality software and its features are there to improve that quality. Chapter 2: The basics C++ is compiled. That means the source files are compiled into object files and the object files are linked into executables. Executables are made for a particular combination of OS (or not) and hardware and are not portable. However, C++ is portable because the source files can be compiled into an executable for many system combinations. ...

A SkillShare class by Roxane Gay Start with your why What are you trying to communicate to the reader? Without a sense of purpose, the reader is left wondering what they just read. Be specific about the purpose. Your target audience shouldn’t be “everyone”. Even if your experience is very specific, the audience will find ways to relate to it. Therefore, your individual experience is enough if written well. For non-fiction essays, potential whys include increasing awareness, calling to action, changing perspective, inspiring stories. Give your reader subtle cues to your why by including examples from your own experience. People need to be told what to do. ...

Glossary Asymptotic analysis (Big O) Asymptotic analysis expresses runtime and space time in terms of how quickly they grow relative to the input as the input grows arbitrarily large. how quickly they grow… Exact runtime can only be measured by benchmarking. Many factors of an actual computer implementation govern this result (cache, CPU instructions, CPU speed, etc.) …relative to the input… Instead of measuring in seconds, we use the size of the input. The input can be just a number or the size of the input object. …as the input grows arbitrarily large The algorithm may have distinct steps that have different runtimes. The overall runtime may have multiple terms, but the only term that matters is the one that grows the fastest as the input increases. Develop a habit of thinking about asymptotic performance while you code, both in time and space. Use it as a tool to identify places for optimization. Constants may not matter in big O notation, but they can be important in practice. If you can make an algorithm run even 2x faster on average, that is 2x more work you can do. ...

Greedy algorithm A greedy algorithm builds up a solution by choosing the option that looks the best at every step. Say you’re a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it? Whenever picking which coin to use, you’d take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies. That’s a greedy algorithm, because you’re always greedily choosing the coin that covers the biggest portion of the remaining amount. ...

Python sys.getsizeof sys.maxsize returns largest signed integer float('inf') represents an infinitely large number with the type float user defined classes sorting: define a __lt__ method. Built-in sort is guaranteed to call __lt__. hashing: define __eq__ and __hash__ methods. Data structures Linked list List, dynamic array, fixed array dictionary trie tree graph set deque algorithms shortest path Djikstra A* strongly connected components minimum spanning tree quicksort quickselect, statistics.median will also find median of unsorted list mergesort binary search insertion sort topological sort NP-complete problems that can’t be solved efficiently; use heuristics backtracking, simulated annealing traveling salesman visit each vertex once and return to starting vertex knapsack graph coloring hamiltonian path visit each vertex once binary negative signed integers are usually represented as two’s complement integers the left-most bit is a negative number and the others are positive in two’s complement, inverting bits changes the sign of the integer ~x = -(x+1) Python uses arithmetic right shifts: the most significant bit is copied This preserves the sign of the integer Python will grow the integer if it detects integer overflow In other languages, it will sometimes generate an error or it will only keep bits that will fit XOR: unique ability to cancel duplicate values continually XORing a list of integers can find a single unique value in a list of duplicates Count bits: Assuming an unsigned integer, update x &= x - 1 until x equals zero. The number of iterations equals the number of bits. If signed integer, switch to positive integer x = ~x + 1 and add one to the count because we need to count the signed bit. This runs in O(lg(n)) time, but could run faster since it skips bit positions where the bit is zero. math every integer has only one prime factorization

Log programming problems and what I learned. Legend: ADM -> Algorithm Design Manual LeetCode: 287. Find the Duplicate Number Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space. You can use the pigeonhole principle to prove that since we have n+1 integers, but only n distinct integers, at least one integer will occur more than one time. ...