diff options
Diffstat (limited to '01-07.md')
| -rw-r--r-- | 01-07.md | 260 |
1 files changed, 260 insertions, 0 deletions
diff --git a/01-07.md b/01-07.md new file mode 100644 index 0000000..a10e53c --- /dev/null +++ b/01-07.md @@ -0,0 +1,260 @@ +[\<- 01/05](01-05.md) + +--- + +## Use Standard Library + +``` +#include <iostream> +``` + +- To use a function from `iostream`, need to specify the `std::___` namespace (since iostream belongs to the std namespace) +- To avoid having to write `std::` behind the `iostream` functions, you can write at the top `using namespace std;` + - You can have multiple `using namespace` specifications + - If a function name belongs to multiple namespaces that are called at the top (and each take the same number of parameters), this can lead to issues + +--- + +## Preconditions and Postconditions + +### Defining a Function + +``` +//example function definition for a function that squares an integer +int square(int A){ + return A*A; +} + +int B = square(2); //B will equal 4 +``` + +### Specifiying Pre and Post conditions + +- Preconditions - What must be true before calling your program/method +- Postconditions - What must be true/what will happen after your program returns + +- For the above function: + - Preconditions + - None (it is implied that the input must be an integer) + - Postconditions + - If precondition is satisfied, postcondition must be true + +### Examples + +``` +double get_sqrt(double A); +//preC A >= 0 : input has to be a double and non-negative +//postC returns square root of integer +``` + +- What will happen if the user calls the following: + +``` +get_sqrt(-1); +``` + +- The program will not work, it may even crash! + - Preconditions are important so that users know how to use the function without breaking it + +``` +void print_name(char *A); +//preC input has to be an array of characters (and non-NULL) +//preC array must be null-terminated ('\0' at the end) +//postC print the input to stdout with no spaces +``` + +### Assert + +- the `assert()` function can be used to enforce preconditions +- Example: + +``` +double get_sqrt(double A){ + assert(A >= 0); //to enforce precondition + + //body of the program goes here +} +``` + +- Alternative example without using `assert()` + +``` +double get_sqrt(double A){ + if(A < 0){ + //print error message and exit + } + + //body of the program goes here +} +``` + +- Detailed C++ Example + +``` +#include <iostream> +// uncomment to disable assert +// #define NDEBUG +#include <cassert> + +int main(){ + assert(10 + 10 == 20); + std::cout << "Execution continues past the first assert\n"; + + assert(12+12 == 20); + std::cout << "Execution continues past the second assert\n"; +} +``` + +### Static Assert + +- Static assert are all checked at compile time, rather than just whenever the program that the assert is called in is called + - `static_assert(A > 0)` + +- Detailed C++ Example + +``` +void foo(int *a){ + assert(a != NULL); + std::cout << *a << std::endl; +} + +void bar(int *a){ + static_assert(sizeof(a) == 8, "I can only compile on a 64-bit architecture!"); //to make sure the code is only compiled on a 64-bit architecture +} + +int main(int argc, const char *argv[]){ + int *a = new int(4); + foo(a); + bar(a); + + return 0; +} +``` + +### Advantages of Using Preconditions and Postconditions + +- Succinctly describes the behavior of a function without cluttering up your thinking with details of how the function works +- At a later point, you may reimplement the function in a new way but programs (which only depend on the precondition/postcondition) will still work with no changes. + +--- + +## Time Analysis + +### What is Time Analysis? + +- How fast the system is running +- How fast the algorithm is executed + - How many clock signals does it take +- Is it the algorithm's fault? + +### Time Analysis? + +- Time is a parameter that needs to be optimized! + - Time is $ + - Some problems are interactable + - Scalability +- Is it better to be faster? + - YES! - time is money! + - NO! - not always (for example, real time applications) + +### How to do Time Analysis? + +- Count the number of operations +- How?? + +``` +int *add_array(int *array1, int *array2, int N){ + for(i = 0; i<N, i++){ + array1[i] += array2[i]; + } + + return array1; +} +``` + +- Number of operations depends on the input size + +### Big-O Notation + +- Declares the ORDER of the number of operations +- O(1), O(n), O(n^2) + +### Various Big-O Notation + +|Complexity|Function|Common name | +|----------|--------|------------| +|Highest |n! |factorial | +| |2^n |exponential | +| |n^d, d>3|polynomial | +| |n^3 |cubic | +| |n^2 |quadratic | +| |nsqrt(n)| | +| |nlog(n) |quasi-linear| +| |n |linear | +| |sqrt(n) |root - n | +| |log(n) |logarithmic | +|Lowest |1 |contsant | + +### Examples + +|T(n) |Complexity| +|--------------------|----------| +|5n^3 + 200n^2 + 15 |O(n^3) | +|3n^2 + 2^300 |O(n^2) | +|5log2(n) + 15ln(n) |O(log(n)) | +|2log(n^3) |O(log(n)) | +|4n + log(n) |O(n) | +|2^64 |O(1) | +|log(n^10) + 2sqrt(n)|O(sqrt(n) | +|2^n + n^1000 |O(2^n) | + +### Big-O Comparisons + +- Different ways to solve a problem -> different complexity + +### Examples + +``` +for(i = 0; i<N; i++){ + statement; +} + +O(N) +``` + +``` +for(i = 0; i < N; i++){ + for(j = 0; j < N; j++){ + statement; + } +} + +O(N^2) +``` + +``` +for(int i = 1; i <= n; ++i){ + for(int j = 1; j <= i; ++j){ + statement; + } +} + +O(?) (to be continued...) +``` + +### Best Case/Worst Case Scenario + +``` +bool search(vector<int> arr, int item){ + for(i = 0; i < arr.size; i++){ + if(arr[i] == item){ + return true; + } + } + + return false; +} + +//if vector<int> arr{1, 2, 3, 4, 5} +search(arr, 1); //O(1) -> Best Case +search(arr, 5); //O(N) -> Worst Case |