New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: clu2 Notetaker
clu2 Notetaker

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Material from second half of course
Programming Abstractions
Keith Schwartz
75 ?




Popular in Programming Abstractions

Popular in ComputerScienence

This 12 page Bundle was uploaded by clu2 Notetaker on Tuesday January 12, 2016. The Bundle belongs to CS106A at Stanford University taught by Keith Schwartz in Winter 2015. Since its upload, it has received 71 views. For similar materials see Programming Abstractions in ComputerScienence at Stanford University.

Similar to CS106A at Stanford

Popular in ComputerScienence


Reviews for CS106A


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 01/12/16
CS106A 2/25/15 notes Graphs and Networks A social network, synonyms A graph is a mathematical structure for representing relationships in CS A graph consists of a set of nodes connected by edges Nodes: people Edges: links between people Some graphs are directed -Indicates the outcome of the "game" - think the unhappy faces at the bottom, and the happy faces at the top Some graphs are undirected -You can think of them as directed graphs with edges both ways How can we represent graphs in Java? Representing graphs Node Connected to All colors Different colors of faces WikipediaGraph Program General Announcements! Midterm: Up until today's lecture Bulk of the material will be on Assignment 5 and 6 Take the practice exam on Thursday Preparing for exam -Type all solutions into a computer and debug them until they work correctly -Look over the reference solutions -Rewrite your old assignments and problems from section handouts on paper, then repeat the above process -Read over the textbook to see new patterns and learn more about concepts Network Analysis -We can analyze how nodes in a graph are connected to learn more about the graph -Sample questions:  How connected are nodes in a graph?  How important is each node in the graph?  How resilient is the graph? Finding important nodes -Suppose we want to have the computer find important articles on Wikipedia -We just have the link structure, not the text of the page, the number of edits, the length of the article, etc. Link analysis -To find important Wikipedia pages, let's look at the links between pages -We'll make two assumptions: The more important an article is, the more pages will link to it The more important an article is, the more that its link matter An article is important if other important articles ink to it Random Surfer Model -Think about the behavior of a Wikipedia reader who randomly surfs Wikipedia -Visits some initial page at random -From there, the user either Clicks a random link on the page to some important article Ranking articles with the RSM -Randomly walk though graph -At the step, either Jump to a totally random article, or follow a random link public void run(){ HashMap<String, Integer> importance = rankArticles(articleTitles, links); } private HashMap<String, Integer> rankArticles(ArrayList<String, articleTitles, HashMap<String, ArrayList<String>){ HashMap<String, Integer> frequencies = new HashMap<String, Integer>; String currPage = chooseRandomPageFrom(articleTitles); for(int i = 0; i<NUM_ITERATIONS; i++){ if(!frequencies.contansKey(currPage)){ frequencies.put(currPage)){ } else { } RandomGenerator rgen = RandomGenerator.getInstance(); if(rgen.nextBoolean(TELEPORT_PROBABILITY)){ currPage = chooseRandomArticleFrom(articleTitles); } else { currPage = chooseRandomArticleFrom(links.get(currPage)); } } } CS106A 2/27/15 notes Classes Designing your own classes will greatly extend your programs Objects and Primitives -Our programs have worked with two types of data: primitives and objects -Primitives are data types int, double, char, and boolean -They're built into Java - you can't define your own primitive types! -Objects are types like ArrayList, String, RandomGenerator, and GPoint -Where do these types come from??? Objects Revisited -An object is a combination of State - persistent information, and Behavior - the ability to operate on that state GRect state:  position move  size change color  color change fill state  is filled report position  etc. etc GPoint  Position move move by angle move polar etc. String state:  Character sequence Get characters produce substrings etc. Classes and Objects -Every object is an instance of a class -The class determines  what state each instance maintains  what behaviors each instance possesses -Each instance determines  the specific values for that state information Class Dog -Has fur color -Has energy level -Has a cuteness level -Can be friends -Can sit -Can stay -Can bark Creating Classes -People counter (tallying device) State: The current number * Use instance variables to keep track of state Behavior: -Can read counter -Can increment the counter * We use methods to specify behavior CountingIsFun program public class CountingIsFun extends ConsoleProgram{ public void run(){ counter c1 = new Counter(); Counter c2 = new Counter(); for(int i = 0; i<5; i++){ c1.increment(); } for(int j = 0; j<137; j++){ c2.increment(); } println(" " + c1.getValue()); println(""" + c2.getValue()); } } public class Counter{ // not a program!!! // state private int value = 0; // behavior public void increment(){ value++; } public int getValue(){ return value; } } Creating objects -Each object is an instance of a class -You can create an object that's an instance of a given type by writing new Type(args) -This is sometimes called instantiating the class Note: when you have two objects that are Counters, the values are always different and kept separate. They work independently Private vs. Public -private int value is hidden from the other classes. It is only visible in the Counter class -public void increment() and getValue(): Any class with these objects can use these values Why hide information? -Making instance variables private and mediating access through public methods has man y advantages -Separates what you can do from how it’s done -We never talked about how GOval or HashMap actually work, but you can still use them -Preventing meaningless operations -A counter may be implemented using an int, but it's not actually an int and not all operations on ints make sense Modifying our class What if you want to start at 1000? Constructor -A constructor is a special method defined in a class that is responsible for setting up class's instance variables to appropriate values -Syntax: public nameOfClass(arguments) { // body of constructor } Inside a constructor: -Gives initial values to instance values -Set up instance variables based on value specified in the parameters -Constructor called when an instance variable is Modification in program: public Counter(int initialValue){ value = initialValue; } However, when you have an instructor, you have to put in an initial value Counter c1 = new Counter(1000); Without the 1000, Java will have an error But with println, you get a bunch of random stuff! toString() -To get a string representation of an object, Java uses a method public String toString() -If you define this method in your Java classes, you can customize what string will be produced -Otherwise, you get icky Javaspeak representations public String toString(){ // add this to the class return "{"+value+"}"; } CS106A 3/2/15 notes Map.size will tell you how many keys there are in the HashMap Today's a fun lecture Machine Learning Perceptron Learning One Approach -Train the perceptron on valid data. -For each data point: -Ask the perceptron what it thinks. -If correct, do nothing. -Otherwise, nudge w₀ … wn in the right direction. -Repeat until number of errors is “small enough.” Question: What kind of mistakes can we make? x₁ x₂ x₃ x₄ x₅ x₆ ... xn +1 + w₁ YES > 0 False Positive A Cute Math Trick  For false positives, set wk = wk – αxk.  For false negatives, set wk = wk + αxk.  For correct answers, set wk = wk.  Let “YES” be 1 and “NO” be 0.  Consider the difference between the actual answer and perceptron guess:  False positive: Actually NO, we say YES. Difference is -1.  False negative: Actually YES, we say NO. Difference is +1.  Correct answer: Both YES or both NO. Difference is 0.  General update rule: wk = wk + α(real – guess)xk. Perceptron Learning Algorithm  Start with a random guess of each wk.  Repeat until perceptron is sufficiently accurate:  Choose a training example (x₀, x₁, ..., xn).  Let real be the real answer, guess be the perceptron's guess.  For each k, set wk = wk + α(real - guess)xk  Note: Use batching in practice.  Update everything all at once. Application: Handwriting Application: Handwriting Analysis  Train a computer to recognize handwritten numbers 0 – 9.  Large training and test set available (MNIST Handwritten Digit Database) CS106A 3/4/15 Networking Computer Networks ● Computer networks allow us to get amazing things done. ● Sharing knowledge (Wikipedia, Khan Academy, Coursera, Udacity, etc.) ● Solving huge problems (folding@home, Mechanical Turk, etc.) ● Computer networks prevent us from getting amazing things done. ● Social networks (Facebook, Google+, etc.) ● Streaming video (Netflix, Hulu, etc.) Sending Data ● Data is sent across the Internet in packets. ● Each packet contains a message (called the payload), along with extra information to help it get to its destination correctly IP Addresses ● Each computer may have one or more IP addresses so that it can receive messages over the Internet. ● Similar to a phone number. ● There are two types of IP addresses: ● IPv4: 232 possible addresses (about four billion), and we've just about run out! ● IPv6: 2128 possible addresses (about 4×1034), and we're very unlikely to run out in the future. Hostnames ● In order to make it easier to find remote computers, computers can have names associated with them. ●, ● These names are called hostnames. ● A system called the domain name system (or DNS) is responsible for converting domain names into IP addresses. ● Like a huge HashMap A Small Problem ● At any one time, you could be ● Surfing the web, ● Downloading music from iTunes, ● Checking your email, ● etc. ● You might have packets from many different machines all arriving at once. How does the computer know how to send each message to the right program? Ports ● Every packet is labeled with a port number that lets the destination computer know how to process the message. ● Has nothing to do with physical ports on the computer; it's just a way of differentiating traffic. ● Different applications listen in on different ports: ● Sending mail (SMTP): Port 25 ● Browsing the web (HTTP): Port 80 ● Checking email (IMAP): Port 143


Buy Material

Are you sure you want to buy this material for

75 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.