# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# + [markdown] slideshow={"slide_type": "slide"}
# <img style="float: center; width: 100%" src="https://raw.githubusercontent.com/andrejkk/TalksImgs/master/FrontSlideUpperBan.png">
# <p style="margin-bottom:2cm;"></p>
#
# <center>
#     <H1> 3. Data structures in algorithms </H1>
#    
#
#
# <br><br>
#     <H3> <NAME>, Lucami, FE </H3>
#     <H4> Contact: prof. dr. <NAME>, <EMAIL>, skype=akosir_sid </H4>
# </center>
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 1 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> Goals  </div>
# </div>
#
#
# ## Goals
#
#
# - Recognize the importance of data structures and algorithms in optimization
# - Importance of computational (time) and spatial (memory) complexity
#
#
# - Main message
#
# <p>
#     
# **Computer program = data structure + algorithm**
#
# <p>
#     
# - Algorithm design does not begin with the procedure, but with data structure design
#
#
#
# #### Important concepts
# - Data structures
# - Algorithms
# - Determination of space complexity of algorithms
# - Size of the data 
# - Classes of complexity
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 2 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> Sections  </div>
# </div>
#
#
# ## ■ Sections (1)
#
# ### 3. 1. Algorithm and pseudocode
#
# ■ Definition and basic characteristics of an algorithm $\large{*}$
#
# ■ Pseudocode $\large{*}$
#
#
# ### 3. 2. Data structures
#
# ■ Data structure description $\large{*}$
#
# ■ Data structure types $\large{*}$
#
# ■ Data structure Stack
#
# ■ Data structure List
#
# ■ Data structure Queue
#
# ■ Data structure Graph
#
# ■ Data structure example: Breadth-first search
#
#  
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 3 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3. 1. Algorithm and pseudocode  </div>
# </div>
#
# ## ■ Sections (2)
#
# ### 3. 3. Computational and space complexity
#
# ■ Description of computational and space complexity $\large{*}$
#
# ■ Input data size $\large{*}$
#
# ■ Complexity class - definition $\large{*}$
#
# ■ Complexity class – list
#
# ■ Time and space (memory) complexity
#
# ■ Performing an algorithm complexity analysis
#
# ■ Example: Symmetric matrix decomposition
#
# ■ Algorithm complexity - notes
#
#
# ### 3. 4. Supplement: Software in optimization
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 4 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3. 1. Algorithm and pseudocode  </div>
# </div>
#
#
# ## ■ Introduction
#
# - Why the computational and space complexity is essential
# - Algorithm backtracking) solves any problem
# - Procedure
#  
#
# ```python
#  1: def backtrackR(n, S, k, x, resitev):
#  2:    # n depth of the tree S of the set of decisions, S [k] possible decision at the step k, k is the current step
#  3:    # x vector containing our previous decisions, x[0] is the decision on the first step, x[1] on the second etc
#  4:    for (i = 0; i < S[k].length; i++) {
#  5:        x = S[k][i];                    # i-th elt of the set S[k]
#  6:        if canLeadToSlution(k, x) {
#  7:            if (k == n) {                  
#  9:            solution.addNewSolution(x); 
# 10:        }                              
# 11:        else {
# 12:        # proceed to the next step by the solution x[i] = S[k][i]
# 13:        backtrackR(n, S, k + 1, x, solution);
# 14:      }
# 15:    }
# 16:  }
#
# ```
#
#
# - This algorithm has exponential complexity and is useless in practice
# - Therefore, the algorithms with reasonable complexity are needed
#
# <img style="float: right; width: 400; margin: -56px 20px 0 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/BackTrackAlg.png">
#
#
#
# <p style="margin-bottom:2cm;"><br><br><br><br><br></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 5 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3. 1. Algorithm and pseudocode  </div>
# </div>
#
#
# # 3. 1. Algorithm and pseudocode
#
# ■ Definition and basic characteristics of an algorithm
#
# ■ Pseudocode
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 6 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3. 1. Algorithm and pseudocode  </div>
# </div>
#
#
# ## ■ Definition and basic characteristics of an algorithm
#
#
# - **Definition (Algorithm):** _Algorithm a set of rules for solving a problem in a finite number of steps on a precisely defined input data_
#
#
# - Basic features of algorithms:
#     - Input data: input data defined;
#     - Results: always available at the end of execution;
#     - Accuracy:  all steps exactly defined;
#     - Deterministic: all results are dependent only on input data
#     - Finite number of steps: for any regular input data;
#     - Correctness : results are always as required;
#     - Generality: operable  on any input data;
#
#
#
# - Dependence on hardware:
#     - We limit to single processor  machines
#     - Turing machine
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 7 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3. 1. Algorithm and pseudocode  </div>
# </div>
#
#
# ## ■ Pseudocode
#
# - **Description (Pseudocode)** Abstract description of data structures or algorithm, independent of software implementation._
#
#
# - It specifies
#     - Input data
#     - Results
#     - Procedure to the selected level
#  
#  
# <img style="float: right; width: 250px; margin: -80px 20px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/PseudoC_Cholesky.png">
#  
#
#
# <p style="margin-bottom:2cm;"><br><br><br><br><br><br><br><br><br><br></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 8 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.2. Data structures  </div>
# </div>
#
#
#
# # 3.2. Data structures
#
# ■ Data structure description
#
# ■ Data structure types
#
# ■ Stack
#
# ■ List
#
# ■ Queue
#
# ■ Graph
#
# ■ Data structure example: Breadth-first search
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 9 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.2. Data structures  </div>
# </div>
#
#
# ## ■ Description of data structure
#
#
# **Description (Data structure)** _Data structure is a particular way of organizing data in a computer so that it can be used efficiently._
#
#
# - Data structure's description
#     - How composite data is stored
#     - Basic operations on these data: access, manipulation
#
#
# - The purpose of introducing data structures:
#     - Separate description data from a specific implementation in a programming language;
#     - It enables study of the universal properties such as correctness
#     - Determination of algorithms complexity 
#
#
# - There are:
#     - Primitive types: char, int ...
#     - Compound types: array, ...
#     - Abstract data structures: stack, queue, graph, ….
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 10 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.2. Data structures  </div>
# </div>
#
#
#
# ## ■ Data structure types
#
#
# - Primitive types
#     - Boolean (binary), Char, Float, Double, Integer, Enumerated;
#     - Purpose: Presentation of numbers
#
#
# - Composite types
#     - Array, Struct, Union, ...
#     - Purpose: Presentation of data fields (arrays, ...)
#
#
# - Abstract Data Types
#     - List
#     - Queue
#     - Stack
#     - Graph
#     - Purpose: presentation of complex data
#
#     
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 11 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.2. Data structures  </div>
# </div>
#
#
# ## ■ Data structure Stack
#
# - Use:
#     - „Reverse Polish notion“ RPN
#     - Von Neuman processor
#
#
#
# <img style="float: right; width: 200px; margin: -40px 20px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/PseudoC_Stack.png">
#
# <img style="float: left; width: 150px; margin: 20px 50px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/DataStructStack.png">
#
#
#
#
# <p style="margin-bottom:2cm;"><br><br><br><br><br><br><br><br></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 12 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.2. Data structures  </div>
# </div>
#
#
#
# ## ■ Data structure List
#
# - Usage
#     - List of  graph nodes 
#     - List of users , ....
#
#     
#
# <img style="float: right; width: 250px; margin: -100px 50px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/PseudoC_Queue.png">
#     
#
# <p style="margin-bottom:2cm;"><br><br><br><br><br><br><br><br></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 13 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.2. Data structures  </div>
# </div>
#
#
# ## ■ Data structure Graph
#
# - Notation $G = (V ,E)$
#     - Nodes (vertices) $V$: natural numbers
#     - Edges (links) $E=\{(u,v): u,v\in V\}$ 
#     
#     
# - Usage
#     - Telecommunication network
#     - Optimization algorithms
#
#
# <img style="float: right; width: 250px; margin: -60px 50px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/PseudoC_Graph.png">
#     
# <img style="float: left; width: 200px; margin: 20px 50px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/DataStructGraph.jpg">
#
#
#
# <p style="margin-bottom:2cm;"><br><br><br><br><br><br><br><br><br><br></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 14 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.2. Data structures  </div>
# </div>
#
#
#
# ## ■ Usage: Breadth-first search
#
# - Theoretical analysis: the algorithm is correct = (visits all nodes)
# - Independently of implementation
# - The introduction of new underlying operations for the analysis of complexity
#
#
# - Graph $G=(V, E)$
#
#     $V=\{1,2,3,4,5,6\}$ <br>
#     $E=\{(12),(15),(16),(23),(34),(35),(45),(46),(56)\}$
#     
#     
# <img style="float: right; width: 200px; margin: -50px 20px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/Algorithm_BFS.png">
#
#
#
# <p style="margin-bottom:2cm;"><br><br><br><br><br><br><br><br><br><br><br></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 15 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
#
# # 3.3. Computational (time) and space complexity
#
# ■ Description of computational and space complexity
#
# ■ Input data size
#
# ■ Complexity class - definition
#
# ■ Complexity class – list
#
# ■ Time and space (memory) complexity
#
# ■ Performing an algorithm complexity analysis
#
# ■ Example: Symmetric matrix decomposition
#
# ■ Algorithm complexity - notes
#
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 16 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
#
# ## ■ Description of computational and space complexity 
#
# - Why: 
#     - Crucial for applicability  of any algorithm;
#     - Algorithm „backtracking“ can solve any problem, but not in a reasonable (acceptable time);
#     
#     
# - Goal:
#     - How to perform the analysis of a given algorithm
#     - Classes of complexity
#     
#     
# - Types of complexity:
#     - **Worst case complexity**: number of operations (locations) that will not be exceeded for any input data; 
#     - **Average case complexity**: average number of operations (locations) for expected input data sets. Can be very different from worst case.  
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 17 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
#
# ## ■ Input data size
#
# - Data size is the input to the analysis of the algorithm complexity
# - Depends on the type of data and the algorithm
# - Types of input data and measuring the size of data
#
# <table border="2">
#   <tr>
#     <th>Data type</th>
#     <th>Size</th>
#     <th>Algorithm </th>
#   </tr>
#   <tr>
#     <td>Number $n$</td>
#     <td>$\log_2(n)$</td>
#     <td>Prime factorization</td>
#   </tr>
#   <tr>
#     <td>List $L$ </td>
#     <td>$|L|$</td>
#     <td>Sort</td>
#   </tr>
#   <tr>
#     <td>Matrix $A$</td>
#     <td>$A_1$</td>
#     <td>Invers</td>
#   </tr>
#   <tr>
#     <td>Graph $G=(V,E)$ </td>
#     <td>$\max(|V|, |E|)$ </td>
#     <td>Maximal spanning tree</td>
#   </tr>
# </table>
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 18 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
#
# ## ■ Complexity class - definition
#
# - We are interested in the algorithm complexity of large input data
#
#
#
# - **Definition** Let $f,g:ℕ\to ℝ_+$ be nonegative functions on natural numbers. nenegativni funkciji na pozitivnih naravnih številih. <br>
# Function $f$ belongs to the class $O(g(n))$, if there are constants $C_1>0$ and $N_1>0$ such that
# $$ f(n)\leq C_1 g(n) \mbox{za vse} n>N_1. $$
# Function $f$ belongs to the class $o(g(n))$, if there are constants $C_1>0$ and $N_1>0$ such that
# $$ \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0.  $$
#
#
# - Observe:
#     - Big $O$ means that the function is increasing at the same pace as the representative of the class
#     - Small $o$ means that the function is growing more slowly as the representative of the class
#
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 19 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
#
# ## ■ Time and space (memory) complexity 
#
# - Time complexity
#     - Notation $T(algorithm)$ [number of oprations = number ciklov]
#     - Basic operations: $+, -, *, /, \ldots$ - odvisno od strojne opreme
#     - Razmerje med $𝑇(𝑜𝑝)$ and $𝑇(𝑝𝑟𝑜𝑐)$;
#         - Python case: square root
#     - **Definition:** _Time complexity is the number of basic operations dependent on input data size_
#     
#     
#     
# - Space (memory) complexity
#     - Notation $M(algorithm)$ [number of basic memory units]
#     - Basic memory units:: byte or memory unit for one basic data  (like int)
#         - Python example: Cholesky decomposition
#     - **Definition:** _Space (memory) complexity the number required of memory units dependent on input data size._
#     
#
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 20 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
# ## ■ Complexity classes - list
#
# <table width="500" border="1">
#   <tr>
#     <th>Name</th>
#     <th>Class</th>
#     <th>Note</th>
#   </tr>
#   <tr>
#     <th>Constant</th>
#     <th>$O(1)$</th>
#     <th></th>
#   </tr> 
#   <tr>
#     <th>Log log</th>
#     <th>$O(\log(\log(n))$</th>
#     <th></th>
#   </tr> 
#   <tr>
#     <th>Log</th>
#     <th>$\log(n)$</th>
#     <th></th>
#   </tr>
#   <tr>
#     <th>Sublinear</th>
#     <th>$O(n^c)$, $c<1$</th>
#     <th></th>
#   </tr>
#   <tr>
#     <th>Linear</th>
#     <th>$O(n)$</th>
#     <th></th>
#   </tr>
#   <tr>
#     <th>N Log n</th>
#     <th>$O(n\log(n))$</th>
#     <th>Very usefull</th>
#   </tr>
#   <tr>
#     <th>Quadratic</th>
#     <th>$O(n^2)$</th>
#     <th>Usefull</th>
#   </tr>
#   <tr>
#     <th>Qubic</th>
#     <th>$O(n^3)$</th>
#     <th></th>
#   </tr>
#   <tr>
#     <th>Polinomial</th>
#     <th>$O(n^k)$, $k\geq 1$</th>
#     <th>Meja uporabnosti</th>
#   </tr>
#   <tr>
#     <th>Exponential</th>
#     <th>$O(c^n)$, $c>1$</th>
#     <th>Uselsess</th>
#   </tr>
#   <tr>
#     <th>Factorial</th>
#     <th>$O(n!)$</th>
#     <th></th>
#   </tr>
# </table>
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 21 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
# ## ■ Complexity class
#
#
# Complexity classes decides on algorithm usefulness;
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 22 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + slideshow={"slide_type": "slide"}
## Time complexity of slected classes
import numpy as np
import matplotlib.pyplot as plt


