# Foundations of Computer Science

Tags | Computer science |
---|---|

Created | |

Updated |

# Notation

$n \in \mathbb{N}$ represents **items** for the algorithm given. This implies I either use $n=ceil(X)$or $n=floor(X)$ by a satisfies the problem presented.

$log_2(n)=lg(n)$

$f$ is faster than $g$, if $f$ is smaller than $g$ i.e. $f<g$

# 0. The Mechanization of Abstraction and Foundations of Computer Science

# Requisites

Epistemology

Logic

Metaphysics

What is science?

Citation: Your ideas vs the canon.

Kind of.

Good sources.

Public domain

## Definition of computer science

Issues related to the computer [1]

The discipline of computing —computer science— is the systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all of computing is, "What can be (efficiently) automated?" [2]

A 1995 U.S. government “blue book” defines it like this: “The systematic study of computing systems and computation. The body of knowledge resulting from this discipline contains theories for understanding computing systems and methods; design methodology, algorithms, and tools; methods for the testing of concepts; methods of analysis and verification; and knowledge representation and implementation.”

The discipline of computing —computer science— is the systematic study of algorithmic processes that describe and transform a domain of discourse -information-: their theory, analysis, design, delivery, efficiency, implementation, and application. The fundamental question underlying all of computing is, "What can be the true domain of discourse?" Tech and computer science are equal.

Logic == computation? https://philosophy.stackexchange.com/questions/42352/logic-and-computation-a-philosophical-viewpoint-on-curry-howard-isomorphism

https://www.youtube.com/playlist?list=PLH2l6uzC4UEW0s7-KewFLBC1D0l6XRfye

https://dl.acm.org/doi/10.1145/1272516.1272529

https://www.informatics-europe.org/images/ECSS/ECSS2015/slides/ECSS2015-Tedre.pdf

## 0.1 Milestones in computer architecture

The history of hardware can be divided into:

- the period of mechanical machines (before 1930)

- the period of electronic computers (1930–1950)

- and the period that includes the five modern computer generations.

- Cloud

- Quantum computer (1980-)

- Desktop Quantum Computer (2021-)

## 0.11 Milestones in software

## 0.2 Etymology

Computer. A **programmable machine is **usually electronic that can give outputs, retrieve, and process data. Does it use the EDVAC model?

https://denninginstitute.com/pjd/GP/GP-site/welcome.html

Underlying our approach to this subject is our conviction that ``computer science'' is not a science and that its significance has little to do with computers. The computer revolution is a revolution
in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called *procedural epistemology* -- the study of the structure of
knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects.
Mathematics provides a framework for dealing precisely with notions of ``what is.'' Computation provides a framework for dealing precisely with notions of ``how to.'' “Structure and Interpretation of Computer Programs,” *Mit.edu*, 2022. [Online]. Available: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-7.html#%_chap_Temp_4. [Accessed: 03-Jan-2022]

https://fgbueno.es/act/img/sdc2018m.pdf

Encyclopedia of Computer Science, 4th Edition. ISBN: 978-0-470-86412-8

https://plato.stanford.edu/entries/computer-science/

Terms for the practitioners of the field.

- computer scientist,

- turingineer,

- turologist,

- flow-charts-man,

- applied meta-mathematician,

- datology or data science?

- and applied epistemologist

## 0.3 Words

#### Traduction

Name | Computing | Computer science | Computer engineering | Information management | PROGRAMMING | Cybernetics | Software engineering | Electronic engineering | Telocommunications | Telematics | Information technology | Data processing |
---|---|---|---|---|---|---|---|---|---|---|---|---|

Spanish | Computacion | Ciencias computacionales | Ingenieria de la computacion | Informatica. Relacionado con humanidades. Admnistracion de la informacion. | Programacion. | Cibernetica | Ingenieria del software | |||||

German | ||||||||||||

Chinese | ||||||||||||

French | ||||||||||||

English |

- Difference between developing and automatizing?

Data Processing Industry.

Programming vs Coding?

electronic engineering

Practical Epistemology

Data. Transmittable and storable information by which computer operations are performed

