COMPUTER SCIENCE Algorithms

COMPUTER SCIENCE

Algorithms

ALL CONTENT IN “ALGORITHMS”

Intro to algorithms

What are algorithms and why should you care? We'll start with an overview of algorithms and then discuss two games that you could use an algorithm to solve more efficiently - the number guessing game and a route-finding game.

• What is an algorithm and why should you care?(Video)
• A guessing game(Article)
• Route-finding(Article)
• Discuss: Algorithms in your life(Article)

Binary search

Learn about binary search, a way to efficiently search an array of items by halving the search space each time.

• Binary search(Article)
• Implementing binary search of an array(Article)
• Challenge: Binary search(Scratchpad)
• Running time of binary search(Article)
• Quiz: Running time of binary search(Exercise)

Asymptotic notation

Learn how to use asymptotic analysis to describe the efficiency of an algorithm, and how to use asymptotic notation (Big O, Big-Theta, and Big-Omega) to more precisely describe the efficiency.

• Asymptotic notation(Article)
• Big-θ (big-theta) notation(Article)
• Functions in asymptotic notation(Article)
• Quiz: Comparing function growth(Exercise)
• Big-O notation(Article)
• Big-Ω (big-omega) notation(Article)
• Quiz: Asymptotic notation(Exercise)

Selection sort

Learn selection sort, a simple algorithm for sorting an array of values, and see why it isn't the most efficient algorithm.

• Sorting(Article)
• Challenge: implement swap(Scratchpad)
• Selection sort pseudocode(Article)
• Challenge: Find minimum in subarray(Scratchpad)
• Challenge: implement selection sort(Scratchpad)
• Analysis of selection sort(Article)
• Project: Selection sort visualizer(Scratchpad)

Insertion sort

Learn insertion sort, another simple but not very efficient way to sort an array of values.

• Insertion sort(Article)
• Challenge: implement insert(Scratchpad)
• Insertion sort pseudocode(Article)
• Challenge: Implement insertion sort(Scratchpad)
• Analysis of insertion sort(Article)

Recursive algorithms

Learn the concept of recursion, a technique that is often used in algorithms. See how to use recursion to calculate factorial and powers of a number, plus to generate art.

• Recursion(Article)
• The factorial function(Article)
• Challenge: Iterative factorial(Scratchpad)
• Recursive factorial(Article)
• Challenge: Recursive factorial(Scratchpad)
• Properties of recursive algorithms(Article)
• Using recursion to determine whether a word is a palindrome(Article)
• Challenge: is a string a palindrome?(Scratchpad)
• Computing powers of a number(Article)
• Challenge: Recursive powers(Scratchpad)
• The Sierpinksi gasket(Article)
• Project: Recursive art(Scratchpad)

Towers of Hanoi

Use the recursive technique to solve the Towers of Hanoi, a classic mathematical puzzle and one reportedly faced by monks in a temple.

• Towers of Hanoi(Article)
• Move three disks in Towers of Hanoi(Exercise)
• Towers of Hanoi, continued(Article)
• Challenge: Solve Hanoi recursively(Scratchpad)

Merge sort

Learn merge sort, a more efficient sorting algorithm that relies heavily on the power of recursion to repeatedly sort and merge sub-arrays.

• Divide and conquer algorithms(Article)
• Overview of merge sort(Article)
• Challenge: Implement merge sort(Scratchpad)
• Linear-time merging(Article)
• Challenge: Implement merge(Scratchpad)
• Analysis of merge sort(Article)

Quick sort

Learn quick sort, another efficient sorting algorithm that uses recursion to more quickly sort an array of values.

• Overview of quicksort(Article)
• Challenge: Implement quicksort(Scratchpad)
• Linear-time partitioning(Article)
• Challenge: Implement partition(Scratchpad)
• Analysis of quicksort(Article)

Graph representation

Learn how to describe graphs, with their edges, vertices, and weights, and see different ways to store graph data, with edge lists, adjacency matrices, and adjacency lists.

• Describing graphs(Article)
• Quiz: Describing graphs(Exercise)
• Representing graphs(Article)
• Quiz: Representing graphs(Exercise)
• Challenge: Store a graph(Scratchpad)

Breadth-first search

Learn how to traverse a graph using breadth-first-search to find a particular node or to make sure you've visited all the notes, traversing one layer at a time.

• Breadth-first search and its uses(Article)
• The breadth-first search algorithm(Article)
• Challenge: Implement breadth-first search(Scratchpad)
• Analysis of breadth-first search(Article)

Further learning

Ideas of how you could continue your learning journey in algorithms.

• Where to go from here