CS 7200 Algorithm Design and Analysis

• (WebEx recorded lectures will be available via CS7200 course page on Pilot.
• The two tests will be conducted in-person for uniformity and fairness.)

Course Objectives

To provide a solid foundation in algorithm design and analysis. Specifically, the student learning outcomes include:

• Able to apply graphs and matching algorithms.
• Ability to design algorithms using greedy strategy, divide and conquer approach, dynamic programming, and max flow - min cut theory.
• Ability to analyze asymptotic runtime complexity of algorithms including formulating recurrence relations.
• Defining and applying basic concepts of computational complexity.
• Preliminary knowledge of approximation and randomized algorithms.
  

Prerequisites CS 3100/5100 Data Structures and Algorithms

Course Description

This course introduces concepts related to the design and analysis of algorithms. Specifically, it discusses recurrence relations, and  illustrates their role in asymptotic and probabilistic analysis of algorithms. It covers in detail greedy strategies, divide and conquer techniques, dynamic programming and max flow - min cut theory for designing algorithms, and illustrates them using a number of well-known problems and applications. It also covers popular graph and matching algorithms, and basics of randomized algorithms and computational complexity. However, the depth of coverage of complexity classes and intractability, approximation algorithms, and randomized algorithms, will  depend on the available time. The programming assignments should be coded in Python 3.

Course Load

The course load includes homeworks, programming assignments and two tests. All the recorded lectures will be available in WebEx/Panopto from course webpage on Pilot and slide decks for the lectures from this publically available course webpage (https://cecs.wright.edu/people/faculty/tkprasad/courses/cs7200/cs7200.html).  Note that  the lectures  and slide decks  are organized  around  topics and may not clearly  map to  fixed lecture time periods. But they will  cover all the requisite content.

Assignment and Exams Policy

(0) We are planning to give same assignments and tests to multiple sections of the class.

(1) Team work is allowed on the assignments and in person discussions are encouraged. While assignments can be done individually and the team work is not mandatory to allow flexibility, forming teams of 2 to 3 students to learn together and collaborate on  joint-assignments is strongly encouraged. This sharing is to improve your understanding of the material. Plagiarising from online resources or other teams or from previous years  is prohibited. 
(2) The tests will be conducted in-class and every registered student MUST take the tests in person. The tests will be closed notes and closed book. You will not be permitted to use any electronic devices, including calculators, laptops, and phones, during the test. Each test will provide helpful information and code snippets from the text book or course notes that are deemed necessary for answering the questions. The format of the test will be communicated to you before the test and they will not be comprehensive.
(3) The entire class is expected to take the test simulaneously. As the class size is large, multiple versions of the questions (of comparable coverage and difficulty) will be administered. 
(4) Any academic impropriety during the test  (which includes copying from or communicating with other students, or accessing web resources) will have a minimum penalty of 'F' grade, plus additional disciplinary action for unethical behavior. See http://www.wright.edu/students/judicial/integrity.html for details. 

(5) While we expect peer exchanges on Course-Related Discord Channel and use of emails for personal matters, the course instructor and/or GTA will be available to the students on WebEx or in person for additional meetings as needed, through appointments.  The students will be notified in advance of any planned brief absences of the instructor due to conference travel, or research panel meetings, or for personal reasons, and every effort will be made to minimize disruption. 

Tentatively,  we are not planning to score assignments because of academic integrity issues in the past. However, assignment related questions can appear on the exam. Test 1 is for 40%, and Test 2 is for 60% for determining the final grade. If this weightage is modified for any reason, you will be informed about it. 

Grading Policy

The letter grades will be assigned using the following scale: A[90-100], B[80-90), C[70-80), D[60-70), and F[0-60). However, I reserve the right to adjust the scale to utilize the gaps in the distribution for a small class. For a large class such as yours, I will describe my approach to fitting a Gaussian (using mean and standard deviation), in detail, in a separate email.

Applicable University Policy on Generative AI

You are discouraged from using generative AI tools for solving assignment problems in this course. (Note that the output generated by these tools can be invalid (due to hallucination) and you will not be able to detect it without first knowing what the "correct" answer is.)

"Attendance" Policy

Required Text

1. J. Klienberg and Eva Tardos: Algorithm Design. 1st Edition. Addison Wesley, 2005. ISBN 0-321-29535-8
   (Lecture Slides)
   

Reference Text

1. T. H. Corman, C. E. Leiserson, R. L. Rivest, and C. Stein: Introduction to Algorithms. 3rd Edition. MIT Press, 2009. ISBN 978-0-262-53305-8  

Tentative Class Schedule and Syllabus

  Sample Old Tests  (Fall 2013, Spring 2020)

• Midterm (pdf)(pdf).
• Final (pdf)(pdf).

  Assignments (OFFERING-SPECIFIC)