https://www.etymonline.com/word/data

Data is not exactly a plural on Datum.

## 0.4 Fields

https://en.wikipedia.org/wiki/Computer_science#Fields

Computing

https://www.acm.org/binaries/content/assets/education/curricula-recommendations/cc2020.pdf

## 0.6 Institutes and corporations

IEEE

ACM

MIT

Stanford

Cambridge

Berkley

ANSI

Dr. Dobb's Journal

Oxford

Bell Labs

Springer Science+Business Media

Addison-Wesley

RAND corporation

FANG

Y-Combinator

Xerox PARC

IBM

**Tech Model Railroad Club**

### How to choose the material?

- Books from someone have built great stuff.

## Learning Path

https://ocw.mit.edu/search/?s=department_course_numbers.sort_coursenum

https://online.stanford.edu/explore?type=course

## 0.7 Characters

Edsger W. Dijkstra. Software Engineering Visioner.

Bertrand Meyer

Dennis Ritchie

Andrey Kolmogorov

Ken Thompson

Peter Chen

Edgar Frank "Ted" Codd

Donald Knuth

Linus Torvalds

Lord Kelvin

Alan Turing

Hedwig Eva Maria Kiesler

John von Neumann

Jonathan James

Barbara Liskov

Grady Booch

Andrew S. Tanenbaum

George Boole (self-taught)

Konrad Zuse (German civil engineer)

David A. Huffman

Anatoly Karatsuba

Arthur C. Clarke

Hal Abelson

Aaron Swartz

Alan Perlis

Gang of Four (GoF). Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides

Kent Beck

John Atanasoff

Alan Kay. The best way to predict the future is to invent it. Der Streit der Fakultäten.

Herman Hollerith (self-taught)

Vannevar Bush

Héctor García-Molina (advisor to Sergey Brin)

Jan Wielemaker

Robert C. Martin

Sir Charles Antony Richard Hoare.

Martin Fowler

James Gosling

George Stibitz. Creator of the term "digital".

Claude Shannon. The father of information theory.

Paul Graham

Rob Pike

https://en.wikipedia.org/wiki/List_of_pioneers_in_computer_science

Martin Odersky

Niklaus Emil Wirth

George Hotz

## Others

Robert S. Langer

### Open-source

Bram Moolenaar

**Miguel de Icaza**

### Business people

Bill Gates

Steve Jobs

Kim Dotcom

Sergey Brin

Larry Page

## Literature and computer science culture

Asimov 1984 **Bicentennial Man**

Jargon File or Hacker Dictionary

**Eric S. Raymond **The Cathedral and the Bazaar

* Unnatural Selection: Why the Geeks Will Inherit the Earth. *Mark Roeder

Gödel, Escher, *Bach*: an Eternal Golden Braid (English)

**Hackers & Painters: Big Ideas from the Computer Age 1st Edition**

## Micro stories

Tanenbaum–Torvalds debate

**AN OPEN LETTER TO HOBBYISTS, by Bill Gates**

IBM vs Harvard by IBM ASCC

Homebrew club

**Taligent**

First Computer Science department was Cambridge

http://xahlee.org/wordy/p/russell-lecture.html

## Prices

Turing Award

Gödel Prize

Edsger W. Dijkstra Paper Prize in Distributed Computing,in short Dijkstra Prize

### Operation research relationship

## Money and business: be Alfa or Beta

**The Top 8 Tech Companies to Intern at in 2022**

**World War II, Operation research, logic, and Hilbert**

NATO and software

University story

https://es.quora.com/Está-el-grado-en-Ciencias-de-la-Computación-sobrevaluado

## 0.81 Curriculum and classification. The books and resources.

## 0.8 Turing model

## 0.9 Von Neumann Model?

This was teamwork, then We called EDVAC Model from First Draft of a Report on the EDVAC, no Von Neumann Model.

## 0.10 Computer components

## 0.11 Computer Science as a Discipline

## 0.12 Outline of the course

## 0.13 Number systems

### 0.130 Positional number systems

Assume $(0)_b=0$ and $(1)_b=1$

