Math & Computer Science Flashcards
What is dependency injection?
Rather than a client object creating its own dependencies or services, they are supplied by someone else so that the client doesn’t need to know how to create the service
What are eigenvectors and eigenvalues?
Eigenvectors of a linear transformation (matrix) are not changed except in magnitude (the corresponding eigenvalue). They can form the basis vectors of a transformation
What is a multiplexer?
A logic gate that toggles between the value of 2 inputs depending on the selector
What does an ALU do? How is it made?
It can do many different calculations (AND, NOT, addition, negation, etc) on inputs depending on several other inputs that can be relatively elegantly designed
How can you create memory from NAND gates?
Build a flip-flop using a looped NAND gate
What is machine language?
Binary instructions to a computer corresponding to different ALU calculations and storage into registers and memory
What is assembly?
A human readable version of machine language e.g. D=A+1, @variable with labels
What are the 3 main components of a computer?
ROM (instructions), CPU, and Memory
What is an assembler?
Turns assembly into machine language, including converting various labels and variables
What does a Virtual Machine do?
Provides indirection between a high level language and assembly
How are Virtual Machines implemented?
Stack Machine
How are function calls represented in a VM?
All arguments are already on the stack. Add the return code address and other pointers. Reserve space for the local variables. Move the stack pointer and jump
How are methods and constructors different from regular function calls?
They also either allocate space or add a “this” reference
How are variables tracked in a compiler?
A linked list of Symbol tables that each go deeper into scope
What does an operating system take care of?
Memory management, device input, output, strings, arrays, math, initializing everything above
What is Godel’s Theorem of Incompleteness?
All consistent axiomatic formulations of number theory include undecidable propositions
OR
Any system sufficiently powerful to express arithmetic is either incomplete or inconsistent
What was Hilbert’s program?
Split mathematics (basic strings) and meta-mathematics (defining statements about such strings) to develop absolute proofs that don’t depend on other systems
How does Godel numbering work?
Assign Godel numbers to all operations, variables, statements, predicates, and sequences of statements using clever schemes of multiplying prime numbers so that they are all unique
What is the halting problem? How can we prove it is undecidable?
Decision problem for whether a given program halts on a given input.
Proof by contradiction. Assume it exists. Create a new program that takes an input and runs that input on that program. Halt if it doesn’t and loop if it does. Give that program as an input to itself l, which leads to a contradiction.
What is a convolutional neural network?
Apply a kernel across an image to aggregate data, which creates a filtered set of linear combinations of local feature. Run that through a neural net
What is a Recurrent Neural Network?
Takes input and then feeds back into itself. It can take 1 or multiple inputs and generate 1 or multiple outputs. Good for sequential data or keeping memory
What is a Recursive neural network?
Aggregates into a hierarchical structure.
How is 3-SAT NP Complete?
3-SAT is NP because you can brute force it.
According to Cook-Levin, you can simulate a nondeterministic Turing Machine into SAT, and then SAT is reducible to 3-SAT
What is Benford’s Law? Why does it happen?
In many real life datasets, the leading digit is likely to be small. This tends to apply to values across multiple orders of magnitude, especially power laws
What does it mean for Problem A to be reducible to Problem B? What is an example?
We can convert Problem A into Problem B, so if we can solve Problem B, we can solve Problem A.
For example, we can reduce adding a list of numbers to the Sum of 2 numbers.
What does it mean for Problem A to be NP Complete? What does it intuitively mean?
- Problem A is in NP
- For all NP problems B, B is poly-time reducible to A
NP Complete problems are the hardest NP problems, and you can use them to solve all NP problems.
What does it mean for Problem A to be NP Hard?
For all NP problems B, B is poly-time reducible to A. This is the second condition of NP Complete.
What are the three parts of a floating point number?
Sign, exponent, significand