fig, ax = plt.subplots(figsize=(8, 6))

n_max = 12
n_lst = np.arange(n_max)+1
lin10n_lst = [10*n for n in n_lst]
lin20n_lst = [20*n for n in n_lst]
nlogn_lst = [n*np.log(n) for n in n_lst]
quadr_lst = [n**2 for n in n_lst]
qubic_lst = [n**3 for n in n_lst]
exp_lst = [2**n for n in n_lst]

ax.plot(n_lst, lin10n_lst, label='$10 n$')
ax.plot(n_lst, lin20n_lst, label='$20 n$')
ax.plot(n_lst, nlogn_lst, label='$n \log(n)$')
ax.plot(n_lst, quadr_lst, label='$n^2$')
ax.plot(n_lst, qubic_lst, label='$n^3$')
ax.plot(n_lst, exp_lst, label='$2^n$')
plt.legend()
plt.show


#<img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
# ## ■ Algorithm complexity analysis: worst case
#
# - Procedure of algorithm complexity analysis 
#     1. Determination of the input data size;
#     2. Determination of basic operations and their complexity;
#     3. Step by step analysis of pseudocode
#     4. Summation of terms
#     5.Analysis of the leading terms and algorithm complexity class determination
#
#
# - Measurement of the implementation - the timing on the basis of implementation
#     - Timing of implementation at the selected size of the data
#     - Analysis of the comparison with the basic operation	
#     - Fit models
#
#
# - Result of the analysis of the complexity class;
#
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 23 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
#
# ## ■ Example: matrix decomposition
#
# - Example: algorithm Cholesky decomposition $A = V.V^\top$
# - time complexity <br>
# $n^3/3 + O(n^2)$
# - Space complexity <br>
# $n^2/2 + O(n)$
# - Square root estimation: <br>
# $c n + O(1)$, $c=1,037$ 
#
#
#
# <img style="float: right; width: 250px; margin: 20px 50px 50px 0;" src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/PseudoC_Cholesky.png">
#
# <img style="float: left; width: 250px; margin: 20px 50px 50px 0;"src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/CholeskyComComp.png">
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 24 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# +
import numpy as np
from timeit import default_timer as timer
import matplotlib.pyplot as plt


