Class Notes (836,174)
United States (324,364)
CAS CS 101 (27)
Lecture

Comp Sci Lecture Notes

5 Pages
61 Views
Unlock Document

Department
Computer Science
Course
CAS CS 101
Professor
David Shim
Semester
Fall

Description
Computer Science Professor Reyzin Friday, 10.25.13 Lecture ­Bit= binary digit (0 or 1), term coined by Hogn Tuker, at AT&T’s Bell Labs, 1947 1. Numbers are just bits 2. Letters have numerical codes, numbers are just bits, therefore letters = bits ­ASCII (American Standard Code for Information Interchange) chart ­Seeing Bits of a File ­Writing out individual bits is a pain ­Shorthand for 4 bits at a time (16 choices, 2^4—multiplication principle) ** FF= 11111111= 255 (hexa decimal)= (binary)= decimal Monday, 10.28.13 Lecture ­Any number b/w 0 and 2 ­1 can be written using k bits. ­So k bits can rep 2  different values (multiplication principle) ­Suppose you want to rep n different values k ­Let n= 2 . You need k= log  n2bits *log 2000= 10 *log 2000000= 20 *log 1000000000= 30 (humans) 2 *log 2000000000000= 40 ($ bills in the world) ­size     = rows X columns X bits per pixel  = rows x columns x log  c2lors ­Streisand Effect: trying to cover something up/block viewing, blown up (high resolution photo  of her house) ­Sound: pressure on ears at given moments in time, measure & represent with bits, richer sound  with higher dots per second (4000= lowest resolution allowed on phones) Friday, 11.1.13 Lecture Models, Abstractions & Layers ­Transistors operate on electric currents ­Gates (made of transistors) operate on bits ­Instructions (built from gates) operate on numbers ­Programs (built from instructions) operate on data Computer Architecture: ­A program is a sequence of instructions ­Both data and program sit in memory (RAM) ­At the heart of your computer is a processor (CPU), which simply executes instructions in order,  one at a time Two Competing Views ­Programs are bits ­In general, bits are info ­In particular, programs convey creative info to programmers, students & others ­Info is protected by freedom of speech ­Computers are devices ­Purpose of program is to make computer work ­In particular, program can do anything illegal Why the difference Matters: Implications of Creative Speech view— ­Gov’t has almost no ability to restrict programs ­No “prior restraint” on publication ­Programs are protected by copyright law ­Copyright= automatically granted monopoly to copy for lifetime + 70 years or 95 years if  corporate author Implications of Device view ­Gov’t can regulate/ban programs just like is can regulate/ban nuclear weapons, guns, toasters, or  toys ­Programs are protected by patent law ­Patent= monopoly to distribute but only if you disclose, prove novelty and pay fees; lasts 20  years Wednesday, 11.6.13 Lecture ­Linear Search ­To find x in a list of N items (worst case performance takes N comparisons) 1. Start at the beginning of the list 2. Compare current value in the list to x ­If =, stop. ­If not, go to the next value in the list ­We’ll be interested in ensuring that algorithms work well even when the input is the worst  possible (good worst case performance) ­# of times you can cut list of N items in half until you get to a single item: log2N ­Binary Search: (worst case performance­ log N c2mparisons) ­keep sub­list that’s still in play (initially it’s the whole list) ­compare X to the middle of this sub­list ­cut sub­list in half accordingly ­Repeat until sub­list size= 1 Friday, 11.8.13 Lecture ­Automated Reasoning has its limits ­Example Program: ­Input integer x>0 ­If x is even, replace it with x/2 ­Else, replace it with 3x+1 ­If x>1, go back to step 1, else stop Does there exist a program H (automation) that on input ­some program P ­some input X decides, after some finite time, if P would stop when given x as an input Lecture Notes, 11.11.13 ­Moving bits b/w 2 parties ­simple wire can be used to send sequence of bits from source to destination ­We want every pair of parties to have functionality of a wire b/w them ­How many wires?      1    +    2    +    3   …+   (n­1)= ?       +    (n­1) + (n­2) + (n­3) …+1= x ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­   n + n + n + n = 2x   n(n­1)= 2x ­Complete graph: every node is connected to every node once ­What’s inside an exchange? ­A circuit takes up a path (that’s needed if your voice takes up the whole wire capacity— analogue communication) ­To increase network capacity, add more connection (make denser graph) ­Communication in packets: ­To ease blockage, limit comm b/w two computers on a local network to a max number  of bits at a time (package) ­divide into multiple packets & send one after the other ­Typical packet: 1,500 butes Discussion 11.12.13 Gauss Formula N(N­1) = (N­1) + 
More Less

Related notes for CAS CS 101

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit