COMPSCI 92L Lecture Notes - Lecture 4: Binary Search Algorithm, Autocomplete

11 views2 pages
11 May 2016
Professor
COMPSCI 92L
Astrachan
Spring 2016
2-3-16
Lecture 4: Algorithms and Abstractions
Uber’s algorithm:
different types of cars: Uber, UberXL, UberSELECT (need insurance certification)
surge pricing: as demand for cars at a certain time/day of the week, baseline
price goes up. Depends on both location of cars and time of day. Taxis have a
flat rate regardless of demand.
first engineered by CS researchers at Northeastern
can defeat surge pricing by walking certain blocks - algorithm is
geographically centered
algorithms must work with scale: “our algorithm generating team is a pragmatic
melding of algorithm design and massive scale”
7 Ideas of CS: creativity, abstraction, data/info, algorithms, programming,
internet, global impact
“An alternate, more succinct definition of computer science is the study of
automating algorithmic processes that scale.”
Write binary search algorithm to guess number from 1-100, 1-n where upper limit of n =
infinity (Autocomplete):
Label the target value as your key, label the user’s guess as a variable named
guess.
Have an ascending order list of all possible numbers.
After each guess, iterate through the entire sorted list to find where the guess lies
in the list.
If the guess is < key, set the lower bound of the list to be the key. The
upper bound remains the largest element in the list of 100 numbers, 100
(also the last element of a sorted list).
Else if the guess is > key, set the upper bound of the list to be the guess.
The lower bound remains the first element in the list of 100 numbers, 1
(also the last element of a sorted list).
If the guess is = key, we retain the value of the guess and return it, then
break from the iteration.
Return the value of the key.
Shotgun text reconstruction algorithm (specific to English language):
Open a text file of jumbled text separated by line numbers.
Starting with the first line, detect if there are any punctuation marks denoting the
end of a sentence. If so, look for instances of the word coming before the
punctuation mark and the punctuation mark in the other lines. Otherwise, start
with the text at the beginning of the first line.
If a match is found, add the content coming after the match to the end of
the original sentence. Delete the line with the old content.
find more resources at oneclass.com
find more resources at oneclass.com
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
Monthly
$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.