Sprint 1: Analyzing Algorithms

Roadmap:

• Teams
• Sprint Duration: 2/6 - 2/22
• Quiz: Thurs Feb 22
• Requirements due: (Team) Tues Feb 20 (Individual) Thurs Feb 22

Rationale:

This sprint covers the very basics of algorithm analysis - how to look at code (or pseudocode) and write a math function denoting the time efficiency of the algorithm. We begin by looking at the growth rate of functions, so that when you write your analysis you will be able to compare the efficiency of one algorithm with that of another. Then, analyzing a non-recursive algorithm is a fairly straight-forward method of looking at the structure of the loops in the algorithm.

Secondly, we look deeper at recursive algorithms. To analyze them, we first write a recurrence relation representing the time analysis (you probably learned how in Discrete) and then we actually solve these relations to get the well-known functions we've been dealing with so far.

We also learn our first two categories of problem solving techniques: Brute force (or try-everything) and Divide and conquer (recursive algorithms). You have already written programs using these two techniques, but we take time to review these skills, adding our new skills of analysis to see which technique is better for a given problem.

Responsibilities (What you need to know):

• Vocabulary:
  • Growth of Functions and big-o, omega, and theta
  • Efficiency classes
  • Best case, worst case, and average case analysis
  • Recurrence Relations, Master Theorem, Back substitution Method
  • Brute-Force and Divide-and-Conquer
  • Medians and Order statistics
• Be able to articulate why we usually only care about the efficiency classes
• Be able to rank functions in terms of growth with big-o, omega, and theta notation
• Be able to write the efficiency class of a non-recursive algorithm from its pseudocode for either best, worst, or average case.
• Be able to write a recurrence relation describing the efficiency of a recursive algorithm given its pseudocode.
• Know which relations can be solved with the Master theorem and which cannot.
• Be able to solve recurrence relations with either the Master theorem or the Back-substitution method, as appropriate.
• Know the difference between brute force and divide-and-conquer algorithms, and be able to write solutions to problems using these methods.
• Be familiar with both a brute force and divide-and-conquer solution to the order statistics problem.

Requirements (What you need to do):

Individual Requirements:

• Understand the concepts on the Responsibilities list.
• Complete this project: Recursive Art (NOTE: THIS IS AN INDIVIDUAL PROJECT)

Team Requirements:

• Complete this problem set on Basic analysis of Non-recursive functions
• Complete this problem set on Divide-and-Conquer algorithms

Resources: (Expert Request)

• Textbook readings:
  • Basic Analysis and Growth of Functions
  • Divide-and-Conquer Algorithms
  • The Select Algorithm
• Useful Math Cheat sheet (Will be given on quiz)
• Practice:
  • Basic Analysis and Growth of Functions (Solution)
  • Divide-and-Conquer algorithms (Solution)
  • Recursion Worksheet
  • Practice Quiz (Solution)
  • Review Game (Answers)
• Lecture Notes:
  • Intro and Motivation
  • Basics of Analysis
  • Divide and Conquer
• Videos:
  • Intro to Algorithm Analysis
  • Big-oh (and part 2 and part 3)
  • Writing Recurrences
  • Solving Recurrences
  • Median Algorithm
  • Divide and Conquer (A cute Santa cartoon!)

Reality Check:

• Tuesday, Feb 6: Sprint planning meeting. For homework, read textbook on Basic analysis
• Thursday, Feb 8: Lecture and worksheet practice on Basic Analysis. Lecture on Writing recurrence relations. For homework, try problem set on Basic Analysis and read on Divide-and-Conquer and Order statistics
• Tuesday, Feb 13: Lecture and practice solving recurrence relations. For homework, try problem set on Divide-and-conquer problems and start on the project.
• Thursday, Feb 15: Practice more recurrence relations and go over the Select algorithm. Compare answers to problem sets with your team and finalize answers. For homework, work on the project.
• Tuesday, Feb 20: Hand in problem sets and go over them in class. Do quiz review. For homework, finish the project.
• Thursday, Feb 22: Have quiz and turn in project.