👩🏼‍💻

Foundations of Computer Science

TagsComputer science
Created
Updated

Notation

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

log2(n)=lg(n)log_2(n)=lg(n)

ff is faster than gg, if ff is smaller than gg i.e. f<gf<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

🗣️
Computer science is no more about computers than astronomy is about telescopes. — Edsger Dijkstra

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

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

0.1 Milestones in computer architecture

The history of hardware can be divided into:

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?

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.

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

Traduction

NameComputingComputer scienceComputer engineeringInformation managementPROGRAMMINGCyberneticsSoftware engineeringElectronic engineeringTelocommunicationsTelematicsInformation technologyData processing
SpanishComputacionCiencias computacionalesIngenieria de la computacionInformatica. Relacionado con humanidades. Admnistracion de la informacion.Programacion.CiberneticaIngenieria del software
German
Chinese
French
English

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

⚠️
Use ACM citations about other styles (IEEE, APA, ...)

IEEE

ACM

MIT

Stanford

Cambridge

Berkley

O'Reilly

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?

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

https://github.com/Developer-Y/cs-video-courses

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

Peter Norvig

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

Andrew Binstock/

George Hotz

Others

Robert S. Langer

Open-source

Bram Moolenaar

Miguel de Icaza

Business people

Bill Gates

Steve Jobs

Carmen Ortiz

Kim Dotcom

Sergey Brin

Larry Page

Ross Ulbricht

Literature and computer science culture

Asimov 1984 Bicentennial Man

Jargon File or Hacker Dictionary

How to become a hacker.

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

https://xkcd.com/2610/

https://www.stephenwolfram.com/questions/2016/02/23/what-is-the-one-thing-any-student-must-try-in-college/

Micro stories

Tanenbaum–Torvalds debate

AN OPEN LETTER TO HOBBYISTS, by Bill Gates

IBM vs Harvard by IBM ASCC

Homebrew club

The humble programmer

Taligent

First Computer Science department was Cambridge

Warren Buffet and Bill Gates

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(0)_b=0 and (1)b=1(1)_b=1

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

(anan1...a1a0)bk=0nakbk=(m)10=m(a_na_{n-1}...a_1a_0)_b\equiv \sum_{k=0}^na_kb^k=(m)_{10}=m

Convert from decimal to bb-base.

m=bqk+ak,until q=0 and q0=nm=bq_k+a_k,\text{until } q=0 \text{ and } q_0=n
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.

(1010)2(22)4=(10 10)2(12)8=(001 010)2(A)16=(1010)2(1010)_2\\ (22)_4=(10\text{ }10)_2\\ (12)_8=(001\text{ }010)_2\\ (A)_{16}=(1010)_2

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

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

⚠️
When you're saving numbers, so computer saves them as binary.

Method of complements

Cb1(m)=bnm>0,bn>mC_b1(m)=b^n-m>0,b^n>m

Nine's complement

C9(m)=(10nm1)C_9(m)=(10^n-m – 1)

Ten's complement

C10(n)=10nC_{10}(n)=10^n

One's complement

One's complement is an operation to inverting bits.

C1(m)=2nm1C_1(m)=2^n-m-1

Worked examples.

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

56=00111000199=1100011156=00111000\\ 199=11000111

Two's complement

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

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

C2(m)=2nmC_2(m)=2^n-m

Worked examples.

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

056=00111000200=11001000056=00111000\\ 200=11001000

Trick.

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

Example. 1110011011100110 two's complement format to integer.

 The sign is negative. 11100110 Apply two’s complement 00011010Integer changed to decimal 26Sign is added 26\text{ The sign is negative. } 11100110\\ \text{ Apply two's complement } 00011010\\ \text{Integer changed to decimal } 26\\ \text{Sign is added } -26

How to encode negative numbers in binary number systems?

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?

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={charactercharactergrammar or character human-computer interface}.code=\{character | character \in grammar \text{ or } character \in \text{ human-computer interface} \}.

For example, English grammar is {A,B,C,...,Z}{a,b,c,...,z}{.,;,,+,!,...,}{0,1,2,3,...,9}\{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}\{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}code=\{A\}, his cardinality code=1|code|=1. Then computer understands computer code=bit patterns ={0}\text{computer code}=\text{bit patterns =}\{0\} and bit pattern length=1\text{bit pattern length}=1

code={A,B},code=2,bit pattern={0,1},bit pattern length=1code=\{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},bit pattern length=2code=\{A,B,C,D\},|code|=4,computer=\{00,01,10,11\},\text{bit pattern length}=2.

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

Therefore, bitPatternLength=lg(code)\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.

00010001000101100010011100010001\\ 00010110\\ 00100111

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

Subtraction of naturals (No complements).

00010001000010100000011100010001\\ 00001010\\ 00000111

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)

