CSP TEST - MONDAY (JAN 12th)

arguments

The actual values passed to a procedure’s parameters when it is called.

binary search

A search algorithm that repeatedly halves a sorted list to find a target.

brute force

A method that tries every possible option.

distributed computing

A model where multiple networked computers run a program together.

heuristic algorithm

An algorithm that finds an approximate solution quickly for complex problems.

intractable problems

Problems that cannot be solved in reasonable (polynomial) time.

linear or sequential search

A search algorithm that checks each element from start to end.

parallel computing

A model where parts of a program run simultaneously using multiple processors or computers.

parameters

Input variables defined by a procedure.

reasonable time

Polynomial time.

sequential computing

A model where operations run one at a time on a single processor.

sorting algorithm

An algorithm that arranges items in numeric or alphabetical order.

The Halting Problem

The undecidable problem of determining whether a program will stop or run forever.

The Traveling Salesman Problem

Finding the shortest route visiting each city once and returning to the start.

undecidable problems

Problems with no algorithm that always gives a correct yes-or-no answer.

Binary Search Worst Case

⌈log2 N⌉ + 1 (or O(log N)).

Linear Search Worst Case

N (or O(N)).

Binary Search Usage

Use when data is sorted.

Linear Search Usage

Use when data is unsorted or very small.

Binary Search Pseudocode

Set low=1, high=N; loop while low

Logo 2 Parameters

:SIDES (number of sides) and :LENGTH (side length/size).

Procedure Calls

Executing a defined procedure (function) with specific values (arguments) for its parameters.

Algorithm Rating Elements

Efficiency (Time/Space complexity) and Clarity/Correctness.

Intractable Problems Importance

They form the basis of cryptography (encryption); security relies on these problems being too hard for computers to solve quickly.

Parallel Computing Benefits

Faster execution and the ability to handle massive datasets.

Parallel Computing Challenges

Complexity in coding, deadlocks, and the overhead of coordinating processors.

Search Engine Spider

A program that automatically "crawls" the web, visiting pages and following links to build an index.

Search Ranking Elements

Words on the page (Keywords), Location of words (Title vs. Body), Links from other pages (PageRank/Authority), and Anchor text of those links.

Search Result Consistency

Results generally vary due to personalization (user history), geographic location, and different data centers.

SEO (Search Engine Optimization)

The practice of tuning a website (using keywords, linking strategies) to rank higher in search engine results.

Google and "Do No Evil" in China

Dishonored by launching a censored search engine (2006); Honored by withdrawing search services to Hong Kong (2010) to refuse censorship.

Overture Innovations Copied

Pay-per-click and Keyword Auction.

Google's Auction Modification

Google modified the auction by adding a "Quality Score" (relevance), so ranking is determined by Bid * Quality, not just the highest bid.