Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 2150 > 2 Lists and nums > Flashcards

2 Lists and nums Flashcards

1
Q

include

A

A growable array!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Iterator

A

-nested type of vector that represents position

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

iterator.begin() or iterator.end()

A

makes a pointer like object to the front or back of the vector

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

itr++
itr–
*itr
itr==itr

A

move forward
move backward
returns reference to object at itr location
true if same location

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

for ( vector::iterator it = v.begin();
it != v.end(); it++ )
cout &laquo_space;*it &laquo_space;endl;

A

this is the way to iteratew through aa vector with an iterator

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Stacks

A

push
pop
top

pancakes!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

7 2 3 + 8 *3+

A

50? I think?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Linked list?

A

Has every object point to the next with a next attribute as the next object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Queues

A

enqueue
dequeue
front()
back()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

abstract data types meaning

A

data type without specifics about language!!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How many hex digits is a byte?

A

2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How many bits is a byte?

A

8

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Unsigned int

A

no sign, 0 up to some number

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

a type can hold?

A

2^n -1 where n is number of bits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Switching endian-ness means what?

A

Swapping the BYTES!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

0xdeadbeef is big endian.

Whats little endian form of this?

A

0xefbeadde

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

1111 0101 0000 1010

to little endian?

A

0000 1010 1111 0101

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Point of two’s compliment?

A

to avoid two representations for zero

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Int range vs unsigned int

A

-2^31 to 2^31 -1 is int

0 to 2^31 -1 is unsigned int

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

pros/cons of fixed point real representation

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

0x41c80000 (big end float) to decimal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Largest positive float

A

2 * 2^127

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

smallest positive float

A

1.175494 x 10-38

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Are floats spacially uniform?

A 
No! 
Make the following numbers the next highest number
1.23 -> 1.24
12.3 -> 12.4
123 -> 124
1230 -> 1240
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

convert 42.125 to binary

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Floating point precision errors

A

.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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

given a=1;
b = .1+.1+.1+.1+.1+.1+.1+.1+.1+.1
c = .99999999999999999999

c==b?
b==a?

A

c==b

b!=a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

How to solve floating point precision errors?

A

-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;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What should you do to avoid floaating point nums?

A

USE RATIONALS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Two ways to declare an array

A

int someInts[3];

int someInts[] = {3,4,5};

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Will compiler catch out of index bounds errors with arrays?

A

No! no index checking

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

How to copy an array?

A

Element by element! You cannot just do ‘=’.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

How to compare arrays?

A

Compare value by value…. == will compare the address of first(0th) element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Arrays are POINTERS to the beginning element of the array (T/F)

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

int someInts[3];

cout &laquo_space;someInts;

A

will print the &someInts[0]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

int* someInts = new int[3];

What’ll this do?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

&someInts[i] equation?

A

{address of someInts} + (sizeof(int) * i)

43
Q

How to declare a multidimensionl int array with 2 rows and 4 columns called ERIC?

A

int ERIC[2][4];

44
Q

How to think of multidimensioonal arrays?

A

Lists inside lists!

45
Q

Row major order?

A

first row values, then second row, then third row

46
Q

int ERIC[4][3] = {{0,1,2},{3,4,5}.{6,7,8},{9,10,11}};

cout &laquo_space;ERIC[1][2];

A

5

47
Q

int ERIC[4][3] = {{0,1,2},{3,4,5}.{6,7,8},{9,10,11}};

cout &laquo_space;ERIC[3][1];

A

10

48
Q

How to enter command line parameters?

A 
int main(int argc, char ** argv) 
or
int main(int argc, char* argv[])

they are same thing!

49
Q 
Explain the parameters!
int main(int argc, char* argv[])

(what is char* mean?)

A

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
Q

How to convert from c style string to string in c++!

A 
char* x;
string s(x);
now s is a string!
51
Q

Ω(g) means?

A

big-omega

-functions that grow at least as fast or faster!

52
Q

Θ(g)

A

big-theta

-functions that grow at the same rate

53
Q

O(g)

A

big-oh

-functions that grow no faster than g, or slower

54
Q

When do we care about orders of growth?

A
  • FOR BIG INPUT SIZES, as limit approaches infinity!

- for smaller ones, it doesn’t really matter much

55
Q

f(n) ∈ O(g(n)) or f ∈ O(g)

meaning?

A

f(n) grows no faster than g(n)

56
Q

f(n) ∉ Ω(g(n)) or f ∉ Ω(g)