p_num = 100
N = 1000000000000
dN = int(N/p_num)

# One operation time
y = np.sqrt(2)
start = timer()
y = 1 + 1
end = timer()
op_time = end - start

x_lst = range(1, N, dN)
time_lst = np.zeros(p_num)
n_count = 0
for x in x_lst:
    start = timer()
    y = np.sqrt(x)
    end = timer()
    time_lst[n_count] = (end - start) / op_time
    n_count += 1

fig, ax = plt.subplots(figsize=(6, 6))
ax.plot(x_lst, time_lst, label='')
plt.show()


# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
# ## ■ Algorithm complexity analysis : average case
#
#
# - Preocedure - computer simulation
#     1. Implement a random data generator / selector: $\{D_1, \ldots, D_N\}$ 
#         - Reprezentativity?
#     2. Complexity estimation $T(D_1), \dots, T(D_N)$ 
#     3. Average complexity: 
#         - $\overline{T}=\frac{1}{N}\sum_{i=1}^N T(D_i)$
#         - confidence interval
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 25 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.3. Computational (time) and space complexity  </div>
# </div>
#
#
#
# ## ■ Algorithm complexity - notes
#
# - If the **for** / **while** loops contain functions of the class $O(1)$, then
#     - Loop **for** (i=1 to n) has complexity $O(𝑛)$
#     - Nested loops <br>
#     **for** (i=1 to n) <br>
#         **for** (j=1 to n) <br>
#     has complexity $O(𝑛^2)$ etc. <br>
#     - ==> each nested loop ads one to the exponent
#     
#     
# - The source of complexity class $O(2^𝑛)$ is finding all subsets of a set $|𝐴|=𝑛$:
#     - Number of subsets of a size $k$ equals to $n\choose k$. 
#     - For small $k$ this is close to $n^k$ (polynomial), for $k$ close to $n/2$ is close to exponential function
#     - The number of all subsets is equal to $2^k$
#     
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 26 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "subslide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.4. Optimisation related software  </div>
# </div>
#
#
#
# # 3.4. Optimisation related software
#
# ## ■ List (1)
#
# ** IBM CPLEX ** software <br>
# CPLEX is a very wide spectrum optimization tool [http://www-03.ibm.com/software/products/us/en/ibmilogcpleoptistud/]. It is unofficially referred to as the best general tool that was used to successfully solve big real problems. It is a group of different algorithms for rescue, which are continuously updated and improved. It is distinguished by an automated algorithm for rescue algorithms, which, after prior analysis of the problem, independently selects the appropriate algorithm. It is a licensed tool with very high royalties, there is also an academic license.
#
# ** Software LP_solve ** <br>
# The LP_solve tool [http://sourceforge.net/projects/lpsolve/] is designed to solve problems of linear, integer and mixed programming, see Chapter 4. Although it's a simple tool, it can solve real problems. Due to its simple use, there is a lot of use, especially in the development of the optimization problem formulation. It is available in open source and for different operating systems. Supports the format of the LP input file.
#
# ** Software Gurobi ** <br>
# Gurobi is a licensed software for solving various optimization tasks [http://www.gurobi.com/]. It is characterized by an efficient user interface for formulation development and optimization task solving. Academic licenses are available. Supports client server configuration.
#
# ** XPRESS ** software <br>
# XPRESS [http://www.fico.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx] software optimization tool is distinguished for its efficient implementation in terms of dealing with very large and complex problems. Among their references are solutions of extremely large logistical problems.
#
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 27 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.4. Optimisation related software  </div>
# </div>
#
# ## ■ List (2)
#
# ** CASS ** software <br>
# The combinatorial auction solution suite [http://www.cs.ubc.ca/~kevinlb/downloads.html] is designed to solve combinatorial auctions. The problem of combinatorial auctions is algorithmically difficult. In this textbook we did not present it, although it is important for the field of telecommunications in terms of conducting auctions of communication resources such as, for example, assignment of frequencies. It is available in open-source formats.
#
# ** Computer infrastructure COIN-OR ** <br>
# COIN-OR Computer Infrastructure [http://www.coin-or.org/] is an initiative in the development of open-source software in the field of operational research. It brings together dozens of universities, institutes and businesses.
#
# ** Network simulator OPNET ** <br>
# OPNET telnet network simulator [http://www.opnet.com/] is considered to be the leading product in the field. It is a demanding tool that enables the simulation of the real environment in terms of integrating real TK building blocks (eg, routers that are on the market) and real terrain configurations. It was successfully used in a large number of designing and optimizing real networks. It is available under high licenses, and an academic license is also available.
#
# ** Network simulator NS-3 ** <br>
# Open source simulator [http://www.nsnam.org/] was created in a research environment and is intended for conceptual simulations. With time, users also made simulations that are closer to the real environment. Its predecessor NS-2 is still in use. It is available in open-source formats, it is more comfortable using it on the Linux operating system. It requires the user to know the programming languages C / C ++ and Tcl / Tk.
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 28 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.4. Optimisation related software  </div>
# </div>
#
#
# ## ■ List (3)
#
# ** Software Gretl ** <br>
# Gretl [http://gretl.sourceforge.net/] is an open source software tool for time analysis and econometrics. It shows good numerical stability of difficult methods (eg Hurst parameter estimates) and is in professional use.
#
# ** Gephi ** software tool <br>
# Gephi is an open source program for analyzing and drawing graphs [https://gephi.org]. It is especially suitable for analysis and visualization of large graphs such as social networks of a large number of users. It is implemented in the Java programming environment and with the expansion of social networks experiencing rapid development.
#
# ** Pajk Programming Software ** <br>
# The Pajk tool is specially developed for the analysis of large networks and is a Slovenian product [http://pajek.imfm.si/doku.php]. Its quality is computational efficiency. In our framework it is useful for analyzing the social networks of users of telecommunication services.
#
# ** Software GraphViz ** <br>
# The GraphViz tool is designed for beautiful drawing of graphs [http://www.graphviz.org]. This is a very difficult task because with the diversity of nodes and links it is not easy to draw transparent images. Visualization of graphs in data analysis is very important, and better solutions allow you to draw larger graphs and easier to summarize the essential characteristics.
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 29 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.4. Optimisation related software  </div>
# </div>
#
#
# ## ■ List (4)
#
# ** IBM SPSS Modeler ** Software <br>
# An effective machine learning tool IBM SPSS Modeler [http://www-01.ibm.com/software/analytics/spss/products/modeler] features a graphical user interface that covers the entire data analysis (without programming). It is one of the leading tools in business intelligence with an emphasis on solving big data problems. It is available in a licensed form.
#
# ** Software SAS ** <br>
# The SAS tool [http://www.sas.com/] is one of the leading tools in business analytics and business intelligence. It covers more than ten specialized tools, including the detection of fraud and user safety. It is available under license terms and is intended for professional use.
#
#
# ** Weka ** software
# Weka [http://www.cs.waikato.ac.nz/ml/weka/] is a tool for machine learning, used primarily by researchers for which it was also developed. It is distinguished by good support for various test plans. It is implemented in the Java programming environment and is available in open source.
#
# ** Software RapidMiner ** <br>
# RapidMiner and RapidAnalytics are open source tools for data mining and analytics [http://rapid-i.com/]. They are available in open source format and have full support through a graphical user interface (without programming).
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 30 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> 3.4. Optimisation related software  </div>
# </div>
#
#
# ## List (5)
#
#
# ** Matlab ** software <br>
# Matlab [http://www.mathworks.com] is a widely used tool for numerical analysis, used for both research and industrial purposes. It also offers optimization packages and predictive analytics. It is especially distinguished for solving non-linear optimization.
#
# ** Software Mathematica ** <br>
# The programming environment [http://www.wolfram.com/mathematica/] is primarily aimed at research work. It is considered to be the best tool for symbolic computing. It is suitable for transforming the criterion into a more effective form and studying the limitations of the optimization task. The user is quite demanding in terms of knowing the concepts on which it is built.
#
# ** Software tool R ** <br>
# The reproductive software tool R [http://www.r-project.org/] is primarily intended for statistical data processing and visualization. It also includes elements of machine learning and analytics. He is very popular in research circles.
#
# ** Orange Software ** <br>
# The Orange tool [http://orange.biolab.si/] is intended for the mining and visualization of data. It is a Slovenian product, which gradually also includes elements of machine learning. It is implemented in the Python programming language.
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 31</div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">

# + [markdown] slideshow={"slide_type": "slide"}
# <div style="display:flex;font-weight:bold;font-size:0.9em;">
# <div style="flex:1;width:50%;"> 3. Data structures in algorithms </div>
# <div style="flex:1;width:50%;text-align:right;"> Conclusions  </div>
# </div>
#
#
# ## ■ Conclusions
#
# - "Program = data structure + algorithm"
#     - The software design starts with the data structure;
#     - Basic operations of the algorithm operations data structures
#     - Analysis of the correctness of the algorithm is carried out on operations of data structures
#
#
# - Computational complexity is essential:
#     - The practical applicability only up to the manageable complexity
#     - Backtracking algorithm solves all problems
#
#
# - Design and implementation of algorithms
#     - First, the identification of the known solutions
#     - Excellent reference: Numerical recipes and C ++: http://www.nr.com/
#     - Code + proof of correctness and optimality
#     - Reliable documentation and code
#
#
#
# <p style="margin-bottom:2cm;"></p>
# <div style="width:100%;text-align:right;font-weight:bold;font-size:1.2em;"> 32 </div>
# <img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg">
# -



StarcoderdataJupyterScriptsDedupFiltered