COMPSCI 92L Lecture Notes - Lecture 5: Graph Theory, App Inventor For Android, Transmission Control Protocol
20 views2 pages
11 May 2016
School
Department
Course
Professor
COMPSCI 92L
Astrachan
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
Programming
● 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
level)
○ 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
manager
find more resources at oneclass.com
find more resources at oneclass.com