Prompt 1 Flashcards
What is the Optimal Stopping problem?
A class of problems that involve deciding when to stop searching for a better option, given limited time or resources.
What does the Optimal Stopping problem aim to determine?
The optimal point at which to stop searching, balancing the risk of stopping too early and missing a better option with the cost of continuing the search.
What is the ‘37% Rule’ in the Optimal Stopping Problem?
The optimal strategy in a simplified scenario where the goal is to maximize the chance of selecting the best option from a sequence of unknown length. It involves observing the first 37% of the options without making a choice, then selecting the next option that surpasses all the previous ones.
What real-world scenarios are often modeled as Optimal Stopping problems?
Choosing a secretary, finding an apartment, deciding when to sell a stock.
What are some of the limitations of applying the ‘37% Rule’ in real-world scenarios?
The exact percentage may vary depending on the specific problem parameters. Real-world problems often involve additional complexities, such as incomplete information or changing circumstances.
What is the Explore/Exploit trade-off?
The dilemma of choosing between exploring new options to gain knowledge and exploiting known options to maximize immediate rewards.
What is the multi-armed bandit problem, and how does it relate to the Explore/Exploit Dilemma?
A mathematical framework for modeling decision-making under uncertainty, where a gambler must choose between playing different slot machines (arms) with unknown pay off probabilities. This problem captures the essence of the explore/exploit tradeoff.
What is the Gittins Index?
A mathematical index that assigns a value to each option in a multi-armed bandit problem, taking into account its potential pay off and the uncertainty associated with that pay off.
How does the Explore/Exploit Dilemma apply to A/B testing in website design?
Exploration: Companies experiment with different versions of their website to find the one that performs best. Exploitation: Once they identify the best-performing version, they show it to most users to maximize conversions or engagement.
How does the Explore/Exploit Dilemma manifest in human relationships?
Exploration: Young adults may date many people to learn about different relationship dynamics and find a compatible partner. Exploitation: Older adults may focus on maintaining existing relationships with close friends and family.
What is sorting in the context of algorithms?
The process of arranging elements in a specific order, such as numerical or alphabetical.
What is the ‘scale hurts’ principle in sorting?
The observation that the time required to sort a set of items increases significantly as the number of items to be sorted grows larger.
What is the difference between Merge Sort and Bucket Sort?
Merge Sort: A divide-and-conquer algorithm that recursively divides the list into smaller sub-lists, sorts them, and then merges the sorted sub-lists. Bucket Sort: A sorting algorithm that distributes the elements into a number of buckets, sorts the elements within each bucket, and then concatenates the buckets.
How can understanding sorting algorithms be applied to real-life situations?
Organizing physical items (books, clothes, files), managing digital information (emails, documents), prioritizing tasks based on urgency or importance.
What is caching in the context of computer science?
The process of storing frequently accessed data in a smaller, faster memory location (the cache) to improve retrieval speed.
What is the principle of temporal locality and how does it relate to caching?
The observation that if a program accesses a particular piece of data, it is likely to access the same data again soon.
What is the Least Recently Used (LRU) cache eviction policy?
A cache management strategy that removes the least recently used item from the cache when it becomes full.
What is the ‘memory wall’ problem in computer architecture?
The performance bottleneck caused by the growing disparity between processor speed and memory access time.
What is scheduling in the context of algorithms?
The process of deciding when to execute tasks or jobs to optimize a particular performance metric.
What are some of the common metrics used to evaluate scheduling algorithms?
Completion time, Makespan, Lateness.
What is the difference between preemptive and non-preemptive scheduling?
Preemptive scheduling: Allows tasks to be interrupted and resumed later. Non-preemptive scheduling: Requires tasks to run to completion once started.
What is the Shortest Processing Time (SPT) scheduling algorithm, and what is its main advantage?
An algorithm that schedules tasks in order of their processing time, starting with the shortest task first. Its main advantage is that it minimizes the average completion time of all tasks.
What is Bayes’s Rule?
A mathematical formula that describes how to update our beliefs about the probability of an event occurring based on prior knowledge and new evidence.
What are prior beliefs and how do they influence Bayesian reasoning?
Initial assumptions or beliefs about the probability of different hypotheses before considering new evidence.
