CS1005 Notes PDF

Preview

Summary

Decimal to Binary PracticeBinary to Decimal Practice CS - Decimal (Base 10) Binary (Base 2) - Binary (Base 2) Decimal (Base 10) Marissa Ann Mayer 44 years old U information technology executive and co-founder of Lumi Labs Former president and CEO of Yahoo!Frances Elizabeth Allen 87 years old America...

Description

CS1005! Decimal to Binary Practice! Decimal (Base 10)

Binary (Base 2)

1

1

1

1

21

10101

17

10001

13

1101

32

100000

31

11111

15

1111

1

1

Binary to Decimal Practice! Binary (Base 2)

Decimal (Base 10)

1

1

5

101

5

101

5

101

18

10010

42

101010

16

10000

17

10001

17

10001

Page 1 of 85

Marissa Ann Mayer! 44 years old! U.S information technology executive and co-founder of Lumi Labs! Former president and CEO of Yahoo!!

Frances Elizabeth Allen"! 87 years old! American computer scientist and pioneer in the field of optimizing compilers.! First female IBM Fellow Became the first woman to win the Turing Award Achievements include seminal work in compilers, program optimization and parallelization.!

Noam Chomsky! 90 years old! The “father of modern linguistics”! Major figure in analytic philosophy and one of the founder of the field of cognitive science! Language Is Innate, explains that children are genetically predisposed to learn language. An input is still needed to be received from a social environment. After input, we have mental capability to generate new meaningful sentences.!

Barbara Liskov! 79 years old! She was one of the first women to be granted a doctorate in computer science in the US and is a Turing award holder.! Developed the Liskov substitution principle.!

Page 2 of 85

In the early 1900s, a group of women processed astronomical data. Not allowed to operate telescopes, these women instead acted as human computers, operating under Edward Charles Pickering for the Harvard Observatory.! Annie Jump Cannon and Henrietta Swan Leavitt was part of this group and they change the face of science.! Cannon became the first female assistant to study variable stars at night, she developed the Harvard Classification Scheme, which would become the new standard of star classification. ! Leavitt found hundreds of new variable stars and discovered that some stars have the same intrinsic brightness (no matter their distance from Earth). Leavitt also developed, and continued to refine, the Harvard Standard for photographic measurements.!

George Boole! 49 years old (1864)! He worked in the fields of differential equations and algebraic logic! Author of “The Laws of Thought” which contains Boolean algebra Boolean Algebra is the branch of algebra in which the values of the variables are the truth values, true and false, are denoted as 1 and 0 respectively.!

Bertrand Russell! 97 years old! He is considered one of the founders of analytic philosophy along with this predecessors Gottlob Frege and protégé Ludwig Wittgenstein.! He wrote Principia Mathematica, an attempt to create a logical basis for mathematics.! He has a considerable influence on mathematics, logic, set theory, linguistics, artificial intelligence, cognitive science, and computer science.!

Page 3 of 85

Charles Babbage! 79 years old (1871)! Was an English polymath! Originated the concept of a digital programmable computer and invented the first mechanical computer than led to the more complex electronic designs! Considered to be the “Father of Computer”! Part of his incomplete mechanisms are on display in the science museum in London.!

Ruth Teitelbaum! 62 years old (1986)! Was one of the fist computer programmers in the world! Was one of the group of 80 women who worked manually to calculate ballistic trajectories.! These women were called “computers”!

Thomas Harold Flowers! 92 years old (1998)! Was an English engineer with the British Post Office during World War 2! Flowers designed and built Collosus, the world’s first programmable electronic computer to help solve encrypted German messages.! Flowers' first contact with wartime codebreaking came in February 1941 when his director, W. Gordon Radley was asked for help by Alan Turing, who was working at Bletchley Park he government codebreaking establishment.!

Gottlob Frege! 76 years old (1925)! Was a German philosopher, logician, and mathematician.! Known to be the father of analytic philosophy concentrating on the philosophy of language, logic, and mathematics.! Development of modern logic in the Begriffsschrift, a book on logic.! His book Foundations of Arithmetic is the seminal text of the loficist project.!

Page 4 of 85

Konrad Zuge! 85 years old (1995)! Was a German civil engineer, computer scientist, inventor, businessman, and computer pioneer.! World’s first programmable computer; the functional programcontrolled Turing-complete Z3 was operational in May 1941.! Zuse has been regarded as the inventor of the modern computer.! Zuse was also noted for the S2 computing machine, considered the first"process control computer.! Founded one of the earliest computer businesses in 1941.!

