If you're seeing this message, it means we're having trouble loading external resources on our website.
If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.
To log in and use all the features of Khan Academy, please enable JavaScript in your browser.
Unit 1: Algorithms
About this unit, intro to algorithms.
- What is an algorithm and why should you care? (Opens a modal)
- A guessing game (Opens a modal)
- Route-finding (Opens a modal)
- Discuss: Algorithms in your life (Opens a modal)
Binary search
- Binary search (Opens a modal)
- Implementing binary search of an array (Opens a modal)
- Challenge: Binary search (Opens a modal)
- Running time of binary search (Opens a modal)
- Running time of binary search 5 questions Practice
Asymptotic notation
- Asymptotic notation (Opens a modal)
- Big-θ (Big-Theta) notation (Opens a modal)
- Functions in asymptotic notation (Opens a modal)
- Big-O notation (Opens a modal)
- Big-Ω (Big-Omega) notation (Opens a modal)
- Comparing function growth 4 questions Practice
- Asymptotic notation 5 questions Practice
Selection sort
- Sorting (Opens a modal)
- Challenge: implement swap (Opens a modal)
- Selection sort pseudocode (Opens a modal)
- Challenge: Find minimum in subarray (Opens a modal)
- Challenge: implement selection sort (Opens a modal)
- Analysis of selection sort (Opens a modal)
- Project: Selection sort visualizer (Opens a modal)
Insertion sort
- Insertion sort (Opens a modal)
- Challenge: implement insert (Opens a modal)
- Insertion sort pseudocode (Opens a modal)
- Challenge: Implement insertion sort (Opens a modal)
- Analysis of insertion sort (Opens a modal)
Recursive algorithms
- Recursion (Opens a modal)
- The factorial function (Opens a modal)
- Challenge: Iterative factorial (Opens a modal)
- Recursive factorial (Opens a modal)
- Challenge: Recursive factorial (Opens a modal)
- Properties of recursive algorithms (Opens a modal)
- Using recursion to determine whether a word is a palindrome (Opens a modal)
- Challenge: is a string a palindrome? (Opens a modal)
- Computing powers of a number (Opens a modal)
- Challenge: Recursive powers (Opens a modal)
- Multiple recursion with the Sierpinski gasket (Opens a modal)
- Improving efficiency of recursive functions (Opens a modal)
- Project: Recursive art (Opens a modal)
Towers of Hanoi
- Towers of Hanoi (Opens a modal)
- Towers of Hanoi, continued (Opens a modal)
- Challenge: Solve Hanoi recursively (Opens a modal)
- Move three disks in Towers of Hanoi 3 questions Practice
- Divide and conquer algorithms (Opens a modal)
- Overview of merge sort (Opens a modal)
- Challenge: Implement merge sort (Opens a modal)
- Linear-time merging (Opens a modal)
- Challenge: Implement merge (Opens a modal)
- Analysis of merge sort (Opens a modal)
- Overview of quicksort (Opens a modal)
- Challenge: Implement quicksort (Opens a modal)
- Linear-time partitioning (Opens a modal)
- Challenge: Implement partition (Opens a modal)
- Analysis of quicksort (Opens a modal)
Graph representation
- Describing graphs (Opens a modal)
- Representing graphs (Opens a modal)
- Challenge: Store a graph (Opens a modal)
- Describing graphs 6 questions Practice
- Representing graphs 5 questions Practice
Breadth-first search
- Breadth-first search and its uses (Opens a modal)
- The breadth-first search algorithm (Opens a modal)
- Challenge: Implement breadth-first search (Opens a modal)
- Analysis of breadth-first search (Opens a modal)
Further learning
- Where to go from here (Opens a modal)
Browse Course Material
Course info.
- Prof. John Guttag
Departments
- Electrical Engineering and Computer Science
As Taught In
- Computer Science
Introduction to Computer Science and Programming
Lecture 3: problem solving.
- Download video
- Download transcript
You are leaving MIT OpenCourseWare
Students create programs with different kinds of loops, events, functions, and conditions and write algorithms for everyday tasks. Through this they will investigate different problem-solving techniques, discuss societal impacts of computing and the Internet, and learn about Internet transmission methods. By the end of the curriculum, students create interactive stories and games they can share with anyone. Students taking Course 3 will have already taken Course 2.
Lesson Sequence of Course 3
Online lessons are in regular text and unplugged activities are in bolded text.
2.2 Computer Science Fundamentals
Wrap your mind around computational thinking, from everyday tasks to algorithms.
Making Decisions
Computers use decision trees to turn many simple decisions into one big decision.
Searching for Solutions
Sometimes, the right way to solve a computational problem is by “brute force.”
- Parallelism
When Pierre the baker wants to get lots of things done, it helps to do many things at once.
End of Unit 1
Complete all lessons above to reach this milestone.
0 of 3 lessons complete
Resource Tradeoffs
Computer scientists deal with tradeoffs all the time. So does Farhad when he does his chores.
Order and Search
Information needs to be organized for use by humans or computers, as Tiye the librarian knows well.
Computer systems and people need to be able to reliably find and access people and resources.
Abstraction
Mayor Jing uses abstraction—a critical tool in computer science—to help her run City Hall.
Abstractions have interfaces that explain what they can and cannot do.
End of Unit 2
0 of 5 lessons complete
Algorithms and Implementations
Algorithms are step-by-step processes for achieving an outcome. They can be very specific or quite general.
Divide and Conquer
Problems often get easier when you split them in half, as the 20 Questions guessing game shows.
- Binary Search
Binary search is a more algorithm-friendly version of the 20 Questions game.
Thinking with Graphs
Graphs are a powerful tool for understanding problems and solving them in clever ways.
Representing Games and Puzzles
Graphs can help us plan solutions to complex problems, like this classic river-crossing puzzle.
Graph Search
Some of the most fundamental algorithms on graphs are designed to get you from point A to point B.
End of Unit 3
0 of 6 lessons complete
Course description
Learn the key ideas of computer science with this interactive course – no coding required! This course is ideal for a high school or college student who wants to learn the fundamentals, or an early professional who wants to strengthen their knowledge of core computer science concepts. Whether you're exploring computer science for the first time or looking to deepen your understanding, this course will allow you to develop the problem-solving techniques you need to think like a computer scientist. Follow librarians, cooks, and mayors to see how computer science problem solving techniques affect their daily lives. Get hands-on with a few specific algorithms, and learn the general principles demonstrated by these algorithms.
Topics covered
- Brute-Force Search
- Concurrency
- Decision Trees
- Graph Abstractions
- Greedy Algorithms
- Programming
Prerequisites and next steps
You don’t need any previous computer science experience to take this course! This course is for anyone excited to actively learn more about how computer scientists think and understand our world.
3.1 Next Steps in Python
Boost your proficiency in Python by learning how to access social media data with public functions.
IMAGES
VIDEO
COMMENTS
Problem Solving and Computing - Lesson 3 Name(s)_____ Period _____ Date _____ Activity Guide - Using the Problem Solving Process Word Search Overview Working with a ...
Exploring Computer Science teaches the creative, collaborative, interdisciplinary, and problem-solving nature of computing with instructional materials that feature an inquiry-based approach to learning and teaching. As part of this course, students will delve into real world
Problem Solving and Computing Aluminum foil, container for water, pennies (note that pennies can be replaced with some other kind of weight of the same size). Alternate activities are available if you do not have access to these supplies. Creating Apps with Devices (Option A and Option B) Option A: Classroom set of Circuit Playgrounds.
Introduction. In order for students to become “computational thinkers” they need experience solving a wide range of problems and the opportunity to experiment with a variety of solution strategies. This unit begins with an introduction to the problem solving process. Students are asked to solve new problems by planning a strategy, designing ...
Preview. Computational Thinking. A method of problem-solving that helps computer scientists prepare problems for digital solutions. Abstraction. Removing details from a solution so that it can work for many problems. Decompose. To break a hard problem up into smaller, easier ones. Pattern. A theme that is repeated many times.
1.a - Apply existing knowledge to generate new ideas, products, or processes. 1.c - Use models and simulation to explore complex systems and issues. 2.d - Contribute to project teams to solve problems. 4.b - Plan and manage activities to develop a solution or complete a project.
Learn. We've partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn with a combination of articles, visualizations, quizzes, and coding challenges.
Please be advised that external sites may have terms and conditions, including license rights, that differ from ours. MIT OCW is not responsible for any content on third party sites, nor does a link suggest an endorsement of those sites and/or their content.
Lesson Sequence of Course 3. Online lessons are in regular text and unplugged activities are in bolded text. Students use the steps of computational thinking (decompose, pattern match, abstract, algorithm) to figure out how to play a game that comes with no instructions. Students write programs (an algorithm for the computer) that get a ...
Whether you're exploring computer science for the first time or looking to deepen your understanding, this course will allow you to develop the problem-solving techniques you need to think like a computer scientist. Follow librarians, cooks, and mayors to see how computer science problem solving techniques affect their daily lives.