Convert from $b$-base to decimal. If $b\geq 2,$ then

Convert from decimal to $b$-base.

```
def a(number, k):
return math.trunc(number / math.pow(10, k)) % 10
def length(number):
return math.trunc(math.log10(number)) + 1
def from_base_to_decimal(number, b):
acc = 0
for k in range(length(number)):
acc +=def from_decimal_to_base(number, base):
return acc
```

```
def from_decimal_to_base(number, base):
base_number = ""
q = number
while q > 0:
qk = trunc(q/base)
ak = q - base*qk
base_number = str(ak)+base_number
q = qk
return base_number
```

```
function from_base_to_decimal(number, base) {
return String(number).
split('').
map((n)=> parseInt(n, base)).
reduce((acc, current, index, array) => {
console.log(`${current}+${base}*${acc}=${current+base*acc}`);
return current+base*acc;
});
}
```

```
function from_decimal_to_base(number, base) {
if (base <= 1) {
return;
}
base_number = ""
q = number
while (q>0)
{
qk = Math.trunc(q/base)
ak = q - base*qk
console.log(`${base * qk + ak}=${base}*${qk}+${ak}`);
base_number = ak.toString(base).toUpperCase()+base_number
q = qk
}
return base_number
}
```

```
function from_any_base_to_any_base(number, start_base, end_base) {
console.log(`from base ${start_base} to decimal`);
const start_number = from_base_to_decimal(number, start_base);
console.log(`from decimal to base ${end_base}`);
return from_decimal_to_base(start_number, end_base);
}
```

Fast algorithm.

http://www.opentextbookstore.com/mathinsociety/2.4/HistoricalCounting.pdf

https://www.gcu.ac.uk/media/gcalwebv2/gcuoutreach/NUMBERS & NUMBER SYSTEMS.pdf

https://www.radford.edu/~wacase/Number Systems Unit Math 116.pdf

https://www.cl.cam.ac.uk/teaching/1415/CompFund/NumberSystemsAnnotated.pdf

https://en.wikipedia.org/wiki/Numeral_system

https://www.cs.princeton.edu/courses/archive/spr15/cos217/lectures/03_NumberSystems.pdf

http://www.unitconversion.org/unit_converter/numbers-ex.html

### 0.1311 Binary and boolean function

Binary vs boolean and bits

### 0.132 Nonpositional Number Systems

## 0.14 Data Storage

### 0.140 Data Types

### 0.141 Storing Numbers

**Method of complements**

**Nine's complement**

**Ten's complement**

**One's complement**

One's complement is an operation to inverting bits.

Worked examples.

$m=-56,C(56)=2^8-56-1=199$

**Two's complement**

There is only one zero in two’s complement notation.

