Computer Science Principles

In this lesson:

• Boolean Logic & Logic Gates
• Number Systems
• Algorithms
• File Size
• Text Compression
• Abstraction

Boolean Logic & Logic Gates:

• A boolean value is either true or false
• A comparison using a relational operator evaluates to a boolean
• = = , >, <, > =, < =, ! = 
  • The 6 signs symbols used to test the relationship between 2 variables, expressions, or values
• Logic Gates
  • AND (&&)
    • 0 && 0 = 0
    • 0 && 1 = 0
    • 1 && 0 = 0
    • 1 && 1 = 1
  • OR (!!)
    • 0 !! 0 = 0
    • 0 !! 1 = 1
    • 1 !! 0 = 1
    • 1 !! 1 = 1
  • NOT (!)
    • ! 0 = 1
    • ! 1 = 0

Number Systems:

• Number bases including binary/decimal are used to represent data
• Binary (base 2) uses combinations of digits 0 and 1 (in bits)
• Decimal (base 10) uses combinations of digits 0-9
  • With decimal, digit’s position in binary sequence determines # value (equal to bit’s value multiplied by place value of its position)
  • With binary, the place value of position is determined by the base raised to the power of position (positions are numbers starting right, increasing to the left)
• Bit (binary digit 0 or 1; 1 byte = 8 bits)
  • Computer represent data digitally (lowest level is bits)
  • They are grouped to represent abstractions (numbers, characters, colors)
  • Some sequences of bits can represent different types of data in different contexts
    • Ex: ASCII table (when a number represents a character)
    • Ex: 1010 = 8421 = 8+2 = 10

Algorithms:

• A set of instructions
• Can be written in different ways to do the same thing
• Ones that look the same can have different side effects/results
  • Ex: Robot pseudocode

File Size:

• Byte (8 bits): standard “chunk” for binary information
• Kilobyte (KB): 1,000 bytes
• Megabyte (MB): 1,000,000 bytes or 1,000 KB
• Gigabyte (GB): 1,000,000,000 bytes or 1,000 MB
• Terabyte (TB): 1,000,000,000,000 bytes or 1,000 GB
• Petabyte (PB): 1,000,000,000,000,000 bytes or 1,000 TB
• Exabyte (EB): 1,000,000,000,000,000,000 bytes or 1,000 PB
• Typical file sizes:
  • .txt : 2.5 KB
  • .jpg image: 100 - 1,000 KB
  • Animated gif: 250 KB or 2 MB
  • .pdf file: under 10 MB
  • Audio file as .mp3: 1 MB
  • .mov or .mp4 movie: 15 MB

Text Compression: 

• To save time/storage, information is compressed (reduce size/ number of bits of transmitted/stored data)
• However, fewer bits DOES NOT mean less information
• Amount of size reduction depends on amount of original data and the compression algorithm
• Lossless Data
  • Data remains in file after uncompressed
  • All information can be restored
  • Text, spreadsheets, gif
• Lossy Data
  • Reduces file size permanently by getting rid of certain information
  • Some information can be restored
  • Video, sound, jpeg
  • Can reduce file size more than lossless data

Abstraction:

• Process of reducing complexity by focusing on main idea
• Hiding irrelevant details related to question and bringing together useful details
• Uses complexity and allows one to focus on the idea
  • Ex. use of digital data to approximate real world analog data

In this lesson:

• What is the Internet?
• Building a Network:
• IP and DNS
• How Information Travels
• Layers of the Internet
• Digital Divide

What is the Internet:

• The Beginning of the Internet:
  • The Internet was the result of the ARPANET experiment
    • A defense department project
    • Paul Baran wanted to find a network that could survive a nuclear attack on the United States
    • He found that a distributed network was better than a centralized network 
    • Distributed Packet Switching Network: break messages into blocks and send them to every network location
• Who controls the internet?
  • No one and everyone
    • Internet comes from a series of independently operated networks to your own provider
