CS 2500: Algorithms | Shubham Chatterjee

Course Description

This course is designed to equip undergraduate students with the foundational skills needed to solve basic computational problems through the effective use of algorithms. Throughout the course, students will develop a solid understanding of how to design, analyze, and implement algorithms to address a wide range of computational challenges. Students will learn to evaluate the efficiency of algorithms, focusing on both memory usage and runtime complexity. Key analytical tools such as asymptotic notation, recurrence relations, and mathematical proof techniques will be employed to rigorously assess algorithmic performance. In addition, students will gain practical experience in programming algorithms, reinforcing their understanding through hands-on application.

The course will cover a variety of algorithm design techniques. Below is a tentative list of topics:

Recursion: A method of solving problems where the solution involves solving smaller instances of the same problem. This technique is foundational for many other algorithm design strategies, such as divide-and-conquer and dynamic programming.
Divide-and-Conquer: Breaking down problems into smaller, more manageable sub-problems, solving each independently, and then combining their solutions to solve the original problem. Examples include merge sort and quicksort.
Dynamic Programming: Optimizing recursive algorithms by storing solutions to overlapping sub-problems to avoid redundant calculations. This approach is particularly useful for problems with optimal substructure, like the knapsack problem and the Fibonacci sequence.
Greedy Algorithms: Making the best local choices at each step with the hope of finding a global optimum. This technique works well for problems like finding the minimum spanning tree (e.g., Kruskal's and Prim's algorithms) or the shortest path in a graph (e.g., Dijkstra's algorithm).
Basics of Computational Complexity: Understanding the inherent difficulty of computational problems by classifying them into complexity classes such as P, NP, and NP-complete. This will include discussions on the theoretical limits of algorithm efficiency, the significance of polynomial-time algorithms, and an introduction to the concept of intractable problems. These concepts are critical for evaluating the feasibility of algorithmic solutions in real-world applications.

These design strategies will be applied to a broad spectrum of problems, ranging from fundamental tasks like sorting to more complex challenges like graph algorithms.

By the end of the course, students will have developed both the theoretical and practical skills necessary to approach algorithmic problems with confidence. They will be well-prepared to tackle more advanced topics in computer science and apply their knowledge to real-world computational tasks.

Course Goals

The course aims to achieve the following objectives:

Develop proficiency in analyzing the correctness and runtime performance of algorithms.
Gain fluency in key algorithm design paradigms, including recursion, divide-and-conquer, greedy algorithms, and dynamic programming.
Enhance technical writing and communication skills within computer science, including the ability to clearly write algorithms using pseudocode and flowcharts, articulate complexity analysis with asymptotic notation, and present design approaches comprehensively.
Acquire thorough knowledge of a core set of algorithms, such as sorting algorithms, graph algorithms, etc.
Apply algorithmic techniques to solve real-world computational problems effectively.

Course Prerequisites

This course is designed for undergraduate students enrolled in any science or engineering degree program who have a strong foundation in procedural programming, a solid understanding of data structures, and basic proficiency in calculus. If you are unsure about your readiness for this course, please contact the instructor for guidance.

Python will be the primary programming language used in this course. Under exceptional circumstances, students may seek approval from the instructor to use an alternative programming language.

The prerequisites for this course are as follows:

A grade of “C” or better in both Comp Sci 1200 and Comp Sci 1575.
A grade of “C” or better in either Math 1208 or Math 1214, or concurrent enrollment in Math 1208 or Math 1214.

Alignment with Bloom's Taxonomy

This course leverages the cognitive framework of Bloom's Taxonomy to guide students through a structured progression of learning objectives. While AI tools can aid in achieving some of these objectives, this course emphasizes the distinctive human skills that are crucial for mastering algorithms and computational problem-solving. The focus is on equipping students with the ability to critically think, evaluate, and innovate, as these are the higher-order skills AI cannot fully replicate. These advanced skills are essential for solving complex computational problems and designing innovative algorithms. By the end of the course, students will have gained not only foundational knowledge but also the ability to apply, critically assess, and design algorithms in novel contexts.

Figure: Bloom's Taxonomy - Levels of Cognitive Learning

Remember: Students will begin by recalling key concepts, definitions, and algorithmic paradigms. For example, they will memorize common algorithms (e.g., merge sort, Dijkstra’s algorithm) and foundational terminologies like asymptotic notation and complexity classes. This foundational knowledge ensures students can retrieve critical information during problem-solving, even in situations where no external aids are available.
Understand: Students will demonstrate comprehension by explaining algorithmic concepts and principles. For instance, they will articulate how divide-and-conquer techniques reduce problem complexity or how dynamic programming avoids redundant calculations. Contextual understanding is essential for applying these techniques effectively to a wide range of computational challenges.
Apply: By implementing algorithms in Python, students will translate theoretical knowledge into practical coding tasks, such as optimizing solutions for graph traversal or developing sorting algorithms. Through hands-on assignments, students will refine their ability to debug, test, and adapt their implementations to specific scenarios, emphasizing the importance of developing practical, independent programming skills.
Analyze: Higher-order thinking begins with analyzing the trade-offs and efficiency of algorithms. Students will learn to break down problems into components, use recurrence relations to predict runtime, and assess memory usage. They will also compare different solutions to identify their strengths and limitations in specific scenarios, building a nuanced understanding of algorithmic performance.
Evaluate: Students will critique and justify algorithmic choices for solving given problems. For instance, they will evaluate when to use a greedy algorithm versus dynamic programming, justifying their decisions based on problem characteristics like optimal substructure and overlapping subproblems. Evaluative skills ensure students can make informed, context-aware decisions in real-world applications.

While the creation of original algorithms or adaptations of existing ones to solve novel computational challenges is undoubtedly important, the "Create" aspect of Bloom's Taxonomy is reserved for CS 5200, a more advanced algorithms course. By focusing on foundational skills in this course, students will build a strong base in algorithmic thinking, analysis, and implementation, which are critical prerequisites for tackling the creative and innovative aspects of algorithm design at a higher level. Excluding the "Create" stage from this course allows students to dedicate their efforts to mastering the essential building blocks of algorithmic problem-solving, such as understanding key paradigms (e.g., recursion, divide-and-conquer, dynamic programming, greedy strategies) and evaluating algorithm performance through rigorous analysis. These skills are invaluable for developing a deep understanding of computational thinking and preparing students for success in advanced courses like CS 5200. By leaving the "Create" stage for a more advanced course, this course remains focused on equipping students with the analytical and practical skills needed to effectively approach real-world computational problems. It ensures that students are not overwhelmed by overly complex tasks before they are ready, setting them up for greater success in their academic and professional pursuits.

By the end of the course, students will have progressed through all (but one) levels of Bloom's Taxonomy, gaining not only foundational knowledge but also the higher-order thinking skills of analyzing, evaluating, and creating. These skills will enable them to solve complex computational problems independently and communicate their solutions effectively, ensuring they are well-prepared for advanced studies and professional roles in computer science.

Developing Higher-Order Thinking Skills

A significant focus of this course is on fostering higher-order thinking skills, specifically:

Problem Analysis: Students will dissect complex problems, identifying patterns, breaking problems into subproblems, and analyzing the feasibility of various approaches.
Critical Evaluation: Through in-depth discussions and assignments, students will evaluate different algorithmic strategies, examining their trade-offs and performance in terms of time and space complexity.
Algorithm Design and Innovation: Students will be tasked with creating and optimizing algorithms for new challenges, requiring them to integrate knowledge, experiment with techniques, and propose innovative solutions.

Do we still need this in the age of AI assistants?

Yes, developing independent problem-solving and higher-order thinking skills remains essential, even in the age of AI assistants. While AI tools can assist in tasks like recalling facts, generating examples, or summarizing content, they are not a substitute for human creativity, critical thinking, and adaptability. These skills are indispensable in addressing complex, real-world challenges where human judgment, ethical reasoning, and innovation are required.

Critical Thinking: AI lacks the ability to fully understand and reason through the emotional, moral, and contextual dimensions of problems. Evaluating complex scenarios and proposing meaningful solutions requires human cognition, which goes beyond algorithmic outputs.
Ethical Reflection: Decisions involving trade-offs or societal implications demand human judgment. While AI can highlight possible outcomes, it cannot weigh these against ethical considerations or make context-aware decisions.
Creativity and Innovation: AI operates based on patterns and data it has been trained on. True originality and the ability to think outside the box—essential for creating novel algorithms or solving new problems—are uniquely human capabilities.
Adaptability: AI models are limited to their training data and struggle with new or unique challenges. Humans, on the other hand, excel in adapting to unforeseen circumstances and crafting solutions that go beyond predefined models.

Emphasis on Technical Writing

Technical writing is a higher-order skill within Bloom's Taxonomy, falling under the levels of Analyze, Evaluate, and Create. It requires students not only to understand and apply algorithmic concepts but also to critically analyze trade-offs, evaluate design decisions, and communicate solutions effectively. This skill extends beyond recalling or applying knowledge—it challenges students to synthesize their understanding and present it in a professional, structured, and coherent manner.

In this course, technical writing serves as a bridge between theoretical knowledge and practical problem-solving. Students will:

Analyze: Break down algorithms into components and use pseudocode or flowcharts to effectively communicate their structure and logic.
Evaluate: Explain the trade-offs of algorithms, considering factors such as time complexity, space usage, and suitability for specific problems, using asymptotic notation and complexity analysis to justify their conclusions.
Create: Articulate design decisions and justify their approaches through clear, well-documented assignments, mimicking the standards of professional research and technical communication.

By emphasizing technical writing as a core component of this course, students develop the ability to convey complex ideas with precision and professionalism. This skill not only enhances their understanding of algorithms but also prepares them for advanced academic research, collaborative projects, and professional roles in the field of computer science. Through structured documentation and communication, students learn to make their algorithmic solutions accessible and understandable, a critical capability for success in real-world computational problem-solving.

Grading and Homeworks

Your performance in this course will be assessed through assignments and exams.

Assignments [50%]: These assignments consist of some problems requiring detailed answers. These aim to deepen your understanding of the material covered in class. Assignments are released every Tuesday and are due by midnight the following Tuesday. You will have 7 days to complete each assignment.
Midterm Examination [25%]: The midterm examination will cover all the material discussed up until the midterm point of the course. It is designed to assess your understanding and application of the key concepts.
Final Comprehensive Examination [25%]: The final exam is comprehensive, covering all the material discussed throughout the course. It will evaluate your overall understanding and integration of the topics covered.

Grading Scale

Letter Grade	Points
A	90 – 100 points
B	80 – 89 points
C	70 – 79 points
D	60 – 69 points
F	59 and below

Course Materials

Course Materials - Lecture Notes, Slides, and Resources
Assignments - Previous assignments and exams