4 deleted 1 character in body edited Jun 21 '15 at 20:17 Mahmoud Emam 2811 gold badge11 silver badge55 bronze badges How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? For example, consider the program below. You’re given a read only array of $$n$$ integers. Find out if any integer occurs more than $$n/3$$ times in the array in linear time and constant additional space. Algorithm: We will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with its proper count. If we reach the size of count array we decrement one from count of each number. If number count becomes zero it can be safely eliminated from the count array. Here is an example: Input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes count arr (3,1). We will proceed with next element in the array which is 2. count arr (3,1)(2,1) count arr (3,2)(2,1) and so on. At the end count arr will be (3,1)(5,1). We will make another loop to the input array to count concurrenceoccurrence of 3 and 5 and if any one exceeds $$n/3$$ it will be printed out. How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? For example, consider the program below. You’re given a read only array of $$n$$ integers. Find out if any integer occurs more than $$n/3$$ times in the array in linear time and constant additional space. Algorithm: We will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with its proper count. If we reach the size of count array we decrement one from count of each number. If number count becomes zero it can be safely eliminated from the count array. Here is an example: Input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes count arr (3,1). We will proceed with next element in the array which is 2. count arr (3,1)(2,1) count arr (3,2)(2,1) and so on. At the end count arr will be (3,1)(5,1). We will make another loop to the input array to count concurrence of 3 and 5 and if any one exceeds $$n/3$$ it will be printed out. How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? For example, consider the program below. You’re given a read only array of $$n$$ integers. Find out if any integer occurs more than $$n/3$$ times in the array in linear time and constant additional space. Algorithm: We will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with its proper count. If we reach the size of count array we decrement one from count of each number. If number count becomes zero it can be safely eliminated from the count array. Here is an example: Input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes count arr (3,1). We will proceed with next element in the array which is 2. count arr (3,1)(2,1) count arr (3,2)(2,1) and so on. At the end count arr will be (3,1)(5,1). We will make another loop to the input array to count occurrence of 3 and 5 and if any one exceeds $$n/3$$ it will be printed out. Post Closed as "too broad" by Yuval Filmus, hengxin, Ran G., D.W.♦, David Richerby occurred Jun 20 '15 at 7:55 3 added 40 characters in body edited Jun 20 '15 at 5:49 Yuval Filmus 208k1515 gold badges202202 silver badges369369 bronze badges How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? Edit: for For example, consider the program below problem You’re. You’re given a read only array of n$$n$$ integers. Find Find out if any integer occurs more than n/3$$n/3$$ times in the array in linear time and constant additional space. algorithm Algorithm: weWe will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with it'sits proper count. ifIf we reach the size of count array we decrementeddecrement one from count of each number if. If number count becomes zero it can be safely eliminated from the count array. here Here is an example: input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1) here we reach the max allowed size for count then we need to decremented count be one and if it reach zero it item will be removed from our count array so count arr becomes count arr (3,1) we will proceed with next element in the array which is 2 count arr (3,1)(2,1) count arr (3,2)(2,1) and so on at the end count arr will be (3,1)(5,1) we Input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes count arr (3,1). We will proceed with next element in the array which is 2. count arr (3,1)(2,1) count arr (3,2)(2,1) and so on. At the end count arr will be (3,1)(5,1). We will make another loop to the input array to count concurrence of 3 and 5 and if any one exceed n/3exceeds $$n/3$$ it will be printed out. How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? Edit: for example consider below problem You’re given a read only array of n integers. Find out if any integer occurs more than n/3 times in the array in linear time and constant additional space. algorithm: we will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with it's proper count. if we reach the size of count array we decremented one from count of each number if number count becomes zero it can be safely eliminated from the count array. here is an example: input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1) here we reach the max allowed size for count then we need to decremented count be one and if it reach zero it item will be removed from our count array so count arr becomes count arr (3,1) we will proceed with next element in the array which is 2 count arr (3,1)(2,1) count arr (3,2)(2,1) and so on at the end count arr will be (3,1)(5,1) we will make another loop to the input array count concurrence of 3 and 5 and if any one exceed n/3 it will be printed out. How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? For example, consider the program below. You’re given a read only array of $$n$$ integers. Find out if any integer occurs more than $$n/3$$ times in the array in linear time and constant additional space. Algorithm: We will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with its proper count. If we reach the size of count array we decrement one from count of each number. If number count becomes zero it can be safely eliminated from the count array. Here is an example: Input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes count arr (3,1). We will proceed with next element in the array which is 2. count arr (3,1)(2,1) count arr (3,2)(2,1) and so on. At the end count arr will be (3,1)(5,1). We will make another loop to the input array to count concurrence of 3 and 5 and if any one exceeds $$n/3$$ it will be printed out. 2 added 1162 characters in body edited Jun 20 '15 at 5:13 Mahmoud Emam 2811 gold badge11 silver badge55 bronze badges How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? Edit: for example consider below problem You’re given a read only array of n integers. Find out if any integer occurs more than n/3 times in the array in linear time and constant additional space. algorithm: we will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with it's proper count. if we reach the size of count array we decremented one from count of each number if number count becomes zero it can be safely eliminated from the count array. here is an example: input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1) here we reach the max allowed size for count then we need to decremented count be one and if it reach zero it item will be removed from our count array so count arr becomes count arr (3,1) we will proceed with next element in the array which is 2 count arr (3,1)(2,1) count arr (3,2)(2,1) and so on at the end count arr will be (3,1)(5,1) we will make another loop to the input array count concurrence of 3 and 5 and if any one exceed n/3 it will be printed out. How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true. but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases. So how can I prove mathematically if my algorithm produce the expected output or not ? Edit: for example consider below problem You’re given a read only array of n integers. Find out if any integer occurs more than n/3 times in the array in linear time and constant additional space. algorithm: we will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with it's proper count. if we reach the size of count array we decremented one from count of each number if number count becomes zero it can be safely eliminated from the count array. here is an example: input: 4 3 3 7 2 3 4 5 count arr (4,1) 4 as first element and 1 is its count till now count arr (4,1)(3,1) count arr (4,1)(3,2) count arr (4,1)(3,2)(7,1) here we reach the max allowed size for count then we need to decremented count be one and if it reach zero it item will be removed from our count array so count arr becomes count arr (3,1) we will proceed with next element in the array which is 2 count arr (3,1)(2,1) count arr (3,2)(2,1) and so on at the end count arr will be (3,1)(5,1) we will make another loop to the input array count concurrence of 3 and 5 and if any one exceed n/3 it will be printed out. 1 asked Jun 20 '15 at 2:33 Mahmoud Emam 2811 gold badge11 silver badge55 bronze badges