# Foundations of Computing

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.

Computer science has two approaches Mathematics and Engineering. Mathematics changes of course, but engineering changes a lot more.

**Foundations of Computer Science by Behrouz A. Forouzan**

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

CHRISTOPHER STRACHEY of Oxford University, entitled "Is Computing Science?" (1970).

## 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**

Top Secret Rosies

https://sites.google.com/view/amexcompmujeres/recursos?authuser=0

AMEXCOMP

# Why study?

https://www.guillermodeladehesa.com/files/capital_humano_y_crecimiento_economico.pdf

https://guillermodeladehesa.com/files/0006.1450263067.KAIQ5962GFQD5022PIAE8796KYES7779.pdf

## Learning Path (Self leaning)

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

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

**Curricula Recommendations **CS2013: Curriculum Guidelines for Undergraduate Programs in Computer Science (English) ACM

Computer Science Educators Stack Exchange. (2022, September 25). Retrieved from https://cseducators.stackexchange.com

https://www.gatevidyalay.com/gate-books/

https://zoo.cs.yale.edu/classes/

**Exams**

GATE CS

- C, Data Structure and Algorithms

- Theory of Automata and Computation

- Compiler Design

- Digital Logic

- Database Management System

- Computer Organization and Architecture

- Operating System

- Computer Networks

### How to choose the material?

- Search books from someone have built great stuff and, then apply BFS, A*, … from his recommendation. Avoid bullshit people.

## 0.7 Character

## Computer science culture

**Kung Fury**

