COMPSCI 92L Lecture Notes - Lecture 5: Graph Theory, App Inventor For Android, Transmission Control Protocol

20 views2 pages
11 May 2016
Spring 2016
2-12-16 to 2-26-16
Internet Packets and Routing, Programming
Telephone Networks
Telephone Networks have the following characteristics:
dedicated line, synchronous connection, limited in scale, vulnerable to disruption
Packet - format for sending bits/information through different media (ex. email, music)
routing packets - protocol to ensure reliable delivery in a network that isn’t totally reliable
Internet is not made up of direct connections, since when multiple users log in,
information transfer wouldn’t occur efficiently
information route doesn’t have to be consistent
packet - travels same way you do when you get around, each packet has address of
where it’s coming from to where it’s going
may arrive at different times/out of order
router: keeps track of multiple routes, cheapest: cost, politics/relationships b/w
companies, time efficiency
● fault-tolerant
transmission control protocol - “guaranteed mail service,” monitors whether packets
accumulated for a specific request are all there at the same time
scalable, work w/ any number of devices
can grow/scale w/o service interruption
Traveling Salesperson Problem: can you visit every city some place flies to without going
to any city twice and end up at the origin city, and can you do this under a set cost?
start and end at the same location
problem in graph theory that requires the most efficient path
no current solution (NP-hard level CS problem, nondeterministic polynomial
ex. if I want to get from RDU > ATL > BWI > ALB > PHX > LAX > RDU, which
order covers the least distance and costs less than $25k?
ex. UberPool uses an approximate TSP algorithm to ensure that multiple riders
can get an acceptable route for each distance inputted
remainder of class: Skype w/ Sophia Cui, Duke ℅ 11’, Uber software engineer/program
find more resources at
find more resources at
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.