👩🏼‍💻

# Foundations of Computing

Tags Computer science @December 28, 2020 1:19 PM @December 7, 2022 8:10 PM

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

# 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

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

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

https://textbooks.cs.ksu.edu/

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 electronic computers (1930–1950)
• and the period that includes the five modern computer generations.
• Cloud
• Quantum computer (1980-)
• Desktop Quantum Computer (2021-)

## 0.2 Etymology

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

Denning, P. J. (2005). Is computer science science? Communications of the ACM, 48(4), 27. doi:10.1145/1053291.1053309

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

Weiss, E. A., & Corley, H. P. T. (1958). Letters to the editor. Communications of the ACM, 1(4), 5. doi:10.1145/368796.368802

## 0.3 Words

NameComputingComputer scienceComputer engineeringInformation managementPROGRAMMINGCyberneticsSoftware engineeringElectronic engineeringTelocommunicationsTelematicsInformation technologyData processing
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

https://dl.acm.org/ccs

## 0.6 Institutes and corporations

IEEE

ACM

MIT

Stanford

Cambridge

Berkley

O'Reilly

ANSI

Dr. Dobb's Journal

Oxford

Bell Labs

RAND corporation

FANG

Y-Combinator

Xerox PARC

IBM

Top Secret Rosies

AMEXCOMP

https://www.quora.com/How-does-the-CS-student-culture-differ-between-the-top-4-MIT-Stanford-Berkeley-and-CMU

# Why study?

## Learning Path (Self leaning)

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

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

http://www.cyc2018.xyz/

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

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

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

Exams

GATE CS

1. C, Data Structure and Algorithms
1. Theory of Automata and Computation
1. Compiler Design
1. Digital Logic
1. Database Management System
1. Computer Organization and Architecture
1. Operating System
1. Computer Networks

### How to choose the material?

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

## Computer science culture

Kung Fury

By Knuth:

• 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)

Göttingen

## FAQ

Are CS undergraduate students spending most of their time writing Compilers and Operating Systems wasting their time?

# 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

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

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

NATO and software

University story

# ASCII

## 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.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.cl.cam.ac.uk/teaching/1415/CompFund/NumberSystemsAnnotated.pdf

https://ocw.mit.edu/courses/aeronautics-and-astronautics/16-01-unified-engineering-i-ii-iii-iv-fall-2005-spring-2006/comps-programming/mud5.pdf

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

https://ocw.mit.edu/courses/aeronautics-and-astronautics/16-01-unified-engineering-i-ii-iii-iv-fall-2005-spring-2006/comps-programming/number_systems.pdf

https://ocw.mit.edu/resources/res-18-008-calculus-revisited-complex-variables-differential-equations-and-linear-algebra-fall-2011/study-materials/MITRES_18_008_supp_notes01.pdf

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.14 Data Storage

### 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 memoryUnsignedSign-and-magnitudeTwo's complementOne's complement
000000+00
000111+11
001022+22
001133+33
010044+44
010155+55
011066+66
011177+77
10008-0-8-7
10019-1-7-6
101010-2-6-5
101111-3-5-4
110012-4-4-3
110113-5-3-2
111014-6-2-1
111115-7-1-0
NotesThe 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?

• 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://stackoverflow.com/questions/12747722/what-is-the-difference-between-a-line-feed-and-a-carriage-return

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

ASA standard X3.4-1963

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

## 0.15 Operations on Data

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

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

## 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.162 Domain of discourse

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

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

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

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

NameAuthorNote
Introduction to AlgorithmsCormenLeisersonRivestStein
The Art of Computer ProgrammingDonald Knuth
The cracking the coding interviewHandbook.
Crash Cou

NameTags
LeetCode
HackerRank

# 0. Computers, People, and Programming

## Military industry

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

# 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

# Abstractions

Computation vs Computing

Tele communications layers

# Recursivity

## Examples

infinite stories l

# 1. The role of Algorithms in Computing

You need to know Discrete mathematics.

## Notes

1. Functional programming vs Procedural programming
1. Some exercises are Jupyter

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

$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

NameTags
Real codeIssues of data abstractionProgramming languageSoftware engineeringerror handlingmodularity
PseudocodeEnglish 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.

• 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

NameEfficiencyTime if 10^7 items
Insertion Sort2n^25.5 hours
Merge sort50nlg(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.
• 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﻿ implies $n﻿ and $n_1﻿.

https://www.wolframalpha.com/input/?i=8x^2<64xlog_2(x)

• 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$﻿.

https://www.wolframalpha.com/input/?i=100x^2%3D2^x

• 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

Visualizer

• 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

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

Time complexity

Space complexity

# Typical algorithms

## Counting repeated characters in a string

# Python 3+
import collections
collections.Counter(input_string)
# Python 2 or custom results.
{key: string.count(key) for key in set(string)}

# Seminumerical Algorithms

## Log

1. 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

1. Extracting individual digits.

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

# 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}$﻿ cents.

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

• Class: Search algorithm
• $T(n)=O(V+E)$﻿
• $S(n)=O(V)$﻿

# Problems

From LeetCode, HackerRank, ...

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

1. Multiply
1. Divide
1. Length

Objects.

Functions.

Array.

Graph.

Tree.

...

REGEX

*

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

https://www.w3schools.com/python/gloss_python_function_arguments.asp#:~:text=Parameters or Arguments%3F,are passed into a function.&text=A parameter is the variable,function when it is called

## Functional programming

### Lambda calculus

El problema del desplazamiento del paradigma.

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

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

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

Foundations.

1. Lambda Calculus
1. https://plato.stanford.edu/entries/lambda-calculus/
1. What is an Efficient Implementation of the $\lambda$﻿- calculus? https://www.cs.cmu.edu/~rwh/papers/nsf-pfl/excerpt.pdf
1. Category theory
1. https://plato.stanford.edu/entries/category-theory/
1. Lisp
1. Racket.
1. Schema.
1. Scala.
1. Elm.
1. Erlang.
1. Ruby.
1. Elixir.
1. Fenix.

1. https://www.wired.com/2015/09/whatsapp-serves-900-million-users-50-engineers/.

https://news.ycombinator.com/item?id=21111662

1. Clojure.
1. Curry.
1. Servidor en linea.

# Assessments

Mandelbrot set from scratch, Markov text-generation,

and John Conway’s Game of Life ar