• Internet: a global network of computing devices communicating with each other in some way (e.g. sending emails, downloading files, sharing websites)
  • It is an open network: any device can join as long as they follow rules
  • In networking, the rules are known as protocols and they define how each device must communicate with each other
• Ingredients of the Internet
  • Wires & Wireless: physical connections between devices plus protocols for converting electromagnetic signals into binary
  • Internet Protocol (IP): a protocol that uniquely identifies devices using IP addresses and provides a routing strategy to send to a destination IP address
  • TCP (Transmission Control Protocol)/ UDP (User Datagram Protocol): protocols that can transport packets of data from one device to another and check for errors along the way
  • TLS (Transport Layer Security): a secure protocol for sending encrypted data so that attackers can’t view private information
  • HTTP/DNS: the protocols powering the World Wide Web, what the browser uses every time you load a webpage

Building a Network:

• Computing device: a machine that can run a program, including computers, tablets, servers, routers, and smart sensors
• Computing system: a group of computing devices and programs working together for a common purpose
• Computing network: a group of interconnected computing devices capable of sending or receiving data
• Path: a series of connections between computing devices on a network starting with a sender and ending with a receiver
• Bandwidth: maximum amount of data that can be sent in a fixed amount of time, usually measured in bits per second
• Routing: the process of finding a path from sender to receiver; usually dynamic on the Internet, not specified in advance

IP and DNS:

• The Internet is a design philosophy/architecture expressed in a set of protocols ( a well known set of rules/standards used to communicate between machines)
  • This allows the Internet to adapt and absorb new communication technologies because it just needs protocols
• IP (Internet Protocol): one of the most important protocols in internet communication
  • Describes how 2 computers communicate with each other
  • Used by every computer
  • Each computer has an IP address
  • Computer asking another computer for information
    • Computer sends other computer its IP address and its origin address so the other computer knows where to send its response
    • Number is unique to each device on the network
    • Set up in a hierarchy, split into 4 numbers from 0-255
    • Traditional IP addresses are 32 bits long (8 bits per each part)
      • country/network, region/network, subnetwork, device
    • This is IPv4 - provides for 4 billion unique addresses (1973)
    • IPv6 is in the process: 128 bits per address - 340 undecillion unique addresses
• DNS (Domain Name System): associates names (www.-----.com) with corresponding addresses
  • Computer uses the DNS to look up domain names and get the associated IP address which connects your computer to internet destination
  • DNS servers are connected in a distributed hierarchy
    • Divided into zones, splitting up responsibilities for each major domain (.org, ,com, etc.)
  • It is an open public communication protocol
    • Susceptible to cyber attacks
    • DNS Spoofing: when a hacker goes into a DNS server and changes it to match a domain name with the wrong UP address (takes you to wrong website)
    • Gives humans a easy way to find where we want to go on the internet
  • Domains - IP addresses
    • Every domain name we type maps to an IP address, but computer figures it out
      • Checks local cache
      • Asks ISP cache
      • Asks home servers

How Information Travels:

• How is the Internet like the US Post Office?
  • Communication systems (trucks/wires)
  • Deliver information (magazines/websites)
  • Have size limits for individual packages
  • Large shipments are broken up into small pieces
• Circuit v. Packet Switching
  • Circuit Switching: once you create a connection, you keep it until all of your message is sent
  • Packet Switching: message is broken up and many messages are sent sharing a connection
    • Selected for the Internet because it is more flexible
    • The selected route can be optimized at each moment in time and it allows for packages of unlimited size
