Course Syllabus for "CS303: Algorithms"
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.
Upon successful completion of this course, you will be able to:
- explain and identify the importance of algorithms in modern computing systems and their place as a technology in the computing industry;
- indentify algorithms as a pseudo-code to solve some common problems;
- describe asymptotic notations for bounding algorithm running times from above and below;
- explain methods for solving recurrences useful in describing running times of recursive algorithms;
- explain the use of Master Theorem in describing running times of recursive algorithms;
- describe the divide-and-conquer recursive technique for solving a class of problems;
- describe sorting algorithms and their runtime complexity analysis;
- describe the dynamic programming technique for solving a class of problems;
- describe greedy algorithms and their applications;
- describe concepts in graph theory, graph-based algorithms, and their analysis;
- describe tree-based algorithms and their analysis; and
- explain the classification of difficult computer science problems as belonging to P, NP, and NP-hard classes.
In order to take this course, you must:
√ Have access to a computer.
√ Have continuous broadband internet access.
√ Have the ability/permission to install plug-ins or software (e.g. Adobe Reader or Flash).
√ Have the ability to download and save files and documents to a computer.
√ Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.).
√ Be competent in the English language.'
√ Have read the Saylor Student Handbook.
√ Be knowledgeable about basics of computer programming using a high-level language, such as C/C++ and/or have completed Introduction to Computer Science I (CS101), Introduction to Computer Science II course (CS102), Elementary Data Structure (CS 201), and Discrete Structures (CS 202) from “The Core Program” in the Computer Science discipline.
√ Be comfortable in writing, compiling, and executing your own programs.
√ Be knowledgeable about basics of discrete mathematics concepts.
Welcome to CS303. Below, please find general information on this course
and its requirements.
Course Designer: Dr. Bhanu Kapoor
Primary Resources: Primary sources for this course include video-based lectures and online reading materials from books and other sources. Some of the key sources include:
- MIT: Dr. Charles E. Leiserson’s “Introduction to Algorithms”
- IIT Bombay: Dr. Abhiram Ranade’s “Introduction to Algorithms”
- University of California – Berkeley: Dr. Jonathan Shewchuk’s “Data Structures”
- University of California – Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani’s Algorithms
- IIT Bombay: Dr. Sunder Viswanathan’s “Design and Analysis of Algorithms”
Requirements for Completion: Please refer to the Course Requirements
section above to review the requirements for this course.
Time Commitment: The course will require approximately 100 work hours over a period of 15 weeks to complete. This includes time spent on lectures, readings, homework, and examinations to complete the requirements.