One's complement + 1. Because $(0)_{one's complement}=(1)_2$, but $(0)_{two'scomplement}=(0)_2$

Worked examples.

$m=-56,C_{8 bits}(56)=2^8-56=200$

Trick.

https://www.csestack.org/how-to-find-2s-complement/

Example. $11100110$ two's complement format to integer.

### How to encode negative numbers in binary number systems?

## Gray code

## Base −2

## 8–4–2–1 code is also called BCD (Binary coded Decimal)

## Sign and magnitude

## Offset binary, also called excess-K or biased representation

Excess-8 (biased)

Zig-zag encoding

Excess-3, 3-excess or 10-excess-3 binary code (often abbreviated as XS-3, 3XS or X3), shifted binary or Stibitz code. https://en.wikipedia.org/wiki/Excess-3

## Complements

- Ones' complement

## Two's complement

Two's complement is the easiest to implement in hardware, which may be the ultimate reason for its widespread popularity. Choo, Hunsoo; Muhammad, K.; Roy, K. (February 2003). "Two's complement computation sharing multiplier and its applications to high performance DFE". IEEE Transactions on Signal Processing. 51 (2): 458–469. doi:10.1109/TSP.2002.806984.

#### Summary

Contents of memory | Unsigned | Sign-and-magnitude | Two's complement | One's complement |
---|---|---|---|---|

0000 | 0 | 0 | +0 | 0 |

0001 | 1 | 1 | +1 | 1 |

0010 | 2 | 2 | +2 | 2 |

0011 | 3 | 3 | +3 | 3 |

0100 | 4 | 4 | +4 | 4 |

0101 | 5 | 5 | +5 | 5 |

0110 | 6 | 6 | +6 | 6 |

0111 | 7 | 7 | +7 | 7 |

1000 | 8 | -0 | -8 | -7 |

1001 | 9 | -1 | -7 | -6 |

1010 | 10 | -2 | -6 | -5 |

1011 | 11 | -3 | -5 | -4 |

1100 | 12 | -4 | -4 | -3 |

1101 | 13 | -5 | -3 | -2 |

1110 | 14 | -6 | -2 | -1 |

1111 | 15 | -7 | -1 | -0 |

Notes | The leftmost bit defines the sign. If is 0, the integer is positive else negative. | The leftmost bit defines the sign. If is 0, the integer is positive else negative. | The leftmost bit defines the sign. If is 0, the integer is positive else negative. This has two 0. |

**How to encode real numbers in binary number systems?**

## Fixed-point

## Floating-point

IEEE 754 format

three parts: a sign, a shifter, and a fixed-point number.

### 0.142 Storing Text

A character is an element of grammar (English, Spanish, ...) + accepted human-computer interface by convention (backspace, delete, escape, @, ...), i.e. a code. $code=\{character | character \in grammar \text{ or } character \in \text{ human-computer interface} \}.$

For example, English grammar is $\{A,B,C,...,Z\}\cup \{a,b,c,...,z\} \cup \{.,;,-,+,!,...,*\} \cup \{0,1,2,3,...,9\}$ and human-computer interface in ASCCI is$\{NUL,SOH,Space,...CAN\}$.

We can represent each character with a bit pattern of n bits (bit pattern length=n). If we have a $code=\{A\}$, his cardinality $|code|=1$. Then computer understands $\text{computer code}=\text{bit patterns =}\{0\}$ and $\text{bit pattern length}=1$

$code=\{A,B\},|code|=2,\text{bit pattern}=\{0,1\},\text{bit pattern length}=1$ .

$code=\{A,B,C,D\},|code|=4,computer=\{00,01,10,11\},\text{bit pattern length}=2$.

$|code|=8,\text{bit pattern length}=3,lg(8)=3$.

Therefore, $\text{bitPatternLength}=lg(|code|)$.

### 0.1421 ASCII Code and UNICODE

ASCII.

Mackenzie, Charles E. (1980). Coded Character Sets, History and Development (PDF). The Systems Programming Series (1 ed.). Addison-Wesley Publishing Company, Inc. pp. 6, 66, 211, 215, 217, 220, 223, 228, 236–238, 243–245, 247–253, 423, 425–428, 435–439. ISBN 978-0-201-14460-4. LCCN 77-90165. Archived (PDF) from the original on May 26, 2016. Retrieved August 25, 2019.

ASA standard X3.4-1963

https://stackoverflow.com/questions/1761051/difference-between-n-and-r

### 0.143 Storing Audio

### 0.144 Storing Images

### 0.145 Storing Videos

## 0.15 Operations on Data

### 0.150 Logic Operations

### 0.151 Shift Operations

### 0.152 Arithmetic Operations

**Sum of naturals.**

Rules. 0+0=0, 0+1=1, 1+0=1 and 1+1=10

**Subtraction of naturals (No complements).**

Rules. 0-0=0, 1-0=1, 1-1=0, 0-1=10-1=1

https://www.calculator.net/binary-calculator.html

**Subtraction of naturals (Two's complement)**

$91-46=91+(-46)=45$

https://www.exploringbinary.com/twos-complement-converter/

### Why does char - '0' successfully convert a char to int in C?

https://www.quora.com/Why-does-char-0-successfully-convert-a-char-to-int-in-C/answer/Greg-Kemnitz

## Nine's complement

Pascaline.

### 0.153 Bitwise operations in C

Bitwise Operators in C and C++

`x & 1`

is equivalent to `x % 2`

(no sign).

if x&1 is true, then x is an odd number.

First of all, an example:

```
5(00000101)& 1(00000001)
00000101 &
00000001
00000001 (1 True)
```

Informal Proof. For non-complement binary number. Where $n$ is position left to right.

```
std::list<int> v = { 1, 2, 3, 4, 5, 6 };
auto it = v.begin();
while (it != v.end())
{
// remove odd numbers.
if (*it & 1)
{
// `erase()` invalidates the iterator, use returned iterator
it = v.erase(it);
}
// Notice that the iterator is incremented only on the else part (why?)
else {
++it;
}
}
```

`x >> 1`

is equivalent to `x / 2`

https://www.cprogramming.com/tutorial/bitwise_operators.html

### 0.154 Boolean Algebra and Digital Logic: Arithmetic Logic Unit

### Summary

## Chapter notes

**Things a Computer Scientist Rarely Talks About **https://www-cs-faculty.stanford.edu/~knuth/things.html http://web.stanford.edu/group/cslipublications/cslipublications/pdf/1575863278.pdf

HOW ARISTOTLE CREATED THE COMPUTER

## 0.16 The Mechanization of Abstraction

### 0.161 Data model

### 0.162 Domain of discourse

- the domain of discourse is also called the universe of discourse, universal set, or simply universe.

### 0.163 Abstract data type

### 0.164 Side effect

## 0.17 Languages

## 0.18 Jobs and Paths

## 0.19 Standards

## 0.20 Technology Sector and what is your society's role as a computer scientist?

What is the technology sector and what sector would like you to work for?

semiconductors, software, networking and Internet, and hardware.

### 0.2 Maquinaria y automatización (Marx) | ¿Las máquinas crean valor? ¿Qué es el General Intellect?

https://www.youtube.com/watch?v=OBt_8MopVGg&ab_channel=DiálogoMarxista

### 0.21 Cyberpunk y la etica

https://www.youtube.com/watch?v=Re7ZEDodXtU

https://www.youtube.com/watch?v=O00Yc1TdYJA

https://www.youtube.com/watch?v=Ep1Vf2Vv2Gc&t=344s

## 0.22 Es un trabajo de mierda? Hay un suficiente trabajo? Debemos crear products obsolentes?

Trabajo de mierda. David Graeber

## Problem set

### References

[1] Forouzan, B., 2017. Foundations of Computer Science: 4th Edition. Andover: Hampshire: Cengage Learning EMEA.

[2] Denning, P. J., Comer, D. E., Gries, D., Mulder, M. C., Tucker, A., Turner, A. J., & Young, P. R. (1989). Computing as a discipline. Communications of the ACM, 32(1), 9–23. doi:10.1145/63238.63239

http://mmc.geofisica.unam.mx/femp/Herramientas/Lenguajes/Java/JavaBasico/Libro.pdf

http://infolab.stanford.edu/~ullman/focs/ch01.pdf

http://infolab.stanford.edu/~ullman/focs/ch02.pdf

Programming: Principles and Practice Using C++,** **: Bjarne Stroustrup

# Resources

https://tug.org/texshowcase/cheat.pdf

#### The canon

Name | Author | Note |
---|---|---|

Introduction to Algorithms | CormenLeisersonRivestStein | |

The Art of Computer Programming | Donald Knuth | |

The cracking the coding interview | Handbook. | |

Crash Cou |

#### Complementary

Name | Tags |
---|---|

LeetCode | |

HackerRank |

# Open source

**Google Summer of Code**

# 1. The role of Algorithms in computing

You need to know Discrete mathematics.

## Notes

- Functional programming vs Procedural programming

- Some exercises are Jupyter

## 1. Timeline

## 1.1 Algorithm

**Algorithm. **Sequence of computational steps that transform the input into the output.

```
input <-> a instance of a problem
...computional steps <-> a computer algorithm <-> transform input to output <-> a program solves a specific problem <-> a task solves an instance of a problem
output
```

### About software

$computer \text{ } algorithm = program =abstract\text{ } code$ and $program \sube software$

Abstracts are important, they define granularity about the algorithm and the elements that achieve it. For example, an algorithm with the English code is not equal to a hardware design. However, the specific precise steps of the elements are given.

The software can be hardware, and inversely.

Church–Turing thesis.

#### Real code vs pseudocode

Name | Tags |
---|---|

Real code | Issues of data abstractionProgramming languageSoftware engineeringerror handlingmodularity |

Pseudocode | English languageNo software engineeringProgramming languageessence of the algorithm |

Another difference between pseudocode and real code is that pseudocode is not typically concerned with issues of software engineering.

Issues of data abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more concisely.

Algorithm.

Software.

Software system.

Function.

Pseudocode.

Testing.

Program. Programming vs coding.

Code.

Solution.

Circuit.

Domain.

Routine.

Subroutine.

Computing.

Calculating.

Procedure.

Applications.

Apps.

Interface.

Script.

Hardware.

Platform.

Systems, computer systems, and business processes.

Systems, Applications, and Products in Data Processing (SAP).

Complex vs hard

Programming complexity

### Correct and incorrect

The algorithm is correct if it can solve the given problem. An incorrect algorithm may halt with a partial or nothing solution. That algorithm could be useful if we control their error rate. However, most time we focused on the correct algorithms.

### Notes

- Convex hull.

## 1.2 Algorithms as a technology

Algorithm efficiency is more significant than differences due to hardware. Why should learn about algorithms? applications use them either to solve larger problems than ever before or they rely heavily upon algorithms.

#### Example

Name | Efficiency | Time if 10^7 items |
---|---|---|

Insertion Sort | 2n^2 | 5.5 hours |

Merge sort | 50nlg(n) | 20 minutes |

Having a solid base of algorithmic knowledge and technique is one characteristic that separates truly skilled programmers from novices. (35)

### Worked examples

## 1. Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

- Page Rank Algorithm by Google. Search web about Internet.

## 2. Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in $8n^2$ steps, while merge sort runs in $64nlg(n)$ steps. For which values of n does insertion sort

**beat**merge sort?$When \text{ is }8n^2 \text{ faster than } 64nlg(n)?$ That implies $\forall n \mid8n^2<64nlg(n)$

Note: If $f$ is a multivalued function, $f(2)=n_1$, $f(2)=n_2$ and $n_2>n_1$. We have $n<f(2)$ implies $n<n_2$ and $n_1<n$.

## 3. What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?

$When \text{ is }100n^2 \text{ faster than } 2^n continually?$ That implies $\text{ from } n_0 \text{ to } \infty \text{, }100n^2<2^n \text{ i.e. } sup(n) \mid 100n^2<2^n$.

**Problem 1-1**Comparison of running times For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.https://math.stackexchange.com/questions/2078997/inverse-of-a-factorial

If o=1 ms

https://udel.edu/~caviness/Class/CISC320-02S/exercise-solns/ch01/R-1.7.pdf

# Framework Thinking about the design and analysis of algorithms (Getting started)

## Sum of sequence

**Input: ** A non-null sequence of $n$ real numbers $[a_1,a_2,a_3,...,a_n]$.

**Output**: A real value $r$, such that $r=\sum_i^n a_i$

```
SUM(A)
n = A.length c1(1)
r = A[n] c2(1)
for j = n-1 downto 1 c3(n)
do r = r + A[j] c4(n-1)
return r c5(1)
```

**Invariant loop. **At the start of each iteration of for loop of lines 3-4, $r$ is equal to elements from $n$ to last values $n-j$.

## Initialization.

Before the first loop iteration, $j=n-1$ and $r=a_n$, therefore $r$ equals the last value, $n-(n-1)=1$. Which checks with the invariant loop.

## Maintenance.

Before the loop iteration, $j=k$, thus $r=a_n+a_{n-1}+a_{n-2}+...+a_{n-k}$ (the summation of last elements). At line $4$ $j=k+1$ element is added to $r$, i.e. the next loop iteration $r=a_n+a_{n-1}+a_{n-2}+...+a_{n-k}+a_{n-(k+1)}$. Which checks with the invariant loop.

## Termination.

When loop terminates $j=n$, $n-j=n-n=0$. By invariant loop We have $r=a_n+a_{n-1}+a_{n-2}+...+a_{n-k}+a_{n-(k+1)}+...+a_1$.

Hence, the algorithm is correct.

We sum the product of the costs times columns $T(n)=c_1+c_2+c_3n+c_4(n-1)+c_5n=(c_4+c_5)n+(c_1+c_2+c_3-c_4)$.

## Sorting problem by insertion sort

**Input**: A sequence (or array) of $n$ numbers $[a_1,a_2,...,a_n]$. The numbers that we wish to sort are also known as the keys.

```
INSERTION_SORT(numberSequence)
for j = 2 to numberSequence.length
key = numberSequence[j]
i = j - 1
while i > 0 and numberSequence[i] > key
numberSequence[i+1] = numberSequence[i]
i = i - 1
numberSequence[i+1] = key
```

## Languages implementation

`def insertion_sort(numberSequence, compareFunction): for j in range(1,len(numberSequence)): key = numberSequence[j] i = j - 1 while i >= 0 and compareFunction(numberSequence[i], key): numberSequence[i+1] = numberSequence[i] i = i - 1 numberSequence[i+1] = key return numberSequence; insertion_sort([4,3,2,1], lambda a,b : a > b)`

`void insertionSort ( int numberSequence[ ] , int length) { for( int j = 1 ; i < length ; i++ ) { int key = numberSequence[ i ]; int i = j - 1; while( i >= 0 && numberSequence[i] > key) { numberSequence[i+1] = numberSequence[i]; i = i - 1; } numberSequence[ i+1 ] = key; } }`

**Output**: A reordering $[a_1^{'},a_2^{'},...,a_n^{'}]$ of the input sequence such that $a_1^{'}\le a_2^{'}\le ...\le a_n^{'}$.

## Preconditions and postconditions

This is a topic in software engineering. Here We assume correct preconditions.

Design by contract

http://www.cs.albany.edu/~sdc/CSI310/MainSavage/notes01.pdf

## Immutability and Mutability

## Loop invariant

## Worked examples

## Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array $A=[31,41,59,26,41,58]$

## Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

`insertion_sort([1,2,3,4], lambda a,b : a < b)`

## Consider the searching problem: Input: A sequence of n numbers A D ha1; a2;:::;ani and a value . Output: An index i such that D AŒi or the special value NIL if does not appear in A. Write pseudocode for linear search, which scans through the sequence, looking for . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

# Memoization

## References

https://docs.python.org/3/library/functools.html

# Fundamental Algorithms

Time complexity

Space complexity

# Typical algorithms

## Counting repeated characters in a string

https://colab.research.google.com/drive/1u3VIr2VS3hpQjeLO66XbwVJeoqvCoEsZ?usp=sharing

```
# Python 3+
import collections
collections.Counter(input_string)
```

```
# Python 2 or custom results.
{key: string.count(key) for key in set(string)}
```

# Seminumerical Algorithms

## Random number generation

## Log

- Count the number of digits

By mod. Its time complexity is $O(n)$

```
def algorithmMod(n):
count=0
while(n>0):
count=count+1
n=n//10is
return count
```

By log. Its time complexity is $O(1)$

```
def algorithmLog(number):
return math.floor(math.log10(math.abs(number)))+1
```

https://replit.com/join/zpwivezz-carlossanchez14

## Modulo operation

Remainder after division.

### Worked examples

- Extracting individual digits.

## Truncate

## Floor and ceil

# Rounding

Round half to even, a variant of the round-to-nearest method.

This method is called the round-to-even method. Other names include the round-half-to-even method, the round-ties-to-even method, and "bankers' rounding." This variant of the round-to-nearest method is also called convergent rounding, statistician's rounding, Dutch rounding, Gaussian rounding, odd–even rounding, or bankers' rounding.

Banker's rounding: the value is rounded to the nearest even number. Also known as "Gaussian rounding", and, in German, "mathematische Rundung".

Standard rounding: the value is rounded to the nearest number (be it odd or even). In German it is known as "kaufmännische Rundung".

754-2019 - IEEE Standard for Floating-Point Arithmetic since 1985.

https://en.wikipedia.org/wiki/Rounding

If the fractional part of x is 0.5, then y is the even integer nearest to x.

```
function roundIt(n, d = 0) {
var m = Math.pow(10, d);
var n = +(d ? n * m : n).toFixed(8);
var i = Math.floor(n),
diff = n - i; // getting the difference
var e = 1e-8; // Rounding errors in var(diff)
// Checking if the difference is less than or
// greater than, based on that adding the 1 to it.
var r = (diff > 0.5 - e && diff < 0.5 + e) ?
((i % 2 == 0) ? i : i + 1) : Math.round(n);
return d ? r / m : r; // if d != 0 then returning r/m else r
}
```

https://www.geeksforgeeks.org/gaussian-bankers-rounding-in-javascript/

## Experimental

```
import time
import numpy as np
def timer(f):
x=np.random.rand(1,100000)[0]
times = []
for i in range(10):
tic = time.perf_counter()
f(x)
toc = time.perf_counter()
times.append(toc - tic)
print(f"Build finished in {np.mean(times):0.4f} +- {np.std(times):0.4f} seconds")
```

# Data structures

# Chapter 16 Greedy Algorithms

## Worked examples

16-1 Coin changing Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin’s value is an integer.

## a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies —25, 10, 5 y 1 respectively. Prove that your algorithm yields an optimal solution.

**Input.****$n\in\mathbb{N}$****Output.**The fewest sequence of quarters, dimes, nickels, and pennies, such that their sum equals to $n$.**Corollary 1.****$quarters, dimes, nickels, pennies \in \mathbb{N}$**

## b. Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are $c^0,c^1,...,c^k$ for some integers c>1 and $k\ge1$. Show that the greedy algorithm always yields an optimal solution.

## c. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n.

## d. Give an $O(nk)$-time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny

# Chapter 22 Elementary Graph Algorithms

## 22.2 Breadth-first search

- Class: Search algorithm

- $T(n)=O(V+E)$

- $S(n)=O(V)$

# Problems

From LeetCode, HackerRank, ...

## Given a signed 32-bit integer

`x`

, return`x`

*with its digits reversed*. If reversing`x`

causes the value to go outside the signed 32-bit integer range`[-231, 231 - 1]`

, then return`0`

.https://math.stackexchange.com/questions/480068/how-to-reverse-digits-of-an-integer-mathematically

**Assume the environment does not allow you to store 64-bit integers (signed or unsigned).**

- Multiply

- Divide

- Length

## 2.1 Timeline

Objects.

Functions.

Array.

Graph.

Tree.

...

# Regular expression

REGEX

# Analysis of algorithms

## NP-Completeness

*

# Parameters or Arguments?

From a function's perspective:

A parameter is the variable listed inside the parentheses in the function definition.

An argument is a value that is sent to the function when it is called.

# Paradigms

## Functional programming

### Lambda calculus

El problema del desplazamiento del paradigma.

https://www.youtube.com/watch?v=cWAHpvkh8Vs

https://alexott.net/en/fp/books/

https://purelyfunctional.tv/functional-programming-languages/

https://betterprogramming.pub/modern-languages-suck-ad21cbc8a57c

https://www.youtube.com/watch?v=-J_xL4IGhJA

https://www.expressionsofchange.org/dont-say-homoiconic/

Foundations.

- Lambda Calculus

- What is an Efficient Implementation of the $\lambda$- calculus? https://www.cs.cmu.edu/~rwh/papers/nsf-pfl/excerpt.pdf

- Category theory

- Lisp
- Racket.

- Schema.

- Haskell.

- Scala.

- Elm.

- Erlang.
- Ruby.

- Elixir.

- Fenix.

- Clojure.

- Curry.

- Servidor en linea.

## Logic programming

# Assessments

## 20 Questions Game on Google Assistant, Telegram and Whatsapp