2 Lists and nums Flashcards
(104 cards)
1
Q
include
A
A growable array!
2
Q
Iterator
A
-nested type of vector that represents position
3
Q
iterator.begin() or iterator.end()
A
makes a pointer like object to the front or back of the vector
4
Q
itr++
itr–
*itr
itr==itr
A
move forward
move backward
returns reference to object at itr location
true if same location
5
Q
for ( vector::iterator it = v.begin();
it != v.end(); it++ )
cout «_space;*it «_space;endl;
A
this is the way to iteratew through aa vector with an iterator
6
Q
Stacks
A
push
pop
top
pancakes!
7
Q
7 2 3 + 8 *3+
A
50? I think?
8
Q
Linked list?
A
Has every object point to the next with a next attribute as the next object
9
Q
Queues
A
enqueue
dequeue
front()
back()
10
Q
abstract data types meaning
A
data type without specifics about language!!
11
Q
How to convert from decimal to radix?
A
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
12
Q
Convert from radix to decimal?
A
110 from base 5 to decimal
15^2 + 15^1 + 0*5^0 = 30
1010 = 2^3 + 2^1 = 10
13
Q
How many hex digits is a byte?
A
2
14
Q
How many bits is a byte?
A
8
15
Q
Boolean math 0+0 0+1 1+0 1+1
A
0+0 = 0
0+1 =1
1+0 =1
1+1=0 carry 1
16
Q
Unsigned int
A
no sign, 0 up to some number
17
Q
a type can hold?
A
2^n -1 where n is number of bits
18
Q
Switching endian-ness means what?
A
Swapping the BYTES!
19
Q
0xdeadbeef is big endian.
Whats little endian form of this?
A
0xefbeadde
20
Q
1111 0101 0000 1010
to little endian?
A
0000 1010 1111 0101
21
Q
Point of two’s compliment?
A
to avoid two representations for zero
22
Q
To find two’s compliment of a number with n-bit memory space.
A
-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)
23
Q
Overflow
A
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!
24
Q
Int range vs unsigned int
A
-2^31 to 2^31 -1 is int
0 to 2^31 -1 is unsigned int
25
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
26
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
27
Largest positive float
2 * 2^127
28
smallest positive float
1.175494 x 10-38
29
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
```
30
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
31
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
32
given a=1;
b = .1+.1+.1+.1+.1+.1+.1+.1+.1+.1
c = .99999999999999999999
c==b?
b==a?
c==b
b!=a
33
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;
```
34
What should you do to avoid floaating point nums?
USE RATIONALS
35
Two ways to declare an array
int someInts[3];
| int someInts[] = {3,4,5};
36
Will compiler catch out of index bounds errors with arrays?
No! no index checking
37
How to copy an array?
Element by element! You cannot just do '='.
38
How to compare arrays?
Compare value by value.... == will compare the address of first(0th) element
39
Arrays are POINTERS to the beginning element of the array (T/F)
True
40
int someInts[3];
| cout << someInts;
will print the &someInts[0]
41
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
42
&someInts[i] equation?
{address of someInts} + (sizeof(int) * i)
43
How to declare a multidimensionl int array with 2 rows and 4 columns called ERIC?
int ERIC[2][4];
44
How to think of multidimensioonal arrays?
Lists inside lists!
45
Row major order?
first row values, then second row, then third row
46
int ERIC[4][3] = {{0,1,2},{3,4,5}.{6,7,8},{9,10,11}};
cout << ERIC[1][2];
5
47
int ERIC[4][3] = {{0,1,2},{3,4,5}.{6,7,8},{9,10,11}};
cout << ERIC[3][1];
10
48
How to enter command line parameters?
```
int main(int argc, char ** argv)
or
int main(int argc, char* argv[])
```
they are same thing!
49
```
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
50
How to convert from c style string to string in c++!
```
char* x;
string s(x);
now s is a string!
```
51
Ω(g) means?
big-omega
| -functions that grow at least as fast or faster!
52
Θ(g)
big-theta
| -functions that grow at the same rate
53
O(g)
big-oh
| -functions that grow no faster than g, or slower
54
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
55
f(n) ∈ O(g(n)) or f ∈ O(g)
| meaning?
f(n) grows no faster than g(n)
56
f(n) ∉ Ω(g(n)) or f ∉ Ω(g)
| meaning?
f(n) doesn't grow at least as fast as g(n)... thus
57
What should you always analyze?
WORST CASE runtime
58
What must be n to be an order of growth?
POSITIVE
59
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!
60
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!
61
How to show Theta(g)?
Show its O(g) and Omega(g)! DO BOTH
62
Does n belong to O(n^2)?
Yes!, c=1, n0=2 works! So this is true.
63
Does 10*n belong to O(n)?
Yes! c=11, n0=2 works with this.
| So this is true
64
Does n^2 belong to O(n)?
...idk probs should figure this out
65
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
66
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
67
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!
68
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
69
Lower bound is?
Omega!
70
Little-oh?
Upper bound NOT type bound
71
Type bound meaning?
equal to
72
Big oh is what?
upper bound and type bound!
73
f(n) is STRICTLY less than g(n) meaning?
Little oh.
74
Little omega?
LOWER BOUND AND TYPE BOUND
75
little theta?
DOESN'T EXIST
76
type of O(g(n))?
A set! Thus nothing can be = to O(g(n))... only belong to with that E thing
77
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
78
Are all orders of growth reflexive?
Yes
| f belongs to theta(f)
79
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)
80
Do bases matter in logs?
Nope. The shape is the same, we don't care about constants
81
linear
n
82
log-linear
n log n
83
quadratic
n^2
84
cubic
n^3
85
exponential
2^n
86
What do for loops run in?
linear time or n
87
What do nested for loops run in?
runtime of the statement * n^2
88
Consecutive statemenmts runtime?
maximum runtime of individual statements! so find the most inefficient part and use that
89
runtime for if/else statements
use whichever has the longer runtime + time for the if/else test
90
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
91
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.
92
theta(log n) meaning?
- occurs when the search space or the outcome space is halved every time!
- binary search tree find
93
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)
94
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
95
theta(n^2)
2 nested for-loops
96
theta(2^n)
- trying EVERY possible solution... and there are only 2 options for each one and n digits!
- ya know this from probability ;)
97
Single linked list vs doubly linked list
single only goes one direction... like only has .next()
double has next and previous!
98
```
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;
}
99
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;
100
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;
101
Calculate this:
20 10 - -3 10 - - 2 +
21
102
You have an executable file a.out.
Make the input for it addition.txt in cmd line.
./a.out < addition.txt
103
Read in input continuously and print it.
string x;
while (cin >> x) {
cout << x << " ";
}
104
Convert -15.125 to little end hex and big end hex
0x800cc2 little
0xc20c80 big
right?
