Compsci cheat final PDF

Preview

Summary

Computers: A programmable electronic device that can store, retrieve, and process data. Reliable in most contexts, can be fast, tire, follow instructions precisely in, garbage out (GIGO) is a No intelligence, can perform simple math, perform comparisons, CPU: Central Processing Unit (Processor) fetc...

Description

Computers: A programmable electronic device that can store, retrieve, and process data. ➢

Reliable in most contexts, can be fast, don’t tire, follow instructions precisely [garbage in, garbage out (GIGO) is a concern] ➢ No intelligence, can perform simple math, perform comparisons, input/output (I/O) ➢ CPU: Central Processing Unit (Processor) – fetches and follows a set of simple instructions | Arithmetic and Logic unit(ALU) – math ops o Control unit – fetches next instruction, decodes instruction, executes instruction appropriately (can be thought of as a cycle) ➢ Main memory: Stores program and its data in random access memory (RAM) | Secondary Memory: Permanent storage Memory: storage of info, represented in binary digits (bits) as 0’s and 1’s; each location is identified by a memory address ➢ Volatile Memory: temporary storage – information is lost when power is lost. Typically faster/higher performing [RAM, DRAM] ➢ Non-Volatile Memory: permanent storage – info persists even after power is lost. Typically slower. [ROM,CDs, magnetic tape] I/O and Processing: input: data from the user is entered into the computer/into the program. ➢ Processing: what the computer is instructed to do by the program, often using info that was input into the program ➢ Output: info input or processed through the program is output Software: programs and other OS info used by a computer (Program: set of instructions to perform specific tasks) ➢ Algorithm: set steps for “doing something” – conducting some task, solving a problem [Programs can implement algorithms; algorithms cannot implement programs ➢ Operating System (OS): allocates computer resources, allows communication between user and the computer (Windows, Unix/Linus, DOS) Programming Language: a structured language that exists to communicate info to a computer in the form of a program ➢ High-level: easy for humans to understand; too difficult for computers to understand (C = A + B) ➢ Low Level: Harder for people to understand, but easier for computer to convert to useable instruction; instructions are fairly easy to convert for computer(ADD A B C) ➢ Machine language: 0’s and 1’s that contain instructions that can be understood by the computer (0110 1001 1010 1011) Function: very loosely – a relationship that maps an input to an output [f(x) = cos(x)] computer function: [sin(x)] ➢ Computer functions: a piece of the computer code that accepts an input argument from the user and provides output to the program ➢ Convenience – particularly if you have something that needs to be done multiple times in a piece of code ➢ Maintainability – easier to segment your code into rational pieces that are easier to maintain ➢ 4 key parts: name, input(s) (if applicable), output(s) (If applicable), comments that describe the other parts ➢ To call the function, you must name the function what you have saved your function as ➢ Important reason to document your code: by creating user-defined functions, you can look up its documentation using the help and doc commands ➢ Anonymous Functions: simple functions you create that are available elsewhere in the program, functions are visible in the workspace Number of I/O Arguments: sometimes you might not know how many input or output arguments you’ll have. Two key commands (inputs are “strings”) ➢ Nargin – determines number of input arguments. When used with a user-defined function, it determines how many input arguments were actually entered o Result of -1 indicates there are multiple answers, depending on how the function can be used ➢ Nargout – determines number of output arguments. When used with a user-defined function, it determines how many output arguments were requested by the user o Result from nargout can change based on how you use a function Formatted Output: the disp command is pretty useful, but has its own inherent limitations, the formatted print function command offers more control. ➢ You can also specify the format of the number to be printed; insert a tab, and do other special things with spacing on the screen. ➢ Width field: controls the minimum number of characters to be printed. Restriction: must be a positive decimal integer ➢ Precision field: preceded by the period, specifies the number of decimal places after the decimal point for both fixed point and exponential numbers Scope: “the extent of the area or subject matter that something deals with or to which it is relevant.” – Google | In computer science it is thought of as “Global” or “Local” ➢ “Development and implementation of algorithms in a procedure –oriented language, with emphasis on numerical methods for engineering problems” – Penn State ➢ Local variables: only have local scope, not displayed in the workspace, not available to any other part of the code except the function in which they exist ➢ Global Variables: global scope, displayed in the workspace, available in other parts of the code identified within a function, limited purpose, (can lead to bad habits) o Advantages: visible to all parts of code, modifiable by all parts of the code | Disadvantages: visible to all parts of the code, modifiable by all parts of the code MATLAB: named MATrix LABoratory | popular in STEM fields because of ease-of-use and built-in features | interpreted language | case sensitive | Graphical user interface

Matrix Inverse: an inverse “undoes” a function, singular matrix/illconditioned matrix: a matrix for which an inverse does not exist Determinants: a matrix inverse does not exist if the determinant of the matrix is equal to 0 Cross Products (Vector Products): result is a vector, always at a right angle (normal, orthogonal) to the plane defined by the two input vectors ➢ Mathematically is a special case of a determinant whose first row comprises unit vectors ➢ Must contain three elements Solving Systems of Equations: avoid inverting matrices as often as you can – its numerical “fussy” – solution accuracy isn’t always great due to ill-conditioning ➢ The \ operator is very, very special in MATLAB o Specialized algorithms exist to solve systems of equations under special conditions: banded matrices, tridiagonal matrices, sparse matrices o These algorithms outperform the Gaussian elimination you would have seen in Algebra – sometimes sever orders of magnitude o When you use the \ operator, MATLAB automatically examines your system, and determines which specialized algorithm to use to most efficiently solve the system o Bottom line: you can take advantage of algorithms you’ve never heard of to “better” solve the system Data Types: most computer science courses cover data types relatively early in their courses ➢ Most languages require you to declare a variable or a constant as a particular data type ➢ MATLAB generally doesn’t care for purposes of many operations ➢ Basic unit of information in computers is the bit o Bits can only have 2 values, 0 or 1 o Bit is a portmanteau (blending) of the phrase “binary digit” ➢ One of the more commonly discussed units of info is the byte o Typically is expressed as 8 bits/byte o Power of 2: allows values between 0 and 255 for 1 byte Numeric Data Types: double-precision Floating-Point Numbers (doubles) – MATLAB by default stores numeric data as doubles ➢ Each value requires 8 bytes of space: 8 bytes* 8 bits/byte = 64 bits ➢ Single-Precision Floating-Point Numbers (single) - uses half the storage space of a double, each value requires 4 bytes ➢ Complex Numbers (can be doubles, singles, or integers – more on integers on the next slide) – requires twice the space of base data type, needs space for both real-valued and complex-valued comp. ➢ Integer (whole numbers) – often used to count, or as matrix arrays, storage depends on id the integer is signed or unsigned Character and String Data: recall the difference between the two: ➢ Character: a single character (each element requires 2 bytes of space: 2 bytes*8 bits/byte = 16bits) ➢ String: a character array (spaces do not count as characters) ➢ Characters are represented in memory in two ways: ➢ ASCII – small computers, EBCDIC – super computers ➢ Main idea – every character stored in memory has a binary representation and a binary equivalent, when you convert from a character to a numeric data type, you get the decimal equivalent in the ASCII coding system Symbolic Data: MATLAB has a symbolic toolbox that uses symbolic data to perform symbolic algebraic operations, one method of doing this is with the sym function Logical Data: binary logic – 0’s and 1’s to represent binary ideas such as true and false, you can use true and false instead of 0’s and 1’s Sparse Arrays/Matrices: Recall that sparse arrays/matrices are arrays/matrices that are sparsely populated ➢ To save memory, we can use the sparse command ➢ If we store a matrix using doubles, it takes 8n bytes, where n represents the number of elements in the matrix ➢ The amount of memory saved is a function of how sparse the matrix is ➢ All machines have a finite amount of memory available – particularly when you have multiple memory intensive operations going on you should consider the amount of memory available Multidimensional Arrays: can store data of multiple attributes Character Arrays: character arrays are arrays of characters, key idea – the number of elements in each row has to be the same, or MATLAB will throw a warning, converting letters to ASCII in memory Rationale: many STEM course evaluate you on how you think, never trust anything that comes out of a computer, scientific expressions can become unwieldy to work with by hand. Humans are mistake prone – careless, absent-minded, easily distracted, bad handwriting

Categorizing Code: sections of computer code can be classifies into three categories ➢ ➢

Sequences – lines of code are executed one after another Selection Structures – executes some piece of code if some known condition is true, otherwise executes some sort of alternative code (can be many branches) ➢ Repetition Structures (loops) – causes a group of statements to be executed multiple times (either a fixed number, or until some stated condition is met). Relational Operators: one can perform comparisons between the relationships between scalars or vectors using the relational operators ➢ Beware: = means equal to/assignment | == means comparison for equality ~= not ➢ Remember: 0 is false, 1 is true Logical Operations: one can augment performing comparisons using and, not, and or ➢ Beware: | is the pipe (underneath backspace) ➢ And: element of the output array is set to 1 if all input arrays contain a non-zero element at that some array index; otherwise the element is set to 0, symbol & ➢ Not: element of the output array is set to 1 if the input array contains a zero value element at that same array location; otherwise that element is set to 0, symbol ~ ➢ Or: remember that this symbol is the pipe, not an L; element of the output array is set to 1 if either input arrays contain a non-zero element at that same array index; otherwise 0 ➢ Exclusive Or: the result is true when either A or B (but not both) are non-zero. The result is false when both A and B are zero or both A and B are non-zero, symbol xor ➢ Short-Circuit: the second operand is evaluated iff (if and only) the result is not fully determined by the first operand. If you know one condition is more likely to trigger something to happen in your code than the other, it makes sense from an efficiency standpoint to lust that condition first. Can be done with scalars and is supported by the following two scalar only operators: And & &, Or | | Pseudocode: verbal description of code, often is language independent ➢ Intermediate step between everyday language and a programming language Selection Structures (if): the simplest “classical” selection structure is the if statement ➢ If the comparison evaluates to be true, then the “do something” statements are executed ➢ If the comparison evaluates to be false, then the “do something” statements are ignored ➢ Can also use elseif and else as choices ➢ If first statement (if statement) doesn’t evaluate to true, it checks the elseif statements ➢ If nothing is true by the time one gets to else, the else commands are executed. ➢ Can mix and match these as much as you need, and not everyone needs to be present Switches: switches have a similar purpose to if statements ➢ Anything you can do with a switch can be done using if/elseif/else ➢ A “true” case will not check the other cases To Loop, or Not to Loop?: in MATLAB, loops should not be your first choice ➢ Low performance (bad clock time) ➢ Many good alternatives ( array operations, find commands, code vectorization ➢ Sometimes loops are unavoidable ➢ 3 types of loops: for loop, while loop, do while loop (do while, not in MATLAB ➢ Instead of indexing a for loop with a matrix, you have the option of using a matrix as the index (not often used, but can be useful, particularly if you want to vectorize code ➢ While loop: loop executes if condition evaluates to make the statement “while true.” If “while false,” loop wont execute. Potential: loop might never execute Analyze Code & Run and Time: analyze code: “This report displays potential errors and problems, as well as opportunities to improve your MATLAB programs” ➢ Run and Time: suggests performance improvements

Performance “Guiding Principles”: ➢ ➢

➢ ➢

Only print using print statements o It takes too much time to dump all of your calculation results to the screen – MATLAB has to stop calculations to print, so only print what you need If you know how big a result vector will be from a loop, consider pre-allocating a vector of that same size – potentially with the zeros or ones command o Some languages actually *require* pre-allocation; MATLAB isn’t one of them, but MATLAB works more efficiently id it doesn’t have to move things around in memory Consider feedback from the MATLAB GUI – both the profiler and the run and time features (MATLAB is very smart and can often offer helpful suggestions Because of quirks with OS’s, its often beneficial to run code multiple times to get average run times

Arrays vs. Matrices: ➢

Array – holds stuff: can gold numeric information, character data, symbolic data, etc. is “an orderly grouping of information.” No special properties by virtue of its existence ➢ Matrix – 2D numeric array used in linear algebra, used extensively in STEM fields, has special properties Matrix Terminology: Zero Matrix: matrix of zeros, Identity Matrix: a matrix of zeros main diagonal has 1’s, Sparse Matrix: most of the elements of the matrix have zero elements ➢ Dense Matrix: most of the elements of the matrix have non-zero elements ➢ Banded Matrix: non-zero elements are confined to a diagonal band comprising the main diagonal and zeros or more diagonals on either size o Bidiagonal matrix: zero matrix except: for non-zero entries along the main diagonal and either the diagonal above or below the main diagonal o Tridiagonal matrix: zero matrix except for non-zero entries along the main diagonal and on the first diagonal above or below the main diagonal Matrix Multiplication: can be thought of as a series of dot products; only defined if inner dimensions match, result size is the outer dimensions Matrix powers: raising a matrix to a power can be thought of as multiplying the matrix itself x (*)

MuPad: MATLAB’s computer algebra system (CAS) prior to the 2007B version of MATLAB was powered by MAPLE ➢ Utilizing research done at the University of Panderborn, MuPad was originally produced by SciFace Software ➢ Software was brought to MathWorks in 2008 ➢ MuPad was discontinued as a stand-alone program and now is only available in matlab Solve (root-finding): when applied to an expression the built-in function solve sets the expression equal to zeros and solves for the roots. MATLAB tries to solve for x id there is an x in the expression, otherwise will solve for the variable closest to x ➢ You can use linear algebra techniques, it is preferable to do so, but remember you can’t solve higher order systems with linear algebra Symbolic Calculus: ➢ Differentiation – instantaneous time rate of change; an analogous word is differential ➢ Integration – anti-derivative, In effect one performs the opposite calculations ➢ Differential Equation (DE) – an equation containing an unknown function and its derivatives ➢ Analogy and Syntax – syntax tends to vary based on special cases, but differential equations are often used in STEM fields to model physical behavior Interpolation and Extrapolation: ➢ Interpolation consists of “method[s] of construction new data points within the range of a discrete set of known data points” ➢ Extrapolation consists of “the process of estimating, beyond the original observation range, the value of a variable” ➢ Interpolation = excellent and good ➢ Extrapolation = fool’s errand: you must assume the data will behave like it had been behaving, which isn’t always a safe bet Linear Interpolation: (may not be the best go-to solution for accuracy) ➢ Most common approach → attempt linear interpolation ➢ Assumptions: the function of interest between two points of interest can be estimated by drawing a straight line between them, so that you end up with n – 1 lines connecting n points ➢ y = mx + b Spline Interpolation: ➢ A spline is to use a different polynomial between each pair of discrete points: in case of linear interpolation, linear equation ➢ Cubic splines are particularly popular ➢ Linear interpolation lacks “smoothness” ➢ Cubic splines correct this flaw by ensuring that at the data points, the adjacent splines have the same 0th, 1st, and 2nd derivatives. A cubic spline is given by a set of cubic polynomial Linear Curve Fitting: ➢ Process of constructing a curve or mathematical function, that has the best it to a series of data points, possible constraints ➢ Easiest approach is fit a linear line f(x) = ax + b ➢ Goal is to minimize the residuals: the difference between the actual and predicted values of a given point ➢ Typically used is the “least squares” e = ∑𝑛𝑖=1 (yi – (axi + b))2 Polynomial Curve Fitting: ➢

e=∑

𝑛

(𝑦𝑖 − (𝑎0 + ∑

𝑖=1

𝑘 𝑎 𝑥𝑖 ) 𝑖=1 𝑖

2

)

Numerical Difference Preface: ➢ Cautions: results from numerical differentiation of “noisy” discrete functions are typically even “nosier” and typically can be unreliable, techniques have been studied to deal with this, we assume our functions of interest aren’t very “noisy” Riemann Sum: ➢ Left: approximates the function by its value at the left end point, yielding multiple rectangles with a base of x and a height f(a+ix). This technique tends to overestimate f if f is decreasing, and underestimates if f is increasing. ➢ Right: underestimate f if f is decreasing, overestimate if f is increasing ➢ Middle: approximate function by its value at the middle point, yielding multiple rectangles with a base of x and the average height between the left and right. This tends to be more robust Trapezoidal Rule: ➢ Approximates function by fitting trapezoids underneath the 𝑏−𝑎 curve with a height of ℎ = 𝑁−1

Simpson’s Rule: ➢ Approximates function by fitting parabolas under the curve. Must use an even number of intervals. ➢ Pros and cons: more computationally expensive, but better fit Numerical Solutions to ODEs: ➢ Many ways to solve differential equations: Euler’s method and Runge-Kutta method

State-Space: ➢ Every ODE can be decomposed into a system of first order differential equations, for the numerical build in ODE solution techniques, you need to break your system down into a system of simultaneous first order differential equations. This is sometimes known as a “state-space” approach ➢ The number of 1st order equations will be equal to the sum of number of independent variable(s) times the order Images: ➢ Image data is stored in MATLAB using matrices ➢ Pcolor creates a pseudocolor checkerboard plot – rectangular array of cells(color spec) ➢ Matrices that represent images typically start in the top left hand corner-image, imagesc ➢ MATLAB generally recognizes three different techniques for storing and representing images: intensity images(gray scale), indexed images, RGB(true color) images ➢ Built in images: flujet,...