tag:blogger.com,1999:blog-49671425484578937212018-01-17T17:45:28.628-08:00Learn AlgorithmAuthornoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-4967142548457893721.post-84498799973490017712018-01-04T16:09:00.002-08:002018-01-04T16:09:28.553-08:00Greedy Algorithms<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<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. <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.com1tag: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