Post-class 01/07

2 files changed, 271 insertions, 0 deletions

diff --git a/01-05.md b/01-05.md
index 6783f60..1c4eb0b 100644
--- a/01-05.md
+++ b/01-05.md
@@ -113,3 +113,14 @@ int *add_array(int *array1, int *array2, int N){
 	- All of the items in the new header files are part of a feature called the **standard namespace**, also called **std**
 	- When you use one of the new header files, your program should also have this statement after the include directives: `using namespace std;`
 	- Note: There are other alternatives that we will talk about later
+		- Namespaces are kind of like classes with a number of defined functions
+		- `::` is the scope resolution
+
+```
+functionGlobal();    //functionGlobal belongs to the global namespace
+A::functionA(); //functionA belongs to namespace A
+```
+
+---
+
+[01/07 ->](01-07.md)
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