• Methods to send bits of info (atoms of the Internet): 
  • Electricity: connected by copper wire
    • 0 - off, 1 - on : binary information
    • Bits can be also be counted by time (bit/sec)
    • To go faster, increase bandwidth (maximum transmission capacity of a device)
    • Another measure of speed is latency (time it takes for a bit to travel from one place to another)
    • Pro: cheap
    • Cons: signal loss (with ethernet wire)
  • Light: send bits as light beams using fiber optic cable (thread of glass engineered to reflect light)
    • Can send multiple bits at a time because of angle of beams sent
    • Pros: really fast, no signal lost (can connect continents)
    • Cons: expensive, hard to work with
  • Radio waves (wireless: uses radio signal to send bits from one place to another)
    • Translate 0 and 1 to binary radio waves frequency
    • Pros: totally mobile
    • Cons: short range
• Packet: small segment of data that’s bundled for sending over transmission media; contains address of computer of peripheral device to which it’s being sent
  • Information is sent in packets of data
  • Many kinds of digital information can be sent with IP packets bit there are limits
    • Different packets are sent in a different route with the IP address it came from and where it’s going then are reassembled 
    • Routers: “traffic managers” that keep the packets moving through networks smoothly
    • Packets try to travel the cheapest way (time, politics, relations with companies) which is usually not the most direct
    • Fault tolerant: network can keep sending packets even if something goes horribly wrong (key principle for reliability)
• TCP (Transmission Control Protocol): manages sending and receiving of all data as packets
  • Completes inventory to make sure all packets are delivered 
  • If it is, its signs and verifies packets
  • TCP and router systems are scalable (can work for 8 or 8 billion devices)
    • Because of fault tolerance and redundancy, growing and scaling occurs without interrupting service
• Networks connect, communicate, and collaborate because of agreed upon protocols
  • Nodes: connecting points to route the data traffic
  • Server: a computer that waits and responds to requests for data
  • Client: a computer that requests data stored on a server

Layers of the Internet:

• Datastream: information passed through the internet in packets
• Packet metadata: data about data; data added to packets to hep route them through the network and reassemble the original message
• TCP (Transmission Control Protocol): a protocol for sending packets that does error checking to make sure all packets are received and properly ordered
• UDP (User Datagram Protocol): a protocol for sending packets quickly with minimal error-checking and no resending of dropped packets
• Web Browsing
  • Enter your web address or URL (Uniform Resource Locator)
  • Your computer connects/talks to a server, usually far away and they communicate in milliseconds in HTTP (Hypertext transfer protocol)
• The Internet is completely open, connections are shared. Information is sent in plain text which makes it easier hackers to see your information
• Scalability: the capacity for the system to change in size and scale to meet new demands
• World Wide Web (WWW): a system of linked pages, programs, and files (NOT THE INTERNET)
• HTTP (Hypertext Transfer Protocol): protocol for computers to request and share pages that make up WWW and internet
• Layers of the Internet
  • The internet is made up of protocols that work together to move information around the network
  • Higher layers rely on lower ones
  • From lowest to highest: Physical network, IP, TCP/UDP, HTTP and DNS

Digital Divide

• The fact that some people have access on the internet and know how to use it effectively, while other people don’t 
• Or people cannot financially afford Internet-accessing devices or access the Internet
• Internet access is required in order to access opportunities, education, and other necessary resources in today’s world: education, applying for jobs, filing taxes, bus schedules, medical care
• Factors:
  • Lack of internet infrastructure and resources
    • Urban v. Rural
    • Poor v. Rich
    • Old v. Young
  • Government censorship of the Internet
    • North Korea, Iran, Russia

In this lesson:

• Abstraction
• Procedural Abstraction
• Algorithms
• Algorithm Vocabulary
• Types of Algorithms
• Efficiency of Algorithms
• Measuring Efficiency
• Solving Problems with Algorithms
• Searches

Abstraction: Represents complex idea with something simple (this is the main idea of Computer Science Principles)

• Using a variable name to represent a concept
• Using a list to represent a collection of items as one list
• Using a function that someone else wrote but that you can use without understanding the code

Procedural Abstraction: process/procedure

• Provides a name for a process and allows a procedure (function) to be used only knowing what it does, not how (e.g. finding the maximum number in a list by coding)
• Allows solution to large problem to be based on solutions of smaller problems
  • Helps improve code readability
