Preview this course in the non-credit experience today!
Start working toward program admission and requirements right away. Work you complete in the non-credit experience will transfer to the for-credit experience when you upgrade and pay tuition. See How It Works for details.
Course Type: Pathway | Breadth
Specialization: Foundations of Data Structures and Algorithms
Instructor: Dr. Sriram Sankaranarayanan, Professor of Computer Science
Prior knowledge needed: You must understand all concepts covered in Dr. Sankaranarayanan's non-credit Algorithms for Searching, Sorting, and Indexing and Trees and Graphs: Basics courses to succeed in this course. We highly recommend successfully completing those two courses in the non-credit experience before starting this course; they are a great option to refresh your skills and ensure you're ready. Note that you cannot apply credit from either of these courses toward MS-CS graduation requirements. Calculus, probability theory: distributions, expectations and moments. Some programming experience with Python also recommended.
Mathematical Background
We expect that the student is comfortable with basic mathematics at the level of a US College first year STEM student. This includes basic notions such as
-
Sets and Functions: Properties of sets, definition and properties of functions.
-
Logarithms and Exponentials: and their properties.
-
Basic series summations: arithmetic and geometric series summations.
-
Probability theory: basic definition of probability, independence of events, probability distributions and expectations.
CLRS has a helpful appendix but a student unfamiliar with these concepts can find numerous high quality explanations online.
Programming Background
The course involves solving programming assignments in Python. You must be comfortable with python programming.
-
Basic control structures in python: conditional branches, for loops and recursion.
-
Functions: defining and calling functions, and recursion.
-
In-built data structures: Lists and Dictionaries
-
Classes
Our use of python will get more sophisticated as the course progresses to accommodate some learning of python.
Course Description
This course continues our data structures and algorithms specialization by focussing on the use of linear and integer programming formulations for solving algorithmic problems that seek optimal solutions to problems arising from domains such as resource allocation, scheduling, task assignment, and variants of the traveling salesperson problem. Next, we will study algorithms for NP-hard problems whose solutions are guaranteed to be within some approximation factor of the best possible solutions. Such algorithms are often quite efficient and provide useful bounds on the optimal solutions. The learning will be supported by instructor provided notes, readings from textbooks and assignments. Assignments will include conceptual multiple-choice questions as well as problem solving assignments that will involve programming and testing algorithms.
Learning Outcomes
Course Grading Policy
Assignment |
Percentage of Grade |
---|---|
Quizzes (19 quizzes) |
2% each (total 38%) |
Programming Assignments (4 assignments) |
11.75% each (total 47%) |
Final Exam |
15% |
Course Content
2022 Coursera Innovation Award Winner. Learn more.