tag:blogger.com,1999:blog-49671425484578937212018-08-09T02:15:58.232-07:00Learn AlgorithmAuthornoreply@blogger.comBlogger7125tag:blogger.com,1999:blog-4967142548457893721.post-19789035405005004892018-01-28T15:51:00.004-08:002018-01-28T15:56:05.474-08:00The Towers of Hanoi<div dir="ltr" style="text-align: left;" trbidi="on"><br /><div style="text-align: justify;">The Towers of Hanoi is an ancient puzzle consisting of a number of disks placed on three columns, the disks all have different diameters and holes in the middle so they will fit over the columns. All the disks start out on column A. The object of the puzzle is to transfer all the disks from column A to column C. Only one disk can be moved at a time, and no disk can be placed on a disk that’s smaller than itself. There’s an ancient myth that somewhere in India, in a remote temple, monks labor day and night to transfer 64 golden disks from one of three diamond-studded towers to another. When they are finished, the world will end. Any alarm you may feel, however, will be dispelled when you see how long it takes to solve the puzzle for far fewer than 64 disks. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-aup4A0TNdas/Wm5d-bRtEHI/AAAAAAAADFQ/_KGMxeePH1gdA5rBgecvBPvIkHRWChVUACLcBGAs/s1600/Screen%2BShot%2B2018-01-29%2Bat%2B12.33.34%2BAM.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-aup4A0TNdas/Wm5d-bRtEHI/AAAAAAAADFQ/_KGMxeePH1gdA5rBgecvBPvIkHRWChVUACLcBGAs/s400/Screen%2BShot%2B2018-01-29%2Bat%2B12.33.34%2BAM.png" /></a></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><b>Moving Subtrees</b> </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Let’s call the initial tree-shaped (or pyramid-shaped) arrangement of disks on tower A a tree. (This kind of tree has nothing to do with the trees that are data storage struc- tures) . Let’s call these smaller trees, containing fewer than the total number of disks, subtrees. For example, if you’re trying to transfer four disks, you’ll find that one of the intermediate steps involves a subtree of three disks on tower B,</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">These subtrees form many times in the solution of the puzzle. This happens because the creation of a subtree is the only way to transfer a larger disk from one tower to another: All the smaller disks must be placed on an intermediate tower, where they naturally form a subtree. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Here’s a rule of thumb that may help when you try to solve the puzzle manually. If the subtree you’re trying to move has an odd number of disks, start by moving the topmost disk directly to the tower where you want the subtree to go. If you’re trying to move a subtree with an even number of disks, start by moving the topmost disk to the intermediate tower. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><b>The Recursive Algorithm</b> </div><div style="text-align: justify;">The solution to the Towers of Hanoi puzzle can be expressed recursively using the notion of subtrees. Suppose you want to move all the disks from a source tower (call it S) to a destination tower (call it D). You have an intermediate tower available (call it I). Assume there are n disks on tower S. Here’s the algorithm: </div><div style="text-align: justify;"><br /></div><blockquote class="tr_bq" style="text-align: justify;">Move the subtree consisting of the top n-1 disks from S to I.<br />Move the remaining (largest) disk from S to D.<br />Move the subtree from I to D. </blockquote><div style="text-align: justify;"><br /></div><div style="text-align: justify;">When you begin, the source tower is A, the intermediate tower is B, and the destination tower is C. </div><div style="text-align: justify;">First, the subtree consisting of disks 1, 2, and 3 is moved to the intermediate tower B. Then the largest disk, 4, is moved to tower C. Then the subtree is moved from B to C. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Of course, this solution doesn’t solve the problem of how to move the subtree consisting of disks 1, 2, and 3 to tower B, because you can’t move a subtree all at once; you must move it one disk at a time. Moving the three-disk subtree is not so easy. However, it’s easier than moving four disks. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">As it turns out, moving three disks from A to the destination tower B can be done with the same three steps as moving four disks. That is, move the subtree consisting of the top two disks from tower A to intermediate tower C; then move disk 3 from A to B. Then move the subtree back from C to B. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">How do you move a subtree of two disks from A to C? Move the subtree consisting of only one disk (1) from A to B. This is the base case: When you’re moving only one disk, you just move it; there’s nothing else to do. Then move the larger disk (2) from A to C, and replace the subtree (disk 1) on it.</div><div style="text-align: justify;"><a href="https://3.bp.blogspot.com/-iJHSi296K7o/Wm5d-47gzVI/AAAAAAAADFU/2VuV16vUNX84TLHhsa73634QJTBioKSGgCLcBGAs/s1600/Screen%2BShot%2B2018-01-29%2Bat%2B12.33.47%2BAM.png"><img border="0" src="https://3.bp.blogspot.com/-iJHSi296K7o/Wm5d-47gzVI/AAAAAAAADFU/2VuV16vUNX84TLHhsa73634QJTBioKSGgCLcBGAs/s640/Screen%2BShot%2B2018-01-29%2Bat%2B12.33.47%2BAM.png" /></a></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><b>The towers.java Program </b></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The <b>towers.java</b> program solves the Towers of Hanoi puzzle using this recursive approach. It communicates the moves by displaying them; this approach requires much less code than displaying the towers. It’s up to the human reading the list to actually carry out the moves. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The code is simplicity itself. The main() routine makes a single call to the recursive method doTowers(). This method then calls itself recursively until the puzzle is solved. There are initially only three disks, but you can recompile the program with any number. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">// towers.java</div><div style="text-align: justify;">// solves the towers of Hanoi puzzle</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><blockquote class="tr_bq"><br /><br /><br />class TowersApp{<br /> static int nDisks = 3;<br /><br /> public static void main(String[] args) {<br /> doTowers(nDisks, ‘A’, ‘B’, ‘C’);<br /> } //-----------------------------------------------------------<br /> public static void doTowers(int topN, char from, char inter, char to){<br /><br /> if(topN==1)<br /><br /> System.out.println(“Disk 1 from “ + from + “ to “+ to);<br /> else{<br /> doTowers(topN-1, from, to, inter); // from-->inter<br /> System.out.println(“Disk “ + topN + “ from “ + from + “ to “+ to);<br /> doTowers(topN-1, inter, from, to); // inter-->to<br /> }<br /><br /> }<br />//----------------------------------------------------------<br />} // end class TowersApp </blockquote><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Remember that three disks are moved from A to C. Here’s the output from the program: </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Disk 1 from A to C</div><div style="text-align: justify;">Disk 2 from A to B </div><div style="text-align: justify;">Disk 1 from C to B </div><div style="text-align: justify;">Disk 3 from A to C </div><div style="text-align: justify;">Disk 1 from B to A </div><div style="text-align: justify;">Disk 2 from B to C </div><div style="text-align: justify;">Disk 1 from A to C </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The arguments to doTowers() are the number of disks to be moved, and the source (from), intermediate (inter), and destination (to) towers to be used. The number of disks decreases by 1 each time the method calls itself. The source, intermediate, and destination towers also change. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Here is the output with additional notations that show when the method is entered and when it returns, its arguments, and whether a disk is moved because it’s the base case (a subtree consisting of only one disk) or because it’s the remaining bottom disk after a subtree has been moved: </div><div style="text-align: justify;"><br /></div><blockquote class="tr_bq" style="text-align: justify;">Enter (3 disks): s=A, i=B, d=C Enter (2 disks): s=A, i=C, d=B<br />Enter (1 disk): s=A, i=B, d=C Base case: move disk 1 from<br />Return (1 disk)<br />Move bottom disk 2 from A to B Enter (1 disk): s=C, i=A, d=B<br />Base case: move disk 1 from Return (1 disk)<br />Return (2 disks)<br />Move bottom disk 3 from A to C Enter (2 disks): s=B, i=A, d=C<br />Enter (1 disk): s=B, i=C, d=A Base case: move disk 1 from<br />Return (1 disk)<br />Move bottom disk 2 from B to C Enter (1 disk): s=A, i=B, d=C<br />Base case: move disk 1 from Return (1 disk)<br />Return (2 disks) Return (3 disks) </blockquote><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">A to C </div><div style="text-align: justify;">C to B </div><div style="text-align: justify;">B to A </div><div style="text-align: justify;">A to C </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">If you study this output along with the source code for doTower(), it should become clear exactly how the method works. It’s amazing that such a small amount of code can solve such a seemingly complicated problem. </div><div style="text-align: justify;"><br /></div></div>Authornoreply@blogger.com0tag:blogger.com,1999:blog-4967142548457893721.post-84498799973490017712018-01-04T16:09:00.002-08:002018-07-07T11:24:37.374-07:00Greedy Algorithms Part 1<div dir="ltr" style="text-align: left;" trbidi="on">A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. Greedy algorithms works in phases, In each phase, a decision is made that appears to be good or the best at that point in time without regard for future consequences. Generally, this means that some local optimum is chosen (The best solution from a small subset of a larger dataset). This "take what you can get now" strategy is the source of the name for this class of algorithms. The local optimum may or may not be equal to the global optimum. If it is equal, then the greedy algorithm is the best approach to solving the problem. if the absolute best answer is not required, then simple greedy algorithms are sometimes used to generate approximate answers, rather than using the more complicated algorithms. Greedy algorithms mostly (but not always) fail to find the globally optimal solution, because they usually do not operate exhaustively on all the data, they can make commitments to certain choices too early which prevent them from finding the best overall solution later<br /><div><br /></div><div>There are lots of real life examples of greedy algorithms. One of the obvious is the coin changing problem, to make change in a certain currency, we repeatedly dispense the largest denomination, thus , to give out seventeen dollars and sixty one cents in change, we give out a ten-dollar bill, a five-dollar bill, two one-dollar bills, two quarters , one dime, and one penny. By doing this, we are guaranteed to minimize the number of bills and coins. This algorithm does not work in all monetary systems, but fortunately, we can prove that it does work in the American monetary system. Indeed, it works even if two-dollar bills and fifty-cent pieces are allowed.<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wLl40l3mk-Y/Wk7B_ddja0I/AAAAAAAADEE/o35FLoIXFF0Lh67TsQdDrA-xqvLsNYmpQCLcBGAs/s1600/greedy.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="200" data-original-width="300" src="https://1.bp.blogspot.com/-wLl40l3mk-Y/Wk7B_ddja0I/AAAAAAAADEE/o35FLoIXFF0Lh67TsQdDrA-xqvLsNYmpQCLcBGAs/s1600/greedy.jpg" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div>Another real life application of greedy algorithm is scheduling problem, virtually all scheduling problems are either NP-complete ( or of similar difficult complexity) or are solvable by a greedy algorithm.<br /><div><br /></div><div>All known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum. For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each stage visit an unvisited city nearest to the current city". This heuristic need not find a best solution, but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps. In mathematical optimization, greedy algorithms solve combinatorial problems having the properties of matroids.<br /><br /><br /><br /><br /><br /><br /><br /></div></div></div></div>Authornoreply@blogger.com0tag:blogger.com,1999:blog-4967142548457893721.post-90909027364806681142017-09-11T13:31:00.002-07:002017-09-11T13:34:49.600-07:00Abstract Data Types (ADTs)<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">ADT is a set of objects and operations, no where in an ADT’s definitions is there any mention of how the set of operations is implemented. Programmers who use collections only need to know how to instantiate and access data in some pre-determined manner, without concerns for the details of the collections implementations. In other words, from a user’s perspective, a collection is an abstraction, and for this reason, in computer science, some collections are referred to as abstract data types (ADTs). The user is only concern with learning its interface, or the set of operations its performs.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Object such as lists, sets and graphs along with their operations can be viewed as abstract data types. ADTs are basically data types that hides its implementation details. Any part of a program that needs to perform an operation on ADT can do so by merely changing the routines that performs the ADT operations. The program that use them (ADT) will not necessarily need to know which implementation was used<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://cdn.slidesharecdn.com/ss_thumbnails/lec-2abstractdatatype-140316022131-phpapp02-thumbnail-4.jpg?cb=1394936522" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="576" data-original-width="768" height="240" src="https://cdn.slidesharecdn.com/ss_thumbnails/lec-2abstractdatatype-140316022131-phpapp02-thumbnail-4.jpg?cb=1394936522" width="320" /></a></div><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Developers of collections(ADTs) are concerned with implementing all operations in the most efficient manner possible, with the goal of providing the best performance to usrs of ADTs. Numerous implementations are usually possible however, many of these takes much space and time that they can be dismissed as pointless.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">In computer science, we use abstraction as a technique for ignoring or hiding details that are , for the main moments non essential and we often build up a software system later by layer, with each layer treated as an abstraction by the layers above, that utilize it. Without abstractions, we would need to consider all aspects of a software system simultaneously</div><style type="text/css"> @page { margin: 2cm } p { margin-bottom: 0.25cm; line-height: 120% } </style></div>Authornoreply@blogger.com0tag:blogger.com,1999:blog-4967142548457893721.post-30698533434186783402017-08-30T12:20:00.001-07:002017-08-30T12:28:09.887-07:00Algorithm Analysis an intro<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: justify;">Once an algorithm is given for a problem and decided (somehow) to be correct, the next step is to determine how much in a way of resources , processes that run on real computers have finite resources, processes consume mainly two resources.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">- The processing time and </div><div style="text-align: justify;">- Space or Memory Use</div><br /><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-oECn5dWqzJc/WacO8HCf0lI/AAAAAAAACsE/i8pa3FwDlBkaKt6oUDXADN7knhIiuifmACLcBGAs/s1600/battle.gif" style="margin-left: auto; margin-right: auto;"><img border="0" height="213" src="https://1.bp.blogspot.com/-oECn5dWqzJc/WacO8HCf0lI/AAAAAAAACsE/i8pa3FwDlBkaKt6oUDXADN7knhIiuifmACLcBGAs/s320/battle.gif" width="320" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Space and Time Battle in the CPU</td></tr></tbody></table><br /><div style="text-align: justify;"><br /></div><div style="text-align: justify;">An algorithm that solves a problem but requires a year is hardly of any use. Likewise an algorithm that requires several gigabytes of main memory is not (currently, as at the time of this writing) useful on most machine, The method of determining the efficiency of algorithms that allows us to rate them independently of platform-dependent timing is called complexity analysis.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">When run with the same problem or data sets, processes that consumes less of the resources are of higher quality than processes that consume more, and so are the corresponding algorithms. Some algorithms consumes an amount of time or memory that is below threshold of tolerance, for example most users are happy with any algorithm that loads a file in less than one seconds.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">When choosing algorithms, we often have to settle for a space/time tradeoff, an algorithm can be designed to gain faster run times at the cost of using extra space (memory) , or the other way around. Some users might be wiling to pay for more memory to get a faster algorithm. Whereas others would rather settle for a slower algorithm that economize on memory.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">In any case, because efficiency is a desirable feature of algorithms, it is important to pay attention to the potential of some algorithms for poor performance. The computer and compiler used can’t do anything about these performance. The major factor to consider are the algorithm logic and the size of input</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">More Reading:</div><div style="text-align: justify;">Measuring the run time of an algorithm</div><div style="text-align: justify;">Measuring the memory used by an algorithm</div><div style="text-align: justify;">Complexity Analysis</div><div style="text-align: justify;">Big-O Notation/Order of Complexity</div><style type="text/css">p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px 'Helvetica Neue'; color: #454545} p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px 'Helvetica Neue'; color: #454545; min-height: 14.0px} </style></div>Authornoreply@blogger.com0tag:blogger.com,1999:blog-4967142548457893721.post-48224422911567931802017-07-22T17:55:00.007-07:002017-08-14T20:59:40.294-07:00Why Algorithm <div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: justify;">Problem solving is not all about getting the right result, writing an algorithm that solves a problem but requires a year is hardly of any use, likewise, an algorithm that requires several gigabytes go main memory is not (currently) useful on most machine. When solving a problem we need to consider several resources such as time and memory space before choosing the logic to use, this is where knowing the exact algorithm to use come in.</div><div style="text-align: justify;"><br /></div><div><div style="text-align: justify;">There have been several arguments on which to learn first, algorithms (and data structure) or programming languages or is there even a need to learn/study algorithm at all. This write up will cover why you should study algorithm and data structure .</div><div style="text-align: justify;"><br /></div></div><div><div style="text-align: justify;"><br /></div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: justify;"><tbody><tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-HLl6VeawiHk/WXPykrmJjbI/AAAAAAAACmw/fWlkQ2_Mz5IOub4BVEJVziUlMQ0xi1pVgCLcBGAs/s1600/image145%2B%25281%2529.jpg" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://4.bp.blogspot.com/-HLl6VeawiHk/WXPykrmJjbI/AAAAAAAACmw/fWlkQ2_Mz5IOub4BVEJVziUlMQ0xi1pVgCLcBGAs/s320/image145%2B%25281%2529.jpg" width="316" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Network connectivity problem:-</td></tr></tbody></table><div class="separator" style="clear: both; text-align: justify;"><br /></div><div style="text-align: justify;">“ Given a large set of items that are connected to another pair wise is there a way to get from one part to another. as you can see from the diagram above its not clear if there is a solution or not” </div></div><div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Most self learnt programmer jump straight into development without having the fundamental knowledge of how exactly some logic works. Programming is all about applying logic to solving problems. An algorithm represents your solution to a programming problem, algorithm which are methods for solving problems. While you may not implements some of the algorithm everyday, the knowledge will sharpen your approach to problem solving. Apart from learning algorithm for fundamentals , there are also tons of other reasons why you should study algorithms, the impact is very broad , far reaching and also helps in intellectual stimulations</div><div style="text-align: justify;"><br /></div><blockquote class="tr_bq" style="text-align: justify;">For me , great algorithm are the poetry of computation, just like verse, they can be terse, allusive, dense, and even mysterious . But once unlocked, they cast a brilliant new light on some aspect of computing -- Francis sullivan</blockquote><blockquote class="tr_bq" style="text-align: justify;">An algorithm must be seen to be believed -- Donald Knuth</blockquote><blockquote class="tr_bq" style="text-align: justify;">I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important . Bad programmers worry about the code. God programmers worry about data structures and their relationships -- Linus Torvalds ( Creator of Linux)</blockquote><blockquote class="tr_bq" style="text-align: justify;">Algorithms + Datat structures = Programs -- Niklaus Wirth</blockquote><div style="text-align: justify;"><br /></div><div style="text-align: justify;">There will often be limited resources when solving a problem so Writing the perfect and efficient login/solution to a problem requires the right set of data structure and algorithms, Because there are always several ways to solve a program , but not all the method are good and efficient. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">If you want to become a master programming, then learning how to write great algorithms is a must. You can start learning algorithms without prior knowledge of any programming language but to be able to implement them you would need to learn at least one programming language. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Here are few topics you should look into to become an algorithm expert </div><div style="text-align: justify;"><div>Data types: stack, queue, bag, union-find, priority queue</div><div>Sorting: sorting quicksort, mergesort, heapsort and radix sorts</div><div>Searching: Binary search tree, red-black tree, hash table</div><div>Graphs: Breath first search, DFS, prim, kruskal, Dijkstra</div><div>Strings: KMP, regular expression . TST, Huffman, LZW</div><div>Advance: B-tree, suffix array, maxflow</div><div><br /></div></div><div style="text-align: justify;">Recommended Books :</div><div style="text-align: justify;"><div><a href="https://www.wikiwand.com/en/The_Art_of_Computer_Programming">Donald Knuth’s The Art of Computer Programming</a></div><div>Algorithm Design Manuel</div></div><div style="text-align: justify;"><br /></div><style type="text/css">p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px 'Helvetica Neue'; color: #454545} p.p3 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px 'Helvetica Neue'; color: #454545; min-height: 14.0px} li.li1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px 'Helvetica Neue'; color: #454545} li.li2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Menlo; color: #454545} li.li4 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px 'Helvetica Neue'; color: #e4af0a} span.s1 {font: 10.0px Menlo} span.s2 {font: 10.0px Menlo; color: #454545} span.s3 {font: 12.0px 'Helvetica Neue'; text-decoration: underline ; color: #e4af0a} ul.ul1 {list-style-type: disc} </style></div></div>Authornoreply@blogger.com2tag:blogger.com,1999:blog-4967142548457893721.post-49698408749711908882016-01-27T18:05:00.001-08:002016-01-30T14:05:05.063-08:00The wonders of prime numbers<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: justify;">People often come across diverse prime number problems, such as Finding largest prime factor of a number or finding all primes between two values. A prime number is a whole number greater than 1 that can only be divisible by itself and 1. It is obvious that prime numbers are different from other numbers because of it several applications in the real world.<br /><br />Questions like this "find the ten digit prime number having highest number of fives in it" may throw you of course a bit, after seeing such questions you often wonder "How many prime number exist", "what is the fastest way to generate a continuous stream of prime numbers" etc.<br /><br />There have been several problems and several solutions on prime numbers. This part of mathematics is not a joke, Many questions regarding prime numbers remain open, such as Goldbach's conjecture (that every even integer greater than 2 can be expressed as the sum of two primes), and the twin prime conjecture (that there are infinitely many pairs of primes whose difference is 2). Such questions spurred the development of various branches of number theory, focusing on analytic or algebraic aspects of numbers. people have even studied just prime numbers as a profession, this is to show the extent at which its relevant.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-gSljhOIUAkY/Vql4UmESSKI/AAAAAAAACBc/BLM8Tel_Jhc/s1600/prime%2Bnumber%2Bchart%2BII.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="298" src="http://4.bp.blogspot.com/-gSljhOIUAkY/Vql4UmESSKI/AAAAAAAACBc/BLM8Tel_Jhc/s320/prime%2Bnumber%2Bchart%2BII.jpg" width="320" /></a></div><br /><br />The applications of prime numbers in computing can not be quantified, from cryptography to various generalizations functions. As a computer scientist the deep knowledge of prime number will be required when working on project such as encryption, special generators functions etc. If you are a computer scientist or programmer without fundamental knowledge of prime numbers, then you should go and study a book on it after this post.<br /><br />Here is one of the provoking problems you will encounter, "The product of a 3 digit palindrome and 13379872 is an exciting 10 digit number, which is also a palindrome. one less than this number is the product of 5 and 6 digit prime numbers. find the palindrome and the prime factors". you should give it a try.<br /><br />Note:<br /><br /><ul><li>2(Two) is the only even prime number</li><li>when testing if a number n is prime, only divide to square root of n</li></ul>Subsequent post will discuss on several methods of generating prime numbers<br />For programming problems on prime numbers check <a href="https://projecteuler.net/archives">https://projecteuler.net/archives</a></div></div>Authornoreply@blogger.com0tag:blogger.com,1999:blog-4967142548457893721.post-18803891024063699302016-01-26T14:09:00.001-08:002017-07-09T14:52:27.700-07:00Mathematics and Programming<div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">People Have wondered if good knowledge in mathematics is required to be a proficient programmer or software developer, depending on who you ask the question you will either get a Yes or a No as an answer.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">The questions may not necessarily be a 'yes' or 'No' answer, it more of knowing the focus of the person involved. learning a programming language such as Java, python, c++, c#, php, ruby obviously does not require a mathematical background or knowledge. The more a person programs in a language the more proficient the person becomes, so there is no really any required mathematical skills. But being a software engineer or programmer is not just all about writing programming in a literal sense ( writing of codes ), you may need some basic mathematical skills in approaching a solution faster or getting a more optimizes solution.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-96Dg2aGSUfc/VqgN5t8PT0I/AAAAAAAACBI/FSfc5xkJHKs/s1600/mathcsc.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="266" src="https://1.bp.blogspot.com/-96Dg2aGSUfc/VqgN5t8PT0I/AAAAAAAACBI/FSfc5xkJHKs/s400/mathcsc.jpg" width="400" /></a></div><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Computer science is entirely different from programming, Although programming is a core part of computer science, most people outside the field or new to the field often think it is the same or that programming is the only thing in computer science. computer science deals with the science of computer, every thing about it, from bit manipulation, architecture, operating system to huge data structure. Mathematics is a core and very important part of computer science, and its relevant and indispensable for all computer science student. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Several algorithms used by programming languages and the ones used by the computer are core mathematical solutions, Mathematics is widely used in computer science research, as well as being heavily applied to graph algorithms and areas of computer vision. several topics were adopted from mathematics to computer science. Random number generator and shortest part algorithm are obvious examples of solutions derived from mathematics. Some of the early stage contributor to computer science algorithm were mathematicians although with core computer science background. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Examples of such people includes Edsger Wybe Dijkstra (professor of mathematics and computer scientist, One of the most influential perform in computer science. His fundamental contributions cover diverse areas of computing science, including compiler construction, operating systems, distributed systems, sequential and concurrent programming, programming paradigm and methodology, programming language research, program design, program development, program verification, software engineering ), Donald Ervin Knuth ( American computer scientist, mathematician, and professor emeritus. Author of The Art of Computer Programming. Knuth has been called the father of the analysis of algorithms). </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Its obvious now that a person can not be a proficient computer scientist without good knowledge of mathematics . Overall, for just programming, mathematics may not be required but for other areas of computer science mathematics is a must. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Some list of mathematics for computer science resources</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/"><span style="color: blue;">MIT Mathematics for computer science</span></a></div><div style="text-align: justify;"><span style="color: blue;"><a href="https://projecteuler.net/"><span style="color: blue;">Project Euler programming</span></a> </span></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div></div>Authornoreply@blogger.com1