• Code can be reused

Algorithms: 

• Finite set of instructions to accomplish a specific task
• Can be expressed in natural language, pseudocode, and/or programming language
• Can be written in different ways, still accomplish some tasks
• Algorithms that appear similar yield different side effects/results
• Different algorithms can be developed or used to solve the same problem
• Can be created from…
  • Idea
  • Modifying existing algorithms
  • Combining existing algorithms
  • Constructed using combinations of…
    • Sequencing (step by step reading of code in order)
    • Selection (conditionals)
    • Iteration (loops)

Algorithm Vocabulary:

• To execute (execution) a program = run program
• Documentation - add comments to program
• Procedure (function) interrupts sequential execution of a program
  • Function must be executed before program continues
  • Functions end when last statement/return statement is made

Types of Algorithms:

• Sequential Algorithm: executed from start to finish on one computer
• Parallel Algorithm: Executes instructions at same time of different processing devices and them combine all the individual outputs to produce a final result
  • Used when there are several lines of code 
  • Less time consuming
• Speed Up: ratio that compares run time of sequential algorithm to parallel algorithm
  • Ex. Sequential: 30 mins;  Parallel: 10 mins;   Speed Up: 3:1 or 3

Efficiency of Algorithms:

• Estimation of amount of computational resources used by the algorithm
• Expressed as a function through size of input
• Determined through formal or mathematical reasoning
• Can be informally measured by determining the number of times a statement(s) execute
• Different correct algorithms for the same problems have different efficiencies

Measuring Efficiency:

• Polynomial/cloer (constant, linear, square, cube) efficiencies run in a reasonable amount of time
  • Ex. 2n
• Exponential/factorial efficiencies run in an unreasonable amount of time
• Same problems can’t be solved in reasonable amounts of time because there is not efficient algorithm, so approximate solutions are found

Solving Problems with Algorithms:

• Optimization Problem: finding the “best”/fastest solution among many
• Decidable Problem: an algorithm written to find outputs for all inputs and find a solution
• Undecidable Problem: no algorithm will always work
• Heuristic: way to solve problem, but not “best” (fastest/cheapest), it is still a way to work

Searches:

• Linear/Sequential Search: you keep going through the list in order to find the solution (beginning to end)
• Binary Search: starts in the middle of set of sorted data, eliminate half of data by dividing it by 2
  • More efficient than linear search
• Libraries: contains procedures that may be used in creating new programs
  • Can come from existing code
  • Need documentation
  • This is easier because you don’t have to rewrite code

In this lesson:

• Learning from Data/Trends
• Exploring One Column
• Filtering & Cleaning Data
• Big, Open, and Crowdsourced Data
• Machine Learning/Bias

Learning from Data/Trends:

• Data visualizations help us answer: 
  • “I think this visualization tells me this…”
    • Something is more popular than something else
    • Something is more important than the other
    • Something has become more or less searched over time
  • “...but I am not sure because…”
    • I don’t know how the data was collected
    • The data doesn’t tell the reason for a certain trend/correlation
    • We need more data
• Visualizations
  • Help us look at lots of data at once
  • Help see patterns that are “invisible” if you just look at a table
  • When looking, consider:
    • What does this data show? (FACT)
    • Why might this be the case? (OPINION)
  • CORRELATION ≠ CAUSATION
    • Use this when making assumptions about data
  • Programs (data visualizer) help princess data so we can understand it and learn
  • charts/visuals help find and communicate what we’ve learned from data

Exploring One Column:

• Metadata: data about data
  • Can be changed without impacting the primary data
  • Used for finding, organizing, and managing information
  • Increases effective use of data by providing extra information
  • Allows data to be structured and organized
• Data analysis process:
  • 1. Collect or choose data
  • 2. Clean and/or filter
  • 3. Visualize and find patterns
  • 4. Generate new information
