Module two: February 5th- February 20th

Analysis of Algorithms

Welcome to Module 2! This Module we will be introducing Asymptotic Notations, Master's Theorem for analyzing running time of the algorithm. We will study about the growth of functions and the correctness of algorithms using proofs. Explore the tabs further below to view the Module's videos, find the Module's readings and complete the Module's activities.

Topics:

Topic 1:Asymptotic Notations

Topic 2:Master's Theorem

Topic 3:Proof of Correctness

Download the Module reader to get lecture slides, important concepts and relevant excerpts in one document

Module 1 Checklist

Get Oriented
- Review the course syllabus for information on assignments, due dates, and course expectations.
- Watch the course introduction video.
- Join us on Monday, January 20th, at 9:30 am EST for a Orientation. We'll review the course navigation, meet the class, and answer any questions. If you aren't able to attend, the session will be recorded and posted on the course site.
- Join from PC, Mac, Linux, iOS or Android: meeting link.... (Links to an external site.)

Watch lecture videos within each tab
- Lecture 1: Introduction to Algorithms – 11:01
- Lecture 2: Types of Algorithms – 15:21
- Lecture 3: Solved Examples – 6:49

Read textbook chapters and article
- Read Chapters 1, 2, 3, 4, and 5 from ........

Earn extra credit by solving Hacker Rank Challenge question of Week
- Click on Coin Change Question link
- Test your solution against all the test cases and upload the final result in the form of pdf file to Hacker Rank Assignment section under Assignments

Submit Assignment #1
- Assignment #1 is due on 1/27, 11:59 pm EST.
- Participate in the Open discussion Q&A forums, attend office hours or this week's Live TA sessions if you have questions about this upcoming assignment.

Optional
Watch optional videos under each Topic Tab to further strengthen your understanding of the topic
Solve practice questions topic wise provided under respective Topic Tab or general questions under Resources Tab

Topic 1: Asymptotic Notations

Topic 1 will cover following concepts:

1. Big O Notation
2. Big Omega Notation
3. Big Theta Notation
4. Application of Asymptotic Notation
5. Growth of functions

Topic 2: Master Theorem: Estimating Time complexity for recursive trees

Video 2 will cover following concepts:

1.No of Subproblems vs Function of combining and splitting the subproblem of a Tree
2.Estimating Height of tree and no of subproblems
3.Estimating Number of of subproblems
4.Master Theorem