9146=91+(46)=4591-46=91+(-46)=45

91=0101101146=00101110+91=0101101146=11010010+45=0010110191=01011011\\ 46=00101110\\\\ +91=01011011\\ -46=11010010\\ +45=00101101

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 nn is position left to right.

P(n)=2n+1:odd Always it needs +1Q(n)=2n:evenP(n)=2n+1:odd \text{ Always it needs +1}\\ Q(n)=2n:even
Odd number0...1..0...1&1000...0001000...00011T\text{Odd number} \equiv 0...1..0...1\&\\ 1\equiv000...0001\\ 000...0001\equiv1\equiv T
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

https://www2.southeastern.edu/Academics/Faculty/kyang/2018/Spring/CMPS375/ClassNotes/CMPS375ClassNotesChap03.pdf

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

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

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

Complementary

NameTags
LeetCode
HackerRank

Open source

Google Summer of Code

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. 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 algorithm=program=abstract codecomputer \text{ } algorithm = program =abstract\text{ } code and programsoftwareprogram \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

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.

Notes

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

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

Sum of sequence

Input: A non-null sequence of nn real numbers [a1,a2,a3,...,an][a_1,a_2,a_3,...,a_n].

Output: A real value rr, such that r=inair=\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, rr is equal to elements from nn to last values njn-j.

Hence, the algorithm is correct.

We sum the product of the costs times columns T(n)=c1+c2+c3n+c4(n1)+c5n=(c4+c5)n+(c1+c2+c3c4)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 nn numbers [a1,a2,...,an][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

Output: A reordering [a1,a2,...,an][a_1^{'},a_2^{'},...,a_n^{'}] of the input sequence such that a1a2...ana_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

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

  1. Count the number of digits

By mod. Its time complexity is O(n)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)O(1)

length(number)=log10(number)+1length(number)=\lfloor log_{10} (|number|)\rfloor+1
def algorithmLog(number):
  return math.floor(math.log10(math.abs(number)))+1

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

Modulo operation

Remainder after division.

a=nq+r,qZr=mod(dividend,divisor)=remainder=anana=nq+r,q\in\mathbb{Z}\\ r=mod(dividend,divisor)=remainder=a-n\lfloor \dfrac{a}{n} \rfloor

Worked examples

  1. Extracting individual digits.
    get(position,number)=trunc(number10position) mod 10get(position,number)=trunc(\dfrac{number}{10^{position}})\text{ }mod\text{ }10

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

Banker's rounding
Banker's rounding VBspeed © 2000-10, updated: 30-May-2002 Banker's 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 "kaufmnnische Rundung".
http://xbeat.net/vbspeed/i_BankersRounding.htm

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.

⚠️
0 is even number.
round(1.7)=2,round(2.7)=3round(1.5)=2,round(2.5)=2round(1.3)=1,round(2.3)=2round(1.7)=2,round(2.7)=3round(1.5)=2,round(2.5)=2round(1.3)=1,round(2.3)=2round( 1.7 )=2,round( 2.7 )=3\\ round( 1.5 )=2,round( 2.5 )=2\\ round( 1.3 )=1, round( 2.3 )= 2\\ round( -1.7 )=-2,round( -2.7 )=-3\\ round( -1.5 )=-2,round( -2.5 )=-2\\ round( -1.3 )=-1, round( -2.3 )=-2
round(x)={xif xx<0.5 or (isEven(x) and xx=0.5)xif xx>0.5 or (isOdd(x) and xx=0.5)round(x) = \begin{cases} \lfloor x \rfloor &\text{if } |\lfloor x \rfloor -x|<0.5 \text{ or (}isEven(x)\text{ and }|\lfloor x \rfloor -x|=0.5 )\\ \lceil x \rceil &\text{if } |\lceil x \rceil -x|>0.5 \text{ or (}isOdd(x)\text{ and }|\lceil x \rceil -x|=0.5 ) \end{cases}
JSFiddle
Test your JavaScript, CSS, HTML or CoffeeScript online with JSFiddle code editor.
https://jsfiddle.net/2hs9nqbk/2/
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.

Chapter 22 Elementary Graph Algorithms

22.2 Breadth-first search

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

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.

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

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.

  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. Haskell.
  1. Scala.
  1. Elm.
  1. Erlang.
    1. Ruby.
    1. Elixir.
    1. Fenix.

    https://www.youtube.com/watch?v=idUgQ87-7kA

    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.

Logic programming

Assessments

20 Questions Game on Google Assistant, Telegram and Whatsapp