Taxonomy of Problem-Solving Techniques

Computer science is essentially the study of computational problems and how solve them using the minimal amount of resources. A computational problem is a specification of the relation between input and output. A solution to the problem is an executable algorithm that realizes that relation. That is, given a particular input to the algorithm (which is really an instance of the problem), the algorithm will process it and produces the required output(1). Sorting is a typical example of a computation problem. Some problems can be solved quite easily even by people who know very little about computer science, while others may require a tremendous amount of ingenuity and/or experience. Continue reading

Advertisements

Linear Search Time Complexity Analysis: Part 1

Linear search is one of the simplest algorithms. Consider an unsorted array A of size n. Given an element x, we would like to determine whether x exits in A or not. Linear search goes like this: search A for x in order by considering A[1], A[2], …, A[n] until either it finds A[i] = x or it reaches the end of the array which means that the element does not exist. Because the algorithm always starts at 1 and continue sequentially up to n, we call it deterministic. We don’t make any assumptions about whether A contains one or more equal copies of the same element. However, we assume that the elements of the array, whatever they are, are equally likely to appear in any order. Also we will consider only the number of comparisons that involves elements from A when computing the running time. Continue reading