COMPSCI 92L Lecture Notes - Lecture 4: Binary Search Algorithm, Autocomplete
11 views2 pages
11 May 2016
School
Department
Course
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