2 Lists and nums Flashcards
include
A growable array!
Iterator
-nested type of vector that represents position
iterator.begin() or iterator.end()
makes a pointer like object to the front or back of the vector
itr++
itr–
*itr
itr==itr
move forward
move backward
returns reference to object at itr location
true if same location
for ( vector::iterator it = v.begin();
it != v.end(); it++ )
cout «_space;*it «_space;endl;
this is the way to iteratew through aa vector with an iterator
Stacks
push
pop
top
pancakes!
7 2 3 + 8 *3+
50? I think?
Linked list?
Has every object point to the next with a next attribute as the next object
Queues
enqueue
dequeue
front()
back()
abstract data types meaning
data type without specifics about language!!
How to convert from decimal to radix?
hard to explain here is a few examples
10 from decimal to binary: 10 = 2^3 + 2^1 = 1010 or 10/2 = 5 r 0 5/2 = 2 r 1 2/2 = 1 r 0 1/2 = 0 r 1
So 1010
30 from decimal to base 5: 30/5 = 6 r 0 6/5 = 1 r 1 1/5 = 0 r 1 so 110
Convert from radix to decimal?
110 from base 5 to decimal
15^2 + 15^1 + 0*5^0 = 30
1010 = 2^3 + 2^1 = 10
How many hex digits is a byte?
2
How many bits is a byte?
8
Boolean math 0+0 0+1 1+0 1+1
0+0 = 0
0+1 =1
1+0 =1
1+1=0 carry 1
Unsigned int
no sign, 0 up to some number
a type can hold?
2^n -1 where n is number of bits
Switching endian-ness means what?
Swapping the BYTES!
0xdeadbeef is big endian.
Whats little endian form of this?
0xefbeadde
1111 0101 0000 1010
to little endian?
0000 1010 1111 0101
Point of two’s compliment?
to avoid two representations for zero
To find two’s compliment of a number with n-bit memory space.
-Zero is n 0s
-Positive numbers:
-Max vlue is 2^n-1 -1
-Sign bit is zero
-This, zero is a “positive”
number! (and is all zeros)
-Negative numbers:
-max value is -2^n-1
-take the absolute value and encode it t binry
-flip ALL the bits
-add 1 (if 0101 then 0110)
Overflow
like adding 1 to 0111 1111 (OR 127)… which is 1000 0000, which is -128.
-need more bits to make sure max value isn’t hit!
Int range vs unsigned int
-2^31 to 2^31 -1 is int
0 to 2^31 -1 is unsigned int
pros/cons of fixed point real representation
pros:
- Less computationally demanding
- Good for CPUs that don’t have an FPU
- Number representation space is uniform
cons:
- Less flexible
- Nobody uses it anymore
- Small range of values
0x41c80000 (big end float) to decimal
bin 0100 0001 1100 1000 0000 0000 0000 0000
sign bit = 0 so positive
Exponent 1000 0011 = 131-127 = 4
Mantissa 100 1000 0000 0000 0000 0000 = 1.1001 in base 2 or 1+ 1/2 + (1/2)^4 = 1.5625
1.5625 * 2^4 = 25
Largest positive float
2 * 2^127
smallest positive float
1.175494 x 10-38
Are floats spacially uniform?
No! Make the following numbers the next highest number 1.23 -> 1.24 12.3 -> 12.4 123 -> 124 1230 -> 1240
convert 42.125 to binary
0 positive
42.125 = 2^5 + 2^3 + 2^1 + 2^-3 = 101010.001 in binary
or 1.01010001 *2^5
so
0
exponent = 5 + 127 = 132 (10000100)
mantissa = 01010001
0100 0010 0010 1000 1000 0000 0000 0000 is answer
Floating point precision errors
.1 can’t be represented! (and other numbers obviously) so it rounds! but the actual value IS .09999999999999, even though it rounds when you print
given a=1;
b = .1+.1+.1+.1+.1+.1+.1+.1+.1+.1
c = .99999999999999999999
c==b?
b==a?
c==b
b!=a
How to solve floating point precision errors?
-float prints 7 digits of accuracy, so add .0000001 to the num THEN compare
// C++: #include & compile with -lm
#define EPSILON 0.000001 bool foo = fabs (a-b) < EPSILON;
What should you do to avoid floaating point nums?
USE RATIONALS
Two ways to declare an array
int someInts[3];
int someInts[] = {3,4,5};
Will compiler catch out of index bounds errors with arrays?
No! no index checking
How to copy an array?
Element by element! You cannot just do ‘=’.
How to compare arrays?
Compare value by value…. == will compare the address of first(0th) element
Arrays are POINTERS to the beginning element of the array (T/F)
True
int someInts[3];
cout «_space;someInts;
will print the &someInts[0]
int* someInts = new int[3];
What’ll this do?
This will make a int pointer called someInts that points to the first element of the array.
IF YOU DO THIS, you must delete [] someInts; afterwards
&someInts[i] equation?
{address of someInts} + (sizeof(int) * i)
How to declare a multidimensionl int array with 2 rows and 4 columns called ERIC?
int ERIC[2][4];
How to think of multidimensioonal arrays?
Lists inside lists!
Row major order?
first row values, then second row, then third row
int ERIC[4][3] = {{0,1,2},{3,4,5}.{6,7,8},{9,10,11}};
cout «_space;ERIC[1][2];
5
int ERIC[4][3] = {{0,1,2},{3,4,5}.{6,7,8},{9,10,11}};
cout «_space;ERIC[3][1];
10
How to enter command line parameters?
int main(int argc, char ** argv) or int main(int argc, char* argv[])
they are same thing!
Explain the parameters! int main(int argc, char* argv[])
(what is char* mean?)
char* is a c-style string! thus its a list of c-style strings..
- “int argc” tells the number of of elements in argv +1… 0th element is the executable file (a.out)
- argv is a list of command line parameters with 0th value a.out(or something else) and the rest are whatever parameters
How to convert from c style string to string in c++!
char* x; string s(x); now s is a string!
Ω(g) means?
big-omega
-functions that grow at least as fast or faster!
Θ(g)
big-theta
-functions that grow at the same rate
O(g)
big-oh
-functions that grow no faster than g, or slower
When do we care about orders of growth?
- FOR BIG INPUT SIZES, as limit approaches infinity!
- for smaller ones, it doesn’t really matter much
f(n) ∈ O(g(n)) or f ∈ O(g)
meaning?
f(n) grows no faster than g(n)
f(n) ∉ Ω(g(n)) or f ∉ Ω(g)
meaning?
f(n) doesn’t grow at least as fast as g(n)… thus
What should you always analyze?
WORST CASE runtime
What must be n to be an order of growth?
POSITIVE
What does it mean that we don’t care about constants?
Constants change between computer processing times.
O(g) is set of functions such that
f(n) <= c*g(n) for all n >= n0
we don’t care about c!
How to show something is O(g) or Omega(g)?
- Pick a c value and an n0 value!
- Plug it in, show its true that its less than or greater than.
- Then say this works for all of them!
How to show Theta(g)?
Show its O(g) and Omega(g)! DO BOTH
Does n belong to O(n^2)?
Yes!, c=1, n0=2 works! So this is true.
Does 10*n belong to O(n)?
Yes! c=11, n0=2 works with this.
So this is true
Does n^2 belong to O(n)?
…idk probs should figure this out
Given f belongs to O(H) and G doesn’t belong to O(H).
Is this true?
For all m, f(m) < g(m).
noppe.. small inputs we’re not sure
Given f belongs to O(H) and G doesn’t belong to O(H).
Is this true?
For some m, f(m) < g(m).
Yep
If given something like that what should you do?
Given f belongs to O(H) and G doesn’t belong to O(H).
DRAW GRAPHS!
Given f belongs to O(H) and G doesn’t belong to O(H).
Is this true?
For some m0, all positive integers greater than m0, m, f(m) < g(m).
YERP
Lower bound is?
Omega!
Little-oh?
Upper bound NOT type bound
Type bound meaning?
equal to
Big oh is what?
upper bound and type bound!
f(n) is STRICTLY less than g(n) meaning?
Little oh.
Little omega?
LOWER BOUND AND TYPE BOUND
little theta?
DOESN’T EXIST
type of O(g(n))?
A set! Thus nothing can be = to O(g(n))… only belong to with that E thing
Are all orders of growth transitive?
Yes
If f belongs to O(g) and g belongs to O(h) then f belongs to O(h).
THIS IS FOR ALL 3 THINGIES
Are all orders of growth reflexive?
Yes
f belongs to theta(f)
Are all orders of growth symmetric?
Nope! Only Big theta… this makes sense!
if f belongs to theta(g) then g belongs to theta(f)
Do bases matter in logs?
Nope. The shape is the same, we don’t care about constants
linear
n
log-linear
n log n
quadratic
n^2
cubic
n^3
exponential
2^n
What do for loops run in?
linear time or n
What do nested for loops run in?
runtime of the statement * n^2
Consecutive statemenmts runtime?
maximum runtime of individual statements! so find the most inefficient part and use that
runtime for if/else statements
use whichever has the longer runtime + time for the if/else test
theta(1) meaning?
Constant time. Regardless of n, the running time will be constant…. for example getting a vector’s size, insert for link list, finding kth element in array or list
Why is “finding kth element in array or list” constant time?
Machine just plugs g into a formula and extracts value at that memory address.
theta(log n) meaning?
- occurs when the search space or the outcome space is halved every time!
- binary search tree find
theta(n) meaning?
-process each element, and constant number of steps per element
examples:
-printing/iterating through list, finding element in unsorted array/vector
-doubling size of array (cuz you copy every element into new array)
theta(n log n) meaning?
-linear number of steps, but each one times log n times
OR
-log n steps, each one times n time
theta(n^2)
2 nested for-loops
theta(2^n)
- trying EVERY possible solution… and there are only 2 options for each one and n digits!
- ya know this from probability ;)
Single linked list vs doubly linked list
single only goes one direction… like only has .next()
double has next and previous!
Class is List Operation is poop which returns a class of poopy. How would you do this in the .cpp file of List?
poopy List::poop() {
return this.poop;
}
Notation for copy constructor? General implementation method?
When used?
className::className(const className &x) {
go through and make a new object, assign same attributes as x
}
Used with
List list2 = list1;
Notation for copy assignment operator? General implementation method?
When used?
className& className::operator=(const className& x) {
-if they are equal return either one
-clear out everything in this, then copy everything from the argument to this
}
list2 = list1;
Calculate this:
20 10 - -3 10 - - 2 +
21
You have an executable file a.out.
Make the input for it addition.txt in cmd line.
./a.out < addition.txt
Read in input continuously and print it.
string x;
while (cin»_space; x) {
cout «_space;x «_space;” “;
}
Convert -15.125 to little end hex and big end hex
0x800cc2 little
0xc20c80 big
right?