• Bar Chart: count how many times each value in the column appears and make a bar at that height
  • If column has too many unique values, it gets difficult to make any sense of them or find patterns
• Histograms: similar to bar chart but first, all numbers in a range are grouped together
  • Can only be created with numbers but useful when bar chart is hard to read

Filtering & Cleaning Data:

• Cleaning Data
  • Why clean data?
    • Data is incomplete
    • Data is messy
    • Data is invalid
  • What is messy data?
    • User enters different types of data (“two”, 2)
    • Users use different abbreviations to represent same information (“Feb”, “Febr”)
    • Data has different spellings (“Color”, “Colour”) or inconsistent spellings (“Spring”, “spring”)
• Filtering Data: allows the user to look at a subset of the data
  • Instead of using traversals, software programs with built in tools (data visualizer) can be used to filter data

Big, Open, and Crowdsourced Data:

• Big Data: Evaluating the large amount of information that a computer has to go through by using parallel processing (Taking large numbers of data and many computers process at the same time)
• Open Data: Data that is available to the public by being published publicly
  • Ex: weather app, GPS app
• Citizen Science: effort to get public engaged in science and using knowledge to solve real world problems
  • Example: Migratory patterns, climate change information
  • Members of the public collect, analyze, spread information about data for research
  • Technology allows anyone to be involved in citizen science

Machine Learning/Bias:

• Machine Learning: computers recognize patterns and make decisions without being explicitly programmed
  • Ex: text, email, filters
  • Computers learn with trial and error
  • Machine Learning can take any kind of data
  • Training data needs to be of high quality
• Bias Data: Favors some things/de-prioritizes others
  • Need a lot of training data to prevent this
• Algorithmic bias: exclusionary experiences/discriminated
  • Need full spectrum inclusion
• Bias warning: Need to make sure to not use prejudice when training data that perpetuated human bias

In this lesson:

• Online Security
• Legal & Ethical Concerns
• Computing Innovations

Online Security:

• Personal identifiable information (PII) is information about an individual that identifies links, relates, or describes them.  
• Examples of PII include:
  • Social Security Number
  • Age
  • Race
  • Phone numbers
  • Medical information
  • Financial information
  • Biometric data (fingerprint and retinal scans)
• Search engines can record and maintain a history of search made by users.
  • Search engines can use search history to suggest websites or for targeted marketing.
• Websites can record and maintain a history of individuals who have viewed their pages.
  • Devices, websites, and networks can collect information about a user’s location.
• Technology enables the collection, use, and exploitation of information about by and for individuals, groups and institutions.
• Personal data such as geolocation, cookies, and browsing history, can be aggregated to create knowledge about an individual.
• Personal identifiable information and other information placed online can be used to enhance a user’s experiences.
• Personal identifiable information stored online can be used to simplify making online purchases.
• Commercial and government curation (collection) of information may be exploited if privacy and other protections are ignored.
• Information placed online can be used in ways that were not intended and that may have a harmful effect.  
  • For example, an email message may be forwarded, tweets can be retweeted, and social media posts can be viewed by potential employers.
• Personal identifiable information can be used to stalk or steal the identity of a person or to aid in the planning of other criminal acts.
• Once information is placed online, it is difficult to delete.
• Programs can collect your information and record where you have been, how you got there and how long you were at a given location.
• Computing resources can be misused.  It is important to protect users.
• All real world systems have errors or design flaws that can be exploited to compromise them.  Regular software updates help fix errors that could compromise a computer system.
• Users can control the permissions programs have for collecting and user information.  Users should review the permission settings of programs to protect their privacy.
• Authentication measures protect devices and information from unauthorized access.
  • Examples of authentication measures include strong passwords and multi factor authentication.  
  • A strong password is something that is easy for a user to remember but would be difficult for someone else to guess based on knowledge of that user.
