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?

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

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 mechanical machines (before 1930)
  • Pascaline simulator

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

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

• 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

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

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

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

http://www.cyc2018.xyz/

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

1. C, Data Structure and Algorithms

2. Theory of Automata and Computation

3. Compiler Design

4. Digital Logic

5. Database Management System

6. Computer Organization and Architecture

7. Operating System

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

0.7 Character

Computer science culture

Kung Fury

By Knuth:

• 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

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

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

How to encode real numbers in binary number systems?

• Fixed-point

  https://planetcalc.com/862/

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

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

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

• Software and services

• Technology hardware and equipment

• Semiconductors and semiconductor equipment

• Information technology sector ETFs and mutual funds

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

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

Overflow

1. The role of Algorithms in Computing

You need to know Discrete mathematics.

Notes

1. Functional programming vs Procedural programming

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

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.

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

  $$8n^2<64nlg(n)\\ 8n^2<64n\dfrac{ln(n)}{ln(2)}\\ nln(2)<8ln(n)\\ \dfrac{ln(2)}{8}<\dfrac{ln(n)}{n}\\ \dfrac{ln(2)}{8}<\dfrac{ln(n)}{e^{ln(n)}}\\ \dfrac{log(2)}{8}<ln(n)e^{-ln(n)}\\ -\dfrac{log(2)}{8}>-ln(n)e^{-ln(n)}\\ -ln(n)>W_(\dfrac{-log(2)}{8})\\ n<e^{-W(\dfrac{-log(2)}{8})}\\ e^{-W_{-1}(\dfrac{-log(2)}{8})}<n<e^{-W_{0}(\dfrac{-log(2)}{8})}\\ n\in[2,43]$$

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

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

  $$100n^2=2^n\\ \dfrac{100n^2}{2^n}=1\\ \dfrac{n^2}{e^{ln(2^n)}}=\dfrac{1}{100}\\ \dfrac{n^2}{e^{nln(2)}}=\dfrac{1}{100}\\ n^2e^{-nln(2)}=\dfrac{1}{100}\\ ne^{-nln(2)/2}=\dfrac{1}{10}\\ \dfrac{-nln(2)}{2}e^{\dfrac{-nln(2)}{2}}=\dfrac{-ln(2)}{20}\\ W(\dfrac{-ln(2)}{20})=\dfrac{-nln(2)}{2}\\ n=\dfrac{-2W(\dfrac{-ln(2)}{20})}{ln(2)}=\{0,15\}\\ sup(n)=15\\ \text{ from } 15 \text{ to } \infty \text{, }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.

  $$\dfrac{f(n)}{operations}\le1 \text{ s}=10^6\text{ μs}\\ f(n)\le(10^6*operations) \text{ instructions}\\ \text{Specially, } n!\le(10^6*operations)\text{ instructions} \text{ and }n>>0\\ ---\\ log_2(n)=(10^6*o),n=2^{10^6*o} \\ \sqrt{n}=(10^6*o),n=(10^6*o)^2\\ n=(10^6*o)\\ nlg(n)=(10^6*o),n = \dfrac{(10^6*o)log(2)}{W((10^6*o)log(2))}\\ n^2=(10^6*o),n=\sqrt{10^6*o}\\ n^3=(10^6*o),n=(10^6*o)^{1/3}\\ \\ 2^n=(10^6*o),n=log_2(10^6*o)\\ n!=(10^6*o),n=ee^{W(\dfrac{log((10^6*o)!/\sqrt{2\pi})}{e})}-\dfrac{1}{2}\\$$

  

  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

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

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.

   $$get(position,number)=trunc(\dfrac{number}{10^{position}})\text{ }mod\text{ }10$$

   • https://blog.mattclemente.com/2019/07/12/modulus-operator-modulo-operation.html
   • https://stackoverflow.com/questions/339150/extracting-individual-digits-from-a-float

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.

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.

• 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}$

  Google Colaboratory

  https://colab.research.google.com/drive/1QdQAHotL6waCUzuMMEWjbxFCD-WcdT2V#scrollTo=EOhWJY3Jrds1&line=7&uniqifier=1

  

• 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

• https://www.cs.usfca.edu/~galles/visualization/BFS.html

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

1. Multiply

2. Divide

3. 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/

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

3. Category theory
   1. https://plato.stanford.edu/entries/category-theory/

4. Lisp
   1. Racket.
   2. Schema.

5. Haskell.

6. Scala.

7. Elm.

8. Erlang.
   1. Ruby.
   2. Elixir.
   3. 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

9. Clojure.

10. Curry.

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