Hypotheses n the traditional sciences a hypothesis typically concerns some phenomenon in the physical world In computer science, some hypotheses are of this kind Other hypotheses involve construction, such as whether a proposed method is fit for a certain purpose and solvability
Hypotheses • In the traditional sciences, a hypothesis typically concerns some phenomenon in the physical world. • In computer science, some hypotheses are of this kind. • Other hypotheses involve construction, such as whether a proposed method is fit for a certain purpose and solvability
Hypotheses in computer science For example: a research question whether it is possible to make better use of cpu cache to reduce computational costs reducing the number of memory accesses can make a program faster even if the number of instructions executed is unchanged
Hypotheses in computer science • For example: a research question whether it is possible to make better use of CPU cache to reduce computational costs • reducing the number of memory accesses can make a program faster even if the number of instructions executed is unchanged
Sorting algorithm hypothesis improved by replacing a tree-based structure with poor locality by an array-based structure with high locality The research goal is to test this hypothesis The phenomenon that should be observed: as the number of items to be sorted is increased the tree-based method should increasingly show a high rate of cache misses compared to the array-based method The data is the number of cache misses for several sets of items to be sorted
Sorting algorithm • Hypothesis – improved by replacing a tree-based structure with poor locality – by an array-based structure with high locality. • The research goal is to test this hypothesis. • The phenomenon that should be observed : as the number of items to be sorted is increased, the tree-based method should increasingly show a high rate of cache misses compared to the array-based method. • The data is the number of cache misses for several sets of items to be sorted
P-lists vs Q-list Suppose p-lists are a well-known data structure used for a range of applications, in particular as an in -memory search structure that is fast and compact A scientist has developed a new data structure called the Q-list Formal analysis has shown the two structures to have the same asymptotic complexity in both space and time but the scientist intuitively believes the Q -list to be superior in practice
P-lists vs Q-list • Suppose P-lists are a well-known data structure used for a range of applications, in particular as an in-memory search structure that is fast and compact. • A scientist has developed a new data structure called the Q-list. • Formal analysis has shown the two structures to have the same asymptotic complexity in both space and time, • but the scientist intuitively believes the Q-list to be superior in practice