• Multifactor authentication is a method of computer access control in which a user is only granted access after successfully presenting several separate pieces of evidence to an authentication mechanism, typically in a least two of the following categories:
  • knowledge (something they know like a password)
  • possession (something they have like a phone)
  • inference (something they are like a fingerprint).  
  • Multi Factor authentication requires at least two steps to unlock protected information; each step adds a new layer of security that must be broken to gain unauthorized access.
• Encryption is the process of encoding data to prevent unauthorized access 
• Decryption is the process of decoding data.
• Two common encryption approaches are:
  • Symmetric key encryption involves one key for both encryption and decryption.
  • Public key encryption pairs a public key for encryption with a private key of decryption.  
    • The sender does not need the receiver’s private key to encrypt a message, but the receiver’s private key is required to decrypt the message.
• Certificate authorities issue digital certificates that validate the ownership of encryption keys used in secure communications and are based on a trust model.
• Computer viruses and malware scanning software can help protect a computing system against infection.
• A computer virus is a malicious program that can copy itself and gain access to a computer in an unauthorized way. 
  • Computer viruses often attach themselves to legitimate programs and start running independently on a computer.
• Malware is software intended to damage a computing system or to take partial control over its operation.  
  • Untrustworthy (often free) downloads from freeware or shareware sites can contain malware.
• Phishing is a technique that attempts to trick a user into providing information.  That personal information can then be used to access personal information.  
  • That information can be used to  access sensitive online resources, such as bank accounts and emails.  
  • Unsolicited emails, attachments, links, and forms in email can be used to compromise the security of a computing system. 
  • These can come from unknown senders ro from known senders whose security has been compromised.
• A malicious link can be disguised on a web page or in an email message.
• Keylogging is the use of a program to record every keystroke made by a computer user in order to gain fraudulent access to passwords and other confidential information.
• Data sent over public networks can be intercepted, analyzed, and modified.  One way that this can happen is through a rogue access point. 
  • A rogue access point is a wireless access point that gives unauthorized access to secure networks.

Legal and Ethical Concerns

• Material created on a computer is the intellectual property of the creator or an organization.
• Ease of access and distribution of digitized information raised intellectual property concerns regarding ownership, values, and use.
• Measures should be taken to safeguard intellectual property.
• The use of material created by someone else without permission and presented as one's own is plagiarism and may have legal consequences.
• The use of material created by someone other than use should always be cited.
• Creative commons, open source, and open access have enabled broad access to digital information.  As with any technology, using computing to harm individuals or groups raises legal concerns.  Computing can play a role in social and political issues, which in turn raised legal and ethical concerns.
• Some example of legal ways to use materials created by someone else include:
  • Creative Commons - a public copyright license that enables the free distribution of an otherwise copyrighted work.  This is used when the content curator wants to give others the right to share, use, and build upon the work they have created.
  • Open source - programs that are made freely available and may be redistributed and modified.
  • Open access - online research output free of any and all restrictions on access and free of many restrictions on use such as copyright or license restrictions.

Computing Innovations  

• The effect of a computing innovation can be both beneficial and harmful
• Not every effect of a computing innovation is anticipated in advance.
• A single effect can be viewed as both beneficial and harmful by different people, or even by the same person.
• Computing innovations have often had unintended beneficial effects leading to advances in other fields.
• A computing innovation can have an impact beyond its intended purpose.
• Advances in computing have generated and increased creativity in other fields, such as medicine, engineering, communications, and the arts.
• Computing innovations can be used in ways that their creators had not originally intended:
• The World Wide Web was originally intended only for rapid and easy exchange of information within the scientific community.
• Targeted advertising is used to help businesses, but it can be misused at both individual and aggregate levels.
• Machine learning and data mining have enabled innovation in medicine, business, and science, but information discovered in this way has also been used to discriminate against groups of individuals.
• Information posted to social media services can be used by others.  
  • Combining information posted on social media and other sources can be used to deduce private information about you.