Algorithms

[Instructor Homepage]

General Course Information

Instructor

Dr. Bineet Ghosh

Teaching Assistant

David Amebley

Course Description

This course will introduce students to the key concepts and techniques used to model, analyze, and reason about computational processes. Following are some of the broad topics that will be covered in this course:

  1. Analysis of Algorithms

  2. Searching

  3. Sorting

  4. Graphs

  5. Divide and Conquer

  6. Greedy Algorithms

  7. Dynamic Programming

  8. Intractability

Prerequisites

  1. Algorithms (CS 201)

  2. Data Structures and Analysis (eg., CS 201)

  3. Discrete Structures (Or their equivalents).

  4. Programming in Python (CS 223/323)

  5. Mathematical Maturity

    • Have you formally proved correctness of algorithms?

    • Are you familiar with proofs using induction?

      • Test your knowledge of inductive proofs. One can refer to basic inductive proofs (available online) and see how comfortable they are in understanding the proofs.

    • Familiarity with theorems in graph theory would be useful

    • Self Evaluation Test will be posted on the first day of classes (Aug 20) to test your pre-requisites.

Speak to instructor, if unsure.

Textbooks

Recommended textbooks:

  1. "Algorithm Design", by Jon Kleinberg, Eva Tardos (primary)

  2. "Introduction to Algorithms", by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein

Course Objectives

By the end of this course students are expected to be able to:

  1. Understand and apply fundamental algorithm design paradigms.

  2. Analyze algorithm performance using mathematical and empirical methods.

  3. Prove algorithm correctness using formal reasoning.

  4. Recognize and address computationally intractable problems.

Student Learning Outcomes

The students can test the above given objectives in the following way:

  1. Design and implement efficient algorithms in Python.

  2. Analyze and compare algorithm efficiency using asymptotic notation.

  3. Apply graph theory, dynamic programming, and greedy strategies to problem-solving.

  4. Identify NP-hard problems and discuss their implications.

Grading

  1. Assignments: 20%

    1. Must be typed (preferably in LaTex), and not handwritten. However hand-drawn figures (such as automata) are permitted.

    2. Assignments will be clearly marked as graded/ungraded.

    3. All submissions must follow this format: <firstname-lastname-CWID>.

  2. Quiz: 70%

    1. Quiz 1: 30%

    2. Quiz 2: 40%

  3. Presentation (of topics/papers), and leading class discussion: 10%

  4. Self Evaluation Test will be posted on the first day of classes (Aug 20) to test your pre-requisites.

Late work policy

Missed quiz policy

Attendance and Participation

Instructor Absence

On rare occasions, the instructor may be away from campus for professional commitments such as conferences, invited talks, or other academic obligations. During these instances, one of the following arrangements will be made:

The instructor will provide advance notice of any such changes to the regular class schedule.

Social Media Policy

In addition to official course announcements on Blackboard, the instructor will also post selected updates—such as important reminders, lecture highlights, and relevant resources—on the course’s social media channels:

Following these accounts is optional and not a substitute for regularly checking Blackboard. All critical information will be posted on Blackboard, and students are responsible for reviewing it in a timely manner.

Communication Boundaries: Students should not send direct messages (DMs) to the instructor or TA via social media. All course-related communication must be conducted through University email using the guidelines provided above.

Disclaimer Notification of Changes

The instructor will make every effort to follow the guidelines of this syllabus as listed; however, the instructor reserves the right to amend this document as the need arises (including project due dates and test dates). In such instances, the instructor will notify students in class and/or via email and will endeavor to provide reasonable time for students to adjust to any changes.

Standard Course Policies

Please refer to the university's standard course policies (Honor code, misconduct, behavior etc.) for details.

Schedule

Please send me an email if you want the lecture slides (registered students can access the slides through Blackboard)

Daily updates are also posted on my lab's social media channels: [instagram/autmn_lab], [facebook/autmn.lab]