The need for efficient algorithms arises in nearly every area of computer science. But the type of problem to be solved, the notion of what algorithms are “efficient,” and even the model of computation can vary widely from area to area. In this second class in algorithms, we will survey many of the techniques that apply broadly in the design of efficient algorithms and study their application in a wide range of application domains and computational models.

The goal is for the class to be broad rather than deep. Our plan is to touch upon the following areas. This is a tentative list of topics that might be covered in the class; we will select material adaptively based on the background, interests, and rate of progress of the students.

Learning Objectives and Outcomes:

By the end of this course students will be able to:

1. Appraise the correctness of algorithms using inductive proofs and loop invariants.
2. Analyze running times of algorithms using asymptotic analysis.
3. Evaluate the use of algorithms in our world.
4. Compare algorithmic design paradigms and methods of analysis.
5. Synthesize efficient algorithms in software engineering design.

Course Schedule and Topics

This course will cover the following topics in eight learning sessions, with one Unit per week.

Week 1: Unit 1 – The Role of Algorithms in Computing

Week 2: Unit 2 – Growth of Functions and Asymptotic Analysis of Algorithms

Week 3: Unit 3 – Divide and Conquer

Week 4: Unit 4 – Analysis of Sorting Algorithms

Week 5: Unit 5 – Data Structures and Algorithms

Week 6: Unit 6 – Hash Tables and their Applications

Week 7: Unit 7 – Graphs and Algorithms

Week 8: Unit 8 – String Matching Algorithms

Learning Guide

The following is an outline of how this course will be conducted, with suggested best practices for students.

Unit 1: The Role of Algorithms in Computing

• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Complete and submit the Written Assignment
• Complete the Reflective Portfolio Assignment

Unit 2: Growth of Functions and Asymptotic Analysis of Algorithms

• Peer assess Unit 1 Written Assignment
• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Complete and submit the Written Assignment
• Complete the Reflective Portfolio Assignment

Unit 3: Divide and Conquer

• Peer assess Unit 2 Written Assignment
• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Complete and submit the Written Assignment
• Begin and participate in the Group Activity (Due Unit 6)
• Complete the Reflective Portfolio Assignment

Unit 4: Analysis of Sorting Algorithms

• Peer assess Unit 3 Written Assignment
• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Complete and submit the Written Assignment
• Continue to participate in the Group Activity
• Complete the Reflective Portfolio Assignment

Unit 5: Data Structures and Algorithms

• Peer assess Unit 4 Written Assignment
• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Continue to participate in the Group Activity
• Complete and submit the Written Assignment
• Complete the Reflective Portfolio Assignment

Unit 6: Hash Tables and their Applications

• Peer assess Unit 5 Written Assignment
• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Complete and submit the Written Assignment
• Post finalized Group Activity
• Complete the Reflective Portfolio Assignment

 Unit 7: Graphs and Algorithms

• Peer assess Unit 6 Written Assignment
• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Complete and submit the Written Assignment
• Complete the Reflective Portfolio Assignment

Unit 8: String Matching Algorithms

• Peer assess Unit 7 Written Assignment
• Read the Learning Guide and Reading Assignments
• Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum)
• Complete the Reflective Portfolio Assignment
• Complete and submit the anonymous Course Evaluation