CS 412 Algorithms: Design and Analysis
This is the crowning glory of the CS Kernel group of required courses for the CS major. By the time students take this course in their junior year, they have completed several programming courses, have reasonable background in discrete mathematics including counting and probability, have done courses on data structures, and know about models of computation and about complexity. This course is a tour of various algorithm design techniques and introduces the tools to analyze them. The exact techniques vary per offering but usually include divide-and-conquer algorithms, dynamic programming, randomized algorithms, graph algorithms, and greedy algorithms. Analysis tools include asymptotic analysis, recurrence relations, and master theorem. The texts we use are Cormen et al., Dasgupta et al., Rosen, and Goodrich et al..
The course has been developed by my ex-colleagues Jibran Rashid and Shahid Hussain, and colleague Shah Jamal Alam. It is offered to every CS batch starting with our inaugural Class of 2018. I got on board in Spring 2022 when it was offered to Class of 2023.
Spring 2023
LMS | Syllabus | Evaluation (course ongoing) | GitHub Classroom
I am now leading the course. There are 4 sections, with Faisal Alvi and myself teaching two each. The course includes weekly recitations this time. To these, we will try to delegate the mechanical aspects of some topics like asymptotic analysis, so that lecture time can be freed to include more algorithms, particularly string algorithms and pseudo-random number generators. Weekly challenges were generally appreciated last time and will be assigned similarly this time.
Spring 2022
LMS | Syllabus | Evaluation | GitHub Classroom
The course was led by Shah Jamal Alam. I enhanced the Weekly Challenge category of assessments. These used to be very short problems, usually auto-graded, e.g. multiple choice questions. I replaced them with programming problems meant to expose, explore, or reveal aspects of the topics currently being done in the lectures. The output was mostly visual in nature, e.g. a plot showing the run time of an algorithm with growing problem size, or of different algorithms for the same task. These were to be shared on the course's social group.
I also introduced my usual practice of Live Syllabus which is a live-shared spreadsheet containing a date-wise list of topics, assessments, and other course events. It is populated for the entire semester when classes begin and edited by the instructors to reflect changes as the semester proceeds. The changes are available to the students real-tine through a read-only link.
The social as well as the programming aspects introduced by me were appreciated by the students.