Blog

CS 199 (133) Final Cheat Sheet for (initialization; test; up…

CS 199 (133) Final Cheat Sheet for (initialization; test; update) { statement(s); … } if (test) { statement(s); } else if (test) { statement(s); } else { statement(s); } while (condition) { statement(s); } type name(parameters) { statement(s); … return expression; } Math Description fabs(value) absolute value sqrt(value) square root round(value) Rounds to the nearest whole number pow(b, e) base to the exponent power   User Input Description getline(cin, variable) reads an entire line of input as a string and stores in variable cin >> variable reads a single token and stores in variable as whatever type variable is declared as   Random Description rand() random integer from 0 to max number srand(time(0)) Seeds random with the current time   Strings String function name Description string(1, chr) converts a character into a string s.append(str) Adds str onto the end of s s.erase(index, length) Removes length number of characters starting at index s.find(str) s.rfind(str) Returns the starting position of str in s (first occurrence for find, last for rfind). Returns string::npos otherwise. s.insert(index, str) Inserts str into s starting at index s.length()  or  s.size() Returns the number of characters in s s.replace(index, len, str) Replaces length characters starting with the character at index with str. s.substr(start, length)  or s.substr(start) Returns a substring of s. Does not alter s.   Character Function Description tolower(ch1) Returns ch1 in lowercase toupper(ch1) Returns ch1 in uppercase isalnum(ch1) Returns true if ch1 is alphanumeric isalpha(ch1) Returns true if ch1 is alphabetic isdigit(ch1) Returns true if ch1 is a decimal digit islower(ch1) Returns true if ch1 is a lowercase letter ispunct(ch1) Returns true if ch1 is a punctuation character isspace(ch1) Returns true if ch1 is white-space isupper(ch1) Returns true if ch1 is an uppercase letter   Streams Stream function Description f.clear(); resets stream’s error state, if any f.close(); stops reading file f.eof() returns true if stream is past end-of-file (EOF) f.fail() returns true if the last read call failed (e.g. EOF) f.good() returns true if the file exists f.get() reads and returns one character f.open(“filename”);f.open(s.c_str()); opens file represented by given C string (may need to write .c_str() if a C++ string is passed) f.unget(ch) un-reads one character f >> var reads data from input file into a variable (like cin);reads one whitespace-separated token at a time getline(f&, s&) reads line of input into a string by reference;returns a true/false indicator of success   Vectors vector member functions Description v.push_back(value); appends value at end of vector v.pop_back(); removes the value at the end of the vector v.clear(); removes all elements v[i] or get(i) returns a reference to the value at given index, get throws an exception if i is out of bounds, [] doesn’t v.insert(iterator, value); inserts given value at the index the iterator points to v.empty() returns true if the vector contains no elements v.erase(start, stop); removes values from start iterator position (inclusive) to stop iterator (exclusive) v[i] = value;  replaces value at given index v.size() returns the number of elements in vector v.begin() returns an iterator pointing to the beginning v.end(); returns an iterator pointing to the end v.cbegin(); returns a const iterator pointing to the beginning v.cend(); returns a const iterator pointing to the end v.rbegin(); returns an iterator pointing to the beginning that moves backwards v.rend() returns an iterator pointing to the end that moves backwards   Stacks s.empty() returns true if stack has no elements s.top() returns top value without removing it s.pop() removes top value; does NOT return anything; s.push(value); places given value on top of stack s.size() returns number of elements in stack Queues q.pop() removes front value; does NOT return anything q.push(value); places given value at back of queue q.empty() returns true if queue has no elements q.front() returns front value without removing q.back() returns back value without removing (not a traditional queue operation – don’t use) q.size() returns number of elements in queue Sets Member Description s.insert(value); adds given value to set s.clear(); removes all elements of set s.count(value) returns 1 if the value is in the set, 0 otherwise s.empty() true if set contains no elements s.erase(value); removes given value from set s.size() number of elements in set s.begin() returns an iterator pointing to the beginning s.end() returns an iterator pointing to the end Maps Member Description m.clear(); removes all key/value pairs m.find(key) an iterator pointing to the element, m.end()if not found m[key]  or m.at(key) returns value mapped to given key; if not found, [] adds it with a default value, .at throws an exception m.empty() true if the map contains no pairs m[key] = value; adds a key/value pair; if key already exists, replaces its value m.erase(key); or m.erase(iterator); removes any pair for given key or any pair pointed at by the iterator m.count() returns number of pairs in map m.begin() returns an iterator pointing to the first element m.end() returns an iterator pointing to one after the last element  

Recall the implementation of a priority queue using a vertic…

Recall the implementation of a priority queue using a vertically-ordered tree called a heap. Recall that the heap structure “bubbles” elements up and down as they are added and removed to maintain its vertical ordering. Given the following string/priority pairs: a:9, b:2, c:5, d:6, e:0, f:7, g:1, h:4, i:3, j:8 a) Write the final array representation of the binary heap that results when all of the above elements are pushed (added in the given order) with the given priorities shown to an initially empty heap. This is a “minheap”, that is, priorities with lesser integer values are higher in the tree. Write your answer in the following format: {a:17, b:63, c:40} [afterAdd] b) After adding all the elements, perform 2 pop operations (remove-min operations) on the heap. Write the final array representation of the heap that results after the two elements are removed, in the same format. [afterRemove]

Give a tight bound of the nearest runtime complexity class f…

Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N. In other words, write the code’s growth rate as N grows. Write a simple expression that gives only a power of N using a caret ^ character for exponentiation, such as O(N^2) to represent O(N2) or O(log N) to represent O(log2 N). Do not write an exact calculation of the runtime such as O(2N3 + 4N + 14). // a) map m; for (int i = 1; i 0) { m.erase(i – 1); m[ i ] = “bar”; } } [c1] // b) vector list; for (int i = N; i >= 1; i–) { for (int j = 1; j