Shafi Goldwasser! 61 years old! American-Israeli computer scientist and winner of the Turing Award in 2012! Professor of Elecrtical Engineering and Computer Science at MIT.! Chief Scientist and Co-Founder of Duality Technologies, an Israeli-American start-up which offers secure data analytics using advanced cryptographic techniques.!

Augusta Ada King, Countess of Lovelace! 36 years old (1852)! English mathematician and writer.! Work with Charles Babbage on the mechanical generalpurpose computer, the first analytical engine.! First to recognize that the machine had applications beyond pure calculation and published the first algorithm intended to be carried out by such a machine.!

Page 5 of 85

Stephen Kleene! 85 years old (1994)! American mathematician, a student of Alonzo Church! Founder of the branch of mathematical logic known as recursion theory which provided the foundations of theoretical computer science.! He invented regular expressions, and made significant contributions to the foundations of mathematical intuitionism.! Many mathematical concepts are named after him: Kleene hierarchy, Kleene algebra, the Kleene Star, Kleene’s recursion theorem and the Kleene fix point theorem.!

Margaret Hamilton! 83 years old! American computer scientist, systems engineer and businesswoman! Was the director of the Software Engineering Division of the MIT Instrumentation Laboratory, which developed on-board flight software for NASA’s Apollo space program.! Founded two software companies- Higher Order Software in 1976 and Hamilton Technologies in 1986, both in Cambridge, Massachusetts.! Received the Presidential Medal of Freedom from President Barack Obama for her work leading to the development of on-board flight software for NASA’s Apollo Moon missions.!

John von Neumann! 53 years old (1957)! Hungarian-American mathematician, physicist, computer scientist, and polymath.! Pioneer of the application of operator theory to quantum mechanics in the development of game theory and the concepts of cellular automata, the universal constructor and the digital computer.! During World War II, he worked on problem solving key steps in the nuclear physics"involved in thermonuclear reactions and the hydrogen bomb. He developed the mathematical models behind the"explosive lens"used in the imposion type nuclear weapons and coined the term "kiloton" (of"TNT), as a measure of the explosive force generated.!

Page 6 of 85

Muḥammad ibn Mūsā al-Khwārizmī! 70 years old (c. 850)! Was a persian scholar who produces works in mathematics, astronomy, and geography.! He was appointed as the astronomer and head of the library of the House of Wisdom in Baghdad.! He presented the first systematic solution of linear and quadratic equations.! One of his principal achievements in algebra was his demonstration on how to solve quadratic equations by completing the square.!

Alan Mathison Turing! 41 years old (1954)! English mathematician, computer scientist, and logician.! Highly influential in development of theoretical computer science, providing a formalisation of the concepts of algorithm and computation with the Turing machine.! Considered to the the father of theoretical computer science and artificial intelligence.! Turing played a pivotal role in cracking intercepted coded messages that enabled the Allies to defeat the Nazis in many crucial engagements and in so doing helped win the war.!

Aristotle! 62 years old (322 BC)! Greek philosopher during Ancient Greece! He is credited with the earliest study of formal logic, and his conception of it was the dominant form of Western logic until 19th century.!

Katherine Johnson! 101 years old! American mathematician whose calculations of orbital mechanics as a NASA employee were critical to the success of the first and subsequent U.S. crewed spaceflights.! First African-American woman to work as a NASA scientist.! Calculating trajectories,"launch windows"and emergency return paths for"Project Mercury spaceflights!

Page 7 of 85

IBM Fellow is an appointed position at IBM"made by IBM’s CEO. Typically only four to nine are appointed each year.

Turing Award is the highest distinction in"computer science, the "Nobel Prize of computing". Parallel computing"is a type of computation in which many calculations or the execution of" processes are carried out simultaneously.! A compiler is a computer program that translates code written in a specific programming language (source language) to another language (the target language).! A program optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources.! Substitutability"is a principle in"object-oriented programming"stating that, in a"computer program, if S is a"subtype"of T, then objects of"type"T may be"replaced"with objects of type S (i.e. an object of type T may be"substituted"with any object of a subtype S) without altering any of the desirable properties of the program (correctness, task performed, etc.)! Boolean Algebra is the branch of algebra in which the values of the variables are the truth values, true and false, are denoted as 1 and 0 respectively. !

Page 8 of 85

Week 2! • A Turing machine is a mathematical concept and can be used to simulate any computer algorithm, it has has a/an:-!

-

