FRS
117: Google and Ye Shall Find???
Fall 2007
Core Computer Science Concepts
This is a list of fundamental computer
science concepts that we have seen to date in our study of Web
search engines.
The list will be updated as we consider new topics.
- ALL INFORMATION IS BITS
- INFORMATION
ORGANIZATION (DATA
STRUCTURES) DETERMINE EFFICIENCY OF
COMPUTATION
- core
algorithm: merging
lists
- GRAPHS
MODEL RELATIONSHIPS
AND ALLOW US TO COMPUTE PROPERTIES
- core
algorithm: visiting graph nodes
- - breadth first versus depth
first
- ITERATIVE COMPUTING PARADIGM
- see in PageRank &
HITS – convergence
- see in physical
simulations
- -simulate effects
of gravity
-
objects in balance
-
objects in motion: planets under gravity:
don't converge, move.
- REPLICATION FOR FAULT-TOLERANCE
- identical computing systems
- DISTRIBUTED COMPUTING FOR SPEED
- divide up task among processors
- improve latency:
get one task done faster
- improve throughput:
get more tasks done per unit time (e.g. per second)
- BOOLEAN ALGEBRA
- operations on values "true" and "false"
- "true" and "false" can also be represented as bits "1" and
"0"
- major applications: logic (philosophy and
mathematics), query expression, digital hardware
design
last
revision Tue Dec 4 15:30 EST 2007
Copyright
2007, Andrea S. LaPaugh