This website houses notes from my studies at the University of Liverpool. If you see any errors or issues, please do open an issue on this site's GitHub.
For a normal case of mathematical induction you can prove that a statement holds for all numbers from a particular start point. It uses a base case so show that it holds for an individual number and an induction rule that proves that it holds for all numbers following. Prove...
Using induction to show that a program is correct. Example on a Recursive Function that Generates Factorials Proof By mathematical induction on $n$. Base Case $n=1$ \(g(1)=1=1!\) Inductive Step Suppose that for some $n=m, g(n)=n!$ Consider $n=m+1$ $g(m+1)$ the code returns $g(m)\times(m+1)$ By induction hypothesis, $g(m)=m!$ So: \(g(m)\times(m+1)=m!\times(m+1)=(m+1)!\)
Mutual and Multiple Recursion Mutual Recursion Mutual recursion is when two functions call each other: even' 0 = True even' n = odd' (n-1) odd' 0 = False odd' n = even' (n-1) We have to make sure that: We terminate in a base case. We always make progress towards...
Recursion with Multiple Lists Sometimes we want to use recursion on more than one list at a time. The following example adds the elements of two lists together: add_lists _ [] = [] add_lists [] _ = [] addlists (x:xs) (y:ys) = x + y : addlists xs ys Base...
where Syntax Sometimes it is useful to bind names across a whole function: remove_twos [] = [] remove_twos (x:xs) | x == 2 = rest | otherwise = x:rest where rest = remove_twos xs As the two expressions are in different guards then you can’t use a let expression. A...
It was made in 1968 in Stanford by the team that constructed Shaky, the robot. The basic idea was to combine uniform cost search and greedy search We look at the cost so far and the estimated cost to goal Thus we use the heuristic $f:$ \(f(s_0\ldots s_k)=g(s_0\ldots s_k)+ h(s_k)\)...
They are used to check conjectures about outcomes of processes that occur repeatedly and according to definite patterns. In general, mathematical induction is a method for proving that a property defined for integers $n$ is true for all values of $n$ that are greater than or equal to come initial...
Two Classic Results These are classical proofs as they we’re proven by the Ancient Greeks. They are both proofs by contradiction. Use proof by contradiction to show that there is no greatest prime number. 2, as the smallest prime number, is known as $P_1$. All following prime numbers are numbered...
Use problem-specific knowledge to make the search more efficient. Based on your knowledge, select the most promising path first. Rather than trying all possible search paths, you try to focus on paths that get you nearer to the goal state according to your estimate. Heuristics They estimate the oct of...
Basic problem solving techniques such as BFS and DFS are either incomplete, in the case of DFS or computationally expensive. You can make some tweaks to generate other uniform cost search algorithms or add more information to give an informed search algorithm. Either of these are an improvement Uniform cost...