Course Introduction
This course focuses on the fundamentals of computer algorithms, emphasizing methods useful in practice. We look into the algorithm analysis as a way to understand behavior of computer programs as a function of its input size. Using the big-O notation, we classify algorithms by their efficiency. We look into basic algorithm strategies and approaches to problem solving. Some of these approaches include the divide and conquer method, dynamic programming, and greedy programming paradigms. Sorting and searching algorithms are discussed in detail as they form part of a solution to a large number of problems solved using computers. We also provide an introduction to the graph theory and graph algorithms as they are also used in many computer-based applications today. We conclude the course with a look into a special class of problems called the NP-complete problems.
Unit 1: Introduction to Algorithms
This unit introduces what algorithms are and discusses their importance with the role that algorithms play compared to other technologies used in computers. We look into description of algorithms using pseudo-code and we use pseudo-code for algorithmic analysis. We will go through an introduction of algorithms using examples of sorting algorithms while discussing the importance of algorithm analysis in that context.
Completing this unit should take you approximately 5 hours.
Unit 2: Introduction to Analysis of Algorithms
In this unit, we explore how we can express an algorithm's efficiency as a function of its input size. The order of growth of running time of an algorithm gives a simple characterization of algorithm's efficiency and allows us to relate performance of alternative algorithms. Asymptotic analysis is based on the idea that as the problem size grows, the complexity will eventually settle down to a simple proportionality to some known function. This idea is incorporated in the "Big Oh", "Big Omega", and "Big Theta" notations for asymptotic performance. These notations are useful for expressing the complexity of an algorithm without getting lost in unnecessary detail.
Completing this unit should take you approximately 9 hours.
Unit 3: Divide and Conquer Method
In this unit, we will examine a popular technique called divide-and-conquer that is used in solving computer science problems. This technique solves the problem by breaking up the problem into smaller problems of same type and then recursively solving these smaller problems and combining their answers. We will also look into analysis of these algorithms through the use of recursion techniques.
Completing this unit should take you approximately 10 hours.
Unit 4: Sorting Algorithms
This unit introduces algorithms that sort real numbers. Algorithms often use sorting as a key subroutine. There is a wide variety of sorting algorithms, and they use a rich set of techniques. These algorithms have different runtime complexities and work better in certain conditions. Some of algorithms that we will study include Quick Sort, Insertion Sort, Bubble Sort, and Merge Sort.
Completing this unit should take you approximately 7 hours.
Unit 5: Dynamic Programming
In this unit, we will study another popular computer science algorithmic paradigm called the dynamic programming. Dynamic programming, like the divide-and-conquer method, solves problem by combining solutions to sub-problems. Dynamic programming typically applies to optimization problems in which a set of choices must be made in order to arrive at an optimal solution. It is effective when a given sub-problem may arise from more than one partial set of choices. We will look into problems, such as the longest common subsequence and the knapsack problem, to explain the key ideas behind dynamic programming.
Completing this unit should take you approximately 7 hours.
Unit 6: Graph Theory and Graph Algorithms
In this unit, you will learn about graph theory and graph-based algorithms. Graphs are a pervasive data structure in computer science and algorithms working with them are fundamental to the subject. We will review basic concepts of graph and associated terminology. We will also see how we can represent graphs in computer algorithms and use these representations to solve some common problems, such as finding the shortest paths between any two places. You will also get an introduction to trees and a minimum weight spanning tree algorithm.
Completing this unit should take you approximately 10 hours.
Unit 7: Greedy Algorithms
In this unit, we will look into a common computer science algorithm technique called the greedy algorithms. Like the dynamic programming paradigm, greedy algorithms typically apply to optimization problems in which a set of choices must be made in order to arrive at an optimal solution. The idea of greedy algorithm is to make each choice in a locally optimal manner. We will explore some common greedy algorithms in use today as a way of explaining the topic in this unit.
Completing this unit should take you approximately 7 hours.
Unit 8: NP-Completeness
In this last unit, we will study a special class of problems called the NP-complete problems. Many interesting computational problems are NP-complete, but there are no polynomial-time algorithms known for solving any of them. The unit presents techniques for determining when a problem is NP-complete.
Completing this unit should take you approximately 11 hours.
