Competitive programming problems are generally divided into a number of categories, each requiring a different skill set, algorithm, or data structure to solve. One subdivision of programming problem topics includes problems which are best solved using what’s known as a “greedy approach”.
A greedy algorithm makes locally optimal decisions, which hopefully produce a globally optimal solution. Furthermore, a greedy algorithm does not revisit a previously-made decision. These characteristics make greedy algorithms easy-to-code, straightforward, and efficient / fast. However, coming up with a greedy solution to a problem typically involves more algorithmic thinking; the difficulty in implementing a greedy approach lies in proving that it will work.
One commonly-used example is the coin change problem. Suppose you have an infinite supply of coins with values of 1, 5, 10, 25, 50, and 100. Now suppose that you must combine a number of your coins such that the values add up to a certain total, and you must do so with the fewest number of coins possible. How would you solve this problem?
The easiest approach is using a greedy algorithm. Let’s say the total you must achieve is 64. A greedy approach would keep a running total, starting at 0. For each iteration, it would determine the highest coin value which would not cause the total to exceed 64 - in this case, 50. Finally, it would add this value to the total, then repeat. In this case, the algorithm would produce the best solution: 50 + 10 + 1 + 1 + 1 + 1 = 64.
Let’s look at another coinage system. Suppose you now have an infinite supply of coins with values of 1, 7, 12, and 33, and you again must combine a number of your coins to add up to a certain total with the fewest number of coins possible. Would a greedy approach work in this case?
Let’s test it, using the value 36. The algorithm starts off with 0. The highest coin value which would not cause the total to exceed 36 is 33. Adding 33 to 0, it now has a running total of 33. During the next iteration, it discovers that it can only add coins of value 1, since any other value would cause the running total to exceed 36. The solution produced by the greedy algorithm is 33 + 1 + 1 + 1 = 36. The optimal solution is 12 + 12 + 12.
Turns out, a greedy approach works only for certain coinage systems (termed “canonical”). For other coinage systems, the solution is a bit more complicated.
Like other competitive programming techniques, greedy algorithms are applicable only in certain situations. Still, it’s important to master them, since problems solvable using these approaches are relatively common in competitions. For more information as well as practice problems, visit any of a number of programming websites (GeeksForGeeks, CodeChef, etc.)
Applications are open for scholarships to Apple's annual developer's conference! Submissions are due March 24, 2019. To apply, create an interactive Xcode Playground and answer several questions. Apple will likely select ~300 from thousands, based off of numbers from previous years, and will provide these developers with a free ticket to WWDC. Scholarship winners will have the opportunity to meet new people, learn new things, and explore Apple's upcoming technologies. Past winners have had the chance to meet Tim Cook and Michelle Obama. Don't delay; submit your project today!
Cognitive science is the study of thought, learning, and organization. The field of cognitive science works to answer difficult questions about the nature of thought, intelligence, and other parts of our mental lives. Additionally, it draws on many other science fields such as psychology, AI, and philosophy. A degree in cognitive science can lead to a variety of careers: artificial intelligence, business, healthcare, etc. The field was first created in the 1950s when scientists began to create theories about how the mind works. These scientists came up with the idea that computation would be a common language used around the world. Today, this growing field works to build cognitive models that imitate the thought processes of humans. The theoretical component of AI is cognitive science, since it maps out and understands how the human mind works. Scientists working in cognitive robotics are trying to create robots that can complete open-ended tasks and solve various problems. When AI researchers and cognitive scientists collaborate, they can create robots similar to those in science-fiction movies.
Competitive programming problems are generally divided into a number categories, each requiring a different skill set, algorithm, or data structure to solve. One subdivision of programming problem topics contains problems for which there exists no general technique or algorithm, i.e. no well-studied solution. These are known as ad-hoc problems.
Each ad-hoc problem is unique, and requires a specialized approach. Some competitive programmers consider ad-hoc problems to be the easiest type of problem. In reality, ad-hoc problems can be easy or hard! For beginners just starting to code competitively, it may be useful to practice lots of these problems.
Here is a good source of ad-hoc problems to practice with: codechef.com/tags/problems/ad-hoc. For each problem, first try to "pseudocode" (planning your solution on paper in non-code words) and solve independently. If you find yourself stuck on a problem for longer than several hours, it may be helpful to consult the solution in order to thoroughly understand the general approach, then code it yourself without checking the solution.
Photo Credit: Sportradar
From behind the scenes, technology is one of the main factors that makes sports so exciting. The power of machine learning and artificial intelligence can help expand the potential of professional athletes by recording and analyzing infinite details at a quicker speed than any sports scientist or analyst could. For example, cameras, videos, and sensors can be applied to the body or equipment and collect an enormous quantity of valuable information. On top of boosting an athlete’s craft, artificial intelligence also can improve the business side to the sport industry, such as a team’s ticket sales, sponsorships, and merchandising.
The predictive capabilities of machine learning allow for coaches to make more informed decisions that are based on a multi-level analysis of several factors. Using this technology, teams no longer need to wonder if they might miss the next shot; they can now anticipate errors and plan accordingly by working on specific plays in practice or changing their game strategy. In addition, while it is impossible for humans to see a play from every angle, machines can do just that to help coaches get a better understanding of that moment.
Though machine learning can tell any coach what the best decision for every situation is by the numbers, human intuition may be a critical missing part of this verdict. There is a difference between what has statistically worked well and what is needed to be successful in a given moment. The instincts, the creativity, and the risk-taking traits of a human are all crucial elements in a sport that artificial intelligence cannot fully replace, especially in team sports.
That being said, there are countless examples of companies in the sports industry who are utilizing various forms of artificial intelligence to enhance player performance. Arccos Caddie, for instance, is golf’s first AI-powered platform that enables the players to walk the course with their own virtual caddie, which can assist in decisions like what direction to hit and what club to use based on the course location, weather, and player ability. Outside of just professional athletes, fitness fans can also see AI incorporated with their nutrition and workouts through the app Talk Human to Me. This app can provide users with an automated workout “buddy” to support users during their workouts with expertise and encouragement. The list goes on and on for the possible applications of artificial intelligence in the incredible world of sports.
Sports open the door to some of the greatest human achievements, and it is fascinating to see the relationship between artificial intelligence and athletic performance. As team owners and coaches continue to strive for a better understanding of data and trends to improve their winning chances, the emerging field of AI is one of the key ways to stay ahead of the rest of the competition. Machine learning algorithms will only continue to evolve more rapidly within the next few years, and the most exciting part will be to see to what extent artificial intelligence will drive human actions and performance on the sports field.
Photo Credit: Shutterstock
Back in November 2017, Facebook announced that it was using artificial intelligence to help
flag suicidal users. The tech was used to identify posts, videos and live streams that could be
indicative of suicidal thoughts. The algorithm also prioritises the order in which the
Facebook team reviews these posts. According to Facebook, these accelerated reports get
reported to local authorities twice as fast as unaccelerated ones – which could save many
Recently, the Canadian government has also announced its use of AI to help prevent
suicides in the nation. It partnered with Advanced Symbolics, an AI firm, which will research
and predict suicide rates by analysing Canadian social media posts. The firm aims to predict
which areas of Canada could see an increase in suicidal behaviour, after which the
government can plan and provide mental health resources, in the right places, at the right
“To help prevent suicide, develop effective prevention programs and recognize ways to
intervene earlier, we must first understand the various patterns and characteristics of
suicide-related behaviours"; a Public Health Agency of Canada spokesperson said to CBC in a statement. "PHAC is exploring ways to pilot a new approach to assist in identifying patterns,
based on online data, associated with users who discuss suicide-related behaviours.”
AI has tremendous potential in the field of suicide prevention as many people that need
help go unnoticed by others. However, there are potential issues that must be taken care of:
1. Safety concerns as AI programs must learn to respond appropriately so as to not worsen
suicidal users’ emotional states.
2. Privacy concerns regarding users’ health information.
3. The accuracy of the AIs in determining suicide intent, to list a few.
Nonetheless, small steps, like those being taken by Facebook and the Canadian government,
will provide valuable insights to improve and advance AI technology.
For our younger audiences, we have an awesome opportunity from ThinkSteam. Enter their global thinkBIG challenge. If you're a girl aged 8-14, you could win an iPad Mini or iPad Pro, among other prizes! Make a 1-4 minute video on the importance of STEM or STEAM (Science, Technology, Engineering, Art, and Math). Teams can range from 1-3 members, with two divisions, open until August 15th. To learn more about how to enter, read the full rules, and see past winners, visit: http://www.thinksteam4girls.org/tbc18/. We hope our elementary school and middle school readers will take advantage of this cool opportunity.
Photo credit: Dubai News Gate
Artificial intelligence is becoming prevalent in various aspects of everyday life. Its various applications are starting to show in fashion and clothing. In fact, according to the MIT Technology Review, Ministry of Supply, a Boston-based clothing company has launched a jacket that incorporates AI. The jacket syncs with Alexa, is controlled by an app and customizes its temperature using machine learning. The jacket is not perfect; there are some connectivity issues, although many of these kinks are being worked out.
Aside from being used in clothes, artificial intelligence is helping with fashion choices. The Verge explains that Amazon has an algorithm that analyzes pictures to design clothing. It helps Amazon to quickly realize a trend and design clothes based on the trends. Additionally, another article from the MIT Technology Review finds that researchers from the University of California, San Diego and Adobe have found a way for AI to learn about a person’s specific fashion style and generate outfits to suit that style. This could help consumers make clothing choices and help retailers decide what clothing to sell.
MIT Technology Review
MIT Technology Review
Pictured: Joy Buolamwini, graduate researcher at MIT Media Lab’s Civic Media Group
Image: Bryce Vickmark
Joy Buolamwini is an graduate researcher at MIT Media Lab and is also the founder of Algorithmic Justice League - an organisation which solves biases in decision-making software. As a computer science undergraduate, Buolamwini worked on a robot which used computer vision to socially interact with humans. She realized that the robot was not able to identify her compared to other light-skinned humans. At the time, Buolamwini thought that people would fix this issue.
But this issue did not get solved. Her anecdote is one of many, including when Google’s facial recognition tagged two black friends as gorillas, when HP’s webcams easily tracked a white face but were unable to track a black one or when Nikon’s cameras continually told at least one Asian user that their eyes were closed. Although this may seem simple, as so many facial recognition softwares struggle with non-white faces, it reminds non-white people that facial recognition is not for them.
According to a study released by researchers at Stanford University and MIT, three commercially released facial recognition softwares from three major tech companies all have gender and skin type bias. In these experiments, the percent error when determining gender of light-skinned males was never larger than 0.8%. However, once determining gender of dark-skinned women, percent error jumped to 20% in one software and over 34% in the other two. These findings raise questions about what kind of data that these neural networks are trained on. After all, the accuracy of a neural network is based upon the variety of data that is provided to it. Although the accuracy of certain softwares was 97%, the data tested was more than 77% male and 83% white.
When companies think about error, they typically look at the statistics. If a program is right 97% of the time, the program is probably accurate enough. But most companies fail to see if the system is making the error randomly over a wide distribution, or only makes mistakes with a certain group of people. So, even if a system is right 95% of the time, it may be wrong with all Asian people in the United States. Or, if a system is correct 99% of the time, it may only make errors with all transgender people in the United States.
But how does one solve this problem? The first step is awareness. Companies must be made aware of the fact that their algorithms and programs need a more diverse data set in order to curb the bias that many programs face. Joy Buolamwini and her partner, Timnit Gebru, hope that their research paper will spur more work into looking at gender and racial disparities in other fields of computer science.
Interested in starting an AI club at your school?
At Allgirlithm, we are developing an AI club curriculum to help make AI education more accessible to middle and high school students in diverse communities. We understand that artificial intelligence is not a typical subject to be taught in school, but we want to change that. Our goal for launching the Allgirlithm Initiative Program is not only to teach students the fundamentals of AI, but also to spark interest, promote diversity, and break stereotypes in this emerging field.
The club lasts for a total of 10 weeks, with students learning 1-2 concepts per meeting. Several topics and subcategories covered include introduction to machine learning, supervised vs. unsupervised learning, clustering algorithms, neural networks, future implications of AI, computer vision, natural language processing, autonomous systems, expert systems, etc. Along with lectures, we will also provide you with links to instructional videos, AI demonstrations, AI/CS-related opportunities, and more. If you are interested in starting your own chapter or know anyone who may be interested, please fill out this form. All curriculum materials provided are free, and we will send them to you in the fall so that you can launch your own AI club for the 2018-2019 school year. Feel free to contact us at firstname.lastname@example.org with any questions.