- Life A Users Manual by Georges Perec (perhaps the greatest 20th century novel) (see Willy Wauquaire's superb webpages about it)

- Gaudy Night by Dorothy L Sayers (captures Oxford high-table small-talk wonderfully)

- An Instance of the Fingerpost by Iain Pears (also Oxford but in the 1660s)

- Death of a Salesperson by Robert Barnard (who is at his best in short stories like these)

- The Haj by Leon Uris (great to read on a trip to Israel)

- Marjorie Morningstar by Herman Wouk (in-depth characters plus a whole philosophy)

- On Food and Cooking by Harold McGee (applied biochemistry in the kitchen)

- Food by Waverley Root (his magnum opus, a wonderful history of everything delicious)

- The Golden Gate by Vikram Seth (the Great California Novel, entirely in 14-line sonnets)

- The Age of Faith by Will Durant (volume 4 of his series, covers the years 325--1300)

- Efronia by Stina Katchadourian (diaries and letters of a remarkable Armenian woman)

- The Man Who Knew Infinity by Robert Kanigel (biographies of Ramanujan and Hardy)

- Hackers by Steven Levy (incredibly well written tale of our times)

- The Abominable Man by Maj Sjöwall and Per Wahlöö (one of their brilliantly Swedish detective novels)

- Blasphemy by Douglas Preston (the best novel to deal with "science versus religion" that I've ever encountered)

- Blacklist by Sara Paretsky (a brilliant characterization of the tragic state of politics and class relations in America that also happens to be an action-packed murder mystery)

- The Travels of Ibn Battutah edited by Tim Mackintosh-Smith (fascinating and eye-opening journal by a 14th-century Muslim scholar)

- Murder in the Museum of Man by Alfred Alcorn (delicious caricature of academic follies)

- America (The Book): Teacher's Edition “A Citizen's Guide to Democracy Inaction” by Jon Stewart et al (has graffiti even better than the marginal notes in Concrete Mathematics)

- Feynman by Jim Ottaviani and Leland Myrick (vivid, witty, hilarious, poignant: I laughed, I cried, I learned; demonstrates the unreasonable effectiveness of a graphic novel)

- Mountains Beyond Mountains by Tracy Kidder (about how Paul Farmer's local and global life combined theory and practice)

- A Dual Autobiography by Will and Ariel Durant (superbly written, a great story about how a man and woman can work creatively and sustainably together despite the mysteries of the human sex drive)

- The Hornet's Nest by Jimmy Carter (a revolutionary novel about the Revolutionary War at all levels)

- Lifeline Rule by Doug Nufer (the rule: parity to vowel; an awesome conovowel opus)

- Inventing the Future by Albert Cory (a novel way to explain how advances in software require lots of time and lots of complementary skills)

- Stravinsky in Pictures and Documents by Vera Stravinsky and Robert Craft (proving again the great value of access to original sources and ephemera)

Fiction: Cloud Atlas: A Novel - Life of Pi - A Prayer for Owen Meany: A Novel - All the Light We Cannot See - The Book Thief - The Fault in Our Stars - Tenth of December: Stories - If I Don't Six - A Game of Thrones - To Kill a Mockingbird - The Kite Runner - Ender's Game - Foundation - Slaughterhouse-Five - The Shadow of the Wind - Flowers for Algernon - Holes - Atonement - The Name of the Wind - Beloved - For Whom the Bell Tolls - Different Seasons - Neuromancer - Snow Crash - Cryptonomicon - Shantaram - A Room with a View - Jude the Obscure - Illusions: The Adventures of a Reluctant Messiah - A Canticle for Leibowitz - A Wizard of Earthsea - Black Swan Green - The Stars My Destination - Ancillary Justice - My Brilliant Friend - Crossing to Safety - Possession - The Selected Works of T.S. Spivet - Essential Ellison - The Demolished Man - The Nightingale - The Overstory - The Windup Girl - The Water Knife Non-fiction: Seabiscuit: An American Legend - Unbroken - Surely You're Joking, Mr. Feynman! - On Intelligence - The Language Instinct - Flow - Guns, Germs, and Steel - The Selfish Gene - A Heartbreaking Work of Staggering Genius - Lies My Teacher Told Me - Freakonomics - How the Irish Saved Civilization - Cod - The Devil in the White City - The Swerve: How the World Became Modern - The Drunkard's Walk - The Visual Display of Quantitative Information - Eats, Shoots & Leaves - The Elements of Style - The Design of Everyday Things - Mountains Beyond Mountains - The Soul of A New Machine - Alan Turing: The Enigma - Consider the Lobster - The Vintage Guide to Classical Music

## Micro stories

## University

Göttingen

### Operation research relationship

## FAQ

# Conventions

## Money and business: be Alfa or Beta

`There’s more to computer science jobs than software engineering.`

https://blog.edx.org/computer-science-careers

https://www.bls.gov/ooh/computer-and-information-technology/home.htm

https://www.youtube.com/watch?v=ILYtS8DtBI8&ab_channel=ÓscarVara

**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

# ASCII

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

## 0.8 Turing model

## 0.9 Von Neumann Model? Mauchly 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

COMS W3827 Fundamentals of Computer Systems

### 0.1311 Binary and boolean function

Binary vs boolean and bits

Ecosystem

### 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

IEEE milestones.

ASCII.

UNICODE. Emojis.

`printf "\r12345\n\r6\n"; printf "\r5\n"`

`printf "\r12345"; printf "\r5\n"`

https://stackoverflow.com/questions/3091524/what-are-carriage-return-linefeed-and-form-feed

Hex Code.

How works internally?

https://www.w3schools.com/tags/ref_urlencode.ASP

https://onlineunicodetools.com/convert-unicode-to-hex

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

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.

https://pjb.com.au/comp/diacritics.html

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.165 Codification: choosing the right abstraction

Bitwise operations

## 0.17 Languages

**GNU C Language Intro and Reference Manual. **https://forums.linuxmint.com/viewtopic.php?t=381284 https://www.docdroid.net/73uNJco/c-pdf

## 0.18 Jobs and Paths

## 0.19 Standards

**Idioms**

https://kotlinlang.org/docs/idioms.html

## 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

https://www.youtube.com/watch?v=f2JL1rdQYog&ab_channel=AlexVogager

## 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

Structured Programming by Edsger W. Dijkstra, Ole-Johan Dahl, and Tony Hoare https://seriouscomputerist.atariverse.com/media/pdf/book/Structured Programming.pdf

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

https://www.gwern.net/docs/math/1973-knuth.pdf

https://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)FunctionPointers.html

https://computingthehumanexperience.com

Computational Artifacts, towards a philosophy of computer science. Towards a Philosophy of Computer Science. Raymond Turner

# Resources

http://neerc.ifmo.ru/wiki/index.php

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**

# 0. Computers, People, and Programming

## Myths

### You’re a genius because you’re a programmer

https://www.youtube.com/watch?v=KEkrWRHCDQU&ab_channel=LaserUnicorns

## Military industry

https://governmentciomedia.com/next-generation-soldiers-will-be-software-engineers

## Fun?

https://www.youtube.com/user/BostonDynamics

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

# Von Neumann Simulator

# Introduction to Programming

??cs101??

**Programming Pearls. **Jon Bentley.?

**Structure and Interpretation of Computer Programs.** Harold Abelson, Gerald Jay Sussman y Julie Sussman.

**Algorithms + Data Structures = Programs**

C language. K&R.

C++ Stroustrup.

Which book should I choose to get into the Lisp World? (2022, September 25). Retrieved from https://cseducators.stackexchange.com/questions/7478/which-book-should-i-choose-to-get-into-the-lisp-world/7481#7481

norvig. (2022, September 27). pytudes. Retrieved from https://github.com/norvig/pytudes

# Notebooks

google. (2022, September 28). latexify_py. Retrieved from https://github.com/google/latexify_py

# Abstractions

https://www.youtube.com/watch?v=ixIlknu7svM&ab_channel=AssociationforComputingMachinery(ACM)

Computation vs Computing

Tele communications layers

# Recursivity

## Self-reference

## Examples

infinite stories l

# Hacking

**Keyboard remapping**

## O**verflow**

# 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 the granularity of the algorithm and the elements that achieve it. For example, an algorithm with 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//10
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

Mandelbrot set from scratch, Markov text-generation,

and John Conway’s Game of Life ar

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