meaning?

A

f(n) doesn’t grow at least as fast as g(n)… thus

57
Q

What should you always analyze?

A

WORST CASE runtime

58
Q

What must be n to be an order of growth?

A

POSITIVE

59
Q

What does it mean that we don’t care about constants?

A

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
Q

How to show something is O(g) or Omega(g)?

A
  • 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
Q

How to show Theta(g)?

A

Show its O(g) and Omega(g)! DO BOTH

62
Q

Does n belong to O(n^2)?

A

Yes!, c=1, n0=2 works! So this is true.

63
Q

Does 10*n belong to O(n)?

A

Yes! c=11, n0=2 works with this.

So this is true

64
Q

Does n^2 belong to O(n)?

A

…idk probs should figure this out

65
Q

Given f belongs to O(H) and G doesn’t belong to O(H).

Is this true?
For all m, f(m) < g(m).

A

noppe.. small inputs we’re not sure

66
Q

Given f belongs to O(H) and G doesn’t belong to O(H).

Is this true?
For some m, f(m) < g(m).

A

Yep

67
Q

If given something like that what should you do?

Given f belongs to O(H) and G doesn’t belong to O(H).

A

DRAW GRAPHS!

68
Q

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).

A

YERP

69
Q

Lower bound is?

A

Omega!

70
Q

Little-oh?

A

Upper bound NOT type bound

71
Q

Type bound meaning?

A

equal to

72
Q

Big oh is what?

A

upper bound and type bound!

73
Q

f(n) is STRICTLY less than g(n) meaning?

A

Little oh.

74
Q

Little omega?

A

LOWER BOUND AND TYPE BOUND

75
Q

little theta?

A

DOESN’T EXIST

76
Q

type of O(g(n))?

A

A set! Thus nothing can be = to O(g(n))… only belong to with that E thing

77
Q

Are all orders of growth transitive?

A

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
Q

Are all orders of growth reflexive?

A

Yes

f belongs to theta(f)

79
Q

Are all orders of growth symmetric?

A

Nope! Only Big theta… this makes sense!

if f belongs to theta(g) then g belongs to theta(f)

80
Q

Do bases matter in logs?

A

Nope. The shape is the same, we don’t care about constants

81
Q

linear

A

n

82
Q

log-linear

A

n log n

83
Q

quadratic

A

n^2

84
Q

cubic

A

n^3

85
Q

exponential

A

2^n

86
Q

What do for loops run in?

A

linear time or n

87
Q

What do nested for loops run in?

A

runtime of the statement * n^2

88
Q

Consecutive statemenmts runtime?

A

maximum runtime of individual statements! so find the most inefficient part and use that

89
Q

runtime for if/else statements

A

use whichever has the longer runtime + time for the if/else test

90
Q

theta(1) meaning?

A

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
Q

Why is “finding kth element in array or list” constant time?

A

Machine just plugs g into a formula and extracts value at that memory address.

92
Q

theta(log n) meaning?

A
  • occurs when the search space or the outcome space is halved every time!
  • binary search tree find
93
Q

theta(n) meaning?

A

-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
Q

theta(n log n) meaning?

A

-linear number of steps, but each one times log n times
OR
-log n steps, each one times n time

95
Q

theta(n^2)

A

2 nested for-loops

96
Q

theta(2^n)

A
  • trying EVERY possible solution… and there are only 2 options for each one and n digits!
  • ya know this from probability ;)
97
Q

Single linked list vs doubly linked list

A

single only goes one direction… like only has .next()

double has next and previous!

98
Q 
Class is List
Operation is poop which returns a class of poopy. How would you do this in the .cpp file of List?
A

poopy List::poop() {
return this.poop;
}

99
Q

Notation for copy constructor? General implementation method?

When used?

A

className::className(const className &x) {
go through and make a new object, assign same attributes as x
}

Used with
List list2 = list1;

100
Q

Notation for copy assignment operator? General implementation method?

When used?

A

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
Q

Calculate this:

20 10 - -3 10 - - 2 +

A

21

102
Q

You have an executable file a.out.

Make the input for it addition.txt in cmd line.

A

./a.out < addition.txt

103
Q

Read in input continuously and print it.

A

string x;
while (cin&raquo_space; x) {
cout &laquo_space;x &laquo_space;” “;
}

104
Q

Convert -15.125 to little end hex and big end hex

A

0x800cc2 little
0xc20c80 big

right?

CS 2150 (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions