# 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