Infinite tape! Read-Write head! A state register! A finite table of instructions!

• Operations

- Inputs at each step! - State! - Value at current tape position! - Actions at each step! - Write a value at current tape position! - Move read/write head! - Change state!

Page 9 of 85

!

Ancient Chinese Abacus can be used for functions other than counting. It has been developed to do"multiplication,"division,"addition,"subtraction,"square root"and"cube root"operations at high speed.! !

A Portion Babbage Difference Engine, made to compute values of"polynomial functions. It was created to calculate a series of values automatically. By using the method of"finite differences, it was possible to avoid the need for multiplication and division.!

Page 10 of 85

! A Slide Rule is a mechanical"analog computer. "As graphical analog calculators, slide rules are closely related to"nomograms, but the former are used for general calculations, whereas the latter are used for application-specific computations.!

The Ishango Bone is a"bone tool, dated to the"Upper Paleolithic"era. It is a dark brown length of bone, the"fibula"of a"baboon,"with a sharp piece of"quartz"affixed to one end, perhaps for engraving. It is thought to be a"tally stick, as it has a series of what has been interpreted as"tally marks"carved in three columns running the length of the tool.!

! The Tide Predicting Machine was the first modern analog computer invented by"Sir William Thomson. It used a system of pulleys and wires to automatically calculate predicted tide levels for a set period at a particular location and was of great utility to navigation in shallow waters. His device was the foundation for further developments in analog computing.*

Page 11 of 85

Week 3! • Automata Theory!

- Deals with the logic of computation with respect to simple machines, refereed to as automata.!

- This allows computer scientists to understand how machines compute functions and solve problems.!

- Automatons are abstract models of machines that perform computations on an input by moving through a series of states or configurations.! • Characteristics of automated machines (Turing Machine, Finite State Machine) include:!

- Inputs - Outputs! - States

Page 12 of 85

Week 4! Finite State Machines • They are the simplest model of computation! • Small computer or controller!

- Limited memory! - Not a lot of computational power! • Have a start state! • Can be used to accept or generate strings.! • A deterministic finite state machine is defined by tuple (S,s1,X,Y,δ,λ) in which!

-

S is a finite set of states! s1 is the initial state! X is the finite input alphabet/set! Y is the finite output alphabet/set! δ is the state transfer function (edges)! λ is the output function!

• The FSM is defined by (Traffic Light):!

-

State set {Red, Green, Amber1, Amber2}! Input state: Green! Input alphabet {ch}! Output alphabet {green, red, amber}! State transfer function: δ (Green/ch)= Amber1, δ (Amber1/ch)= Red, δ (Red/ch)= Amber2. δ (Amber2/ch)= Green!

- Output function: λ(Green/ch)= amber, λ(Amber1/ch)= red, λ(Red/ch)= amber, λ(Amber2/ch)= green! • The FSM is defined by (Light switch):!

-

State set {Dim, Bright, Off,}! Input state: Off! Input alphabet {ch}! Output alphabet {off, dim, bright}! Sequence: Off, then dim, then Bright, then back to off! State transfer function: δ (Off/ch)= Dim, δ (Dim/ch)= Bright, δ (Bright/ch)= Off. δ Output function: λ(Off/ch)= dim, λ(Dim/ch)= bright, λ(Bright/ch)= off!

• A Turing machine is a finite state machine with a tape • A Turing machine has more computational power than a finite state machine as the finite state machine has limited memory from the number of states it has#

Page 13 of 85

Week 5! Addition and multiplication to binary • In base 10,!

- To add one, just add 1 in the 10’s column! • In base 2,!

- To add one, just add 1 in the 2’s column! • Multiplying by 2 in binary,!

- Shift all numbers left and put 0 in the first column! Universal Turing Machines • Can simulate any other Turing Machine! • Read it’s own tape:-! - The definition of the Turing Machine being simulated!

- The tape of the Turing Machine being simulated! • What are the uses of UTM’s?!

- Can imitate any computer! - E.g: Virtual machines! - Java Virtual Machine (JVM)- runs on any computer!

UTM • What are the uses of UTM’s!

- Can imitate any computer! • Virtual machines to run! • Java Virtual Machine runs on any computer!

Page 14 of 85

!

Page 15 of 85

!

Page 16 of 85

What can Turing Machines calculate? • Computable numbers: a TM which starting from a blank tape computes an arbitrarily precise approximation to that number! • Computable Functions: TM machine for addition! • Universal Turing Machine: Start the UTM on a tape which includes another TM, it can simulate the new TM.*

Page 17 of 85

Week 6!

Sets • A collection of definite, distinguishable objects such that given a set and an object, we can ascertain whether or not that object is in the set.!

- Characters! - Strings! • Elements of a set are listed between curly brackets!

- FRUITS = {apple, pear, banana}! • No duplicates! • Ø = empty set! • Singleton set contains just one element, e.g. {a} ! • Membership indicated by ∈ ! • Apple ∈ Fruits! Set notation • Denote set names by capital letters! • Denote elements in sets by lower case letters! Example: • Let set A = {x | x is prime and 0 < x < 12}! • A = {2, 3, 5, 7, 11}! • 7∈A • 7 ∉ A!

Page 18 of 85

Set notation • Set union: A ∪ B The elements in either A or B or both A and B.! • Set intersection: A ⋂ B The elements common to both A and B • Let A = {2, 3, 5, 7, 11}! • B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}! • A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} ! • A ⋂ B = { 2, 3, 5, 7}! Set equality • Set equality A = B: Both set A and set B contain the same elements! • If A = {1, 2, 3, 4} and B = {3, 2, 4, 1}! • Then A = B! Subsets • A is a subset of B: Either all elements of set A are contained in set B or set A and set B are equal. A⊆B ! • B is a superset of A: Either set B contains all elements of set A, or set B and set A are equal. B⊇A ! • A is a proper subset of B: All the elements of set a are contained in set B, but set A is not equal to set B. A⊂B ! • B contains all the elements of set a but set B is not equal to set A. B ⊃ A • A is a subset of B: Either all elements of set A are contained in set B or set A and set B are equal. A⊆B ! • The empty set is a subset of every set: ∅ ⊆ A""also%∅ ⊂ A" • Every set is a subset of itself: A ⊆ A but A ∉ A!

Example • A = {x | x is even and 1 ≤ x ≤ 10}! • A = {2, 4, 6, 8, 10} • B = {x | 1≤ x ≤ 10} • B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}! • A ⊂ B! • B ⊃ A! • A ⋂ B = A! • A ∪ B = B!

Page 19 of 85

Example: Sets, subsets • Set A = {banana, pears, apples}! • Proper subsets of A!

- ∅ ⊂ A%(Empty%set%is%a%subset%of%every%set)% - {∅}%⊄ A (A%does%not%contain%the%empty%set)% - {bananas}%⊂%A% - {pears}%⊂%A% - {apples}%⊂%A% - {pears,%bananas}%⊂%A% - {bananas,%apples}%⊂%A% - {apples,%pears}%⊂%A% - {apple,%pears,%bananas}%⊆%A% Sets of sets • Let A = {x, y, z}! • Let B be all the proper subsets of A! • B = {{}, {x}, {y}, {z}, {x,y}, {x,z}, {y,z}}! • We can write {} as ∅! Cardinality - size of set • The size of a set is the number of elements in the set! • This is indicated by |SetName|! • If A { x | 1 ≤ x ≤ 10} ! • A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}! • If B { x | x is prime and 1 ≤ x ≤ 20} ! • A = {2, 3, 5, 7, 11, 13, 17}! • Then |A| = 10 and |B| = 7! • A ⋂ B = {2, 3, 5, 7}! • |A ⋂ B | = 4! • A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 17} ! • |A ∪ B| = 13!

Page 20 of 85

Basic set notation

Page 21 of 85

Week 7! Formal Languages • Alphabet: A finite set of fundamental units (symbols, letters, tokens)! • We of write Σ as the name of an alphabet

• Σ = {a, q, r} ! • Language: A set of strings of symbol from the alphabet, plus rules specific to the language! • Words: Those strings that are permissible in the language which can be generated from the alphabet and the rules of the language! • Empty null string: ε pronounced ‘epsilon’ Describing abstract languages • Either an alphabet & exhaustive list of all valid words or an alphabet & a set of rules defining acceptable words! • The rule set must enable us to decide in a finite amount of time whether a given string is a valid word.! • Two kinds of rule-sets:!

- Test valid words! - Generate all the words in the language! Concatenation •

xn concatenated with xm is the word xn+m!

• If xxx is called a and xx is b then ab = xxxxx! • Concatenation doesn’t mean that your language membership is preserved ! • ab = ba but houseboat and boathouse is not the same! Length of strings • The length of a string is the number of characters in the string! • If a= xxxx then length (a)= 4! • If b=428 then length (b)= 3! • Length (ε)= 0! Reversing strings • If a is a word in language L, then re...