Last updated: 2 April, 2018.

CS 231: Algorithmic Problem Solving

General description

This course introduces various algorithmic and heuristic techniques that can be employed to solve a wide variety of problems using a computer. Students learn both the advantages and the pitfalls of translating a real-world problem into a formal specification, and consider the subsequent steps of choosing one or more paradigms, analyzing the algorithms, and implementing them. Specific paradigms taught include exhaustive search, divide and conquer, greedy, and dynamic programming approaches. Students who successfully complete the course can use these approaches to design and develop efficient programs for a wide variety of applications.

Logistics

Audience

• Students wishing to understand how choices made in program design can significantly affect performance and how to make these choices
• Students doing the Computer Science minor or Computing option.
• Highly recommended for students in Information Management and similar fields and for those in the Mathematics/Teaching plan
• Not open to Computer Science majors and SE and CFM students (take CS 341 instead)

Normally available

• Spring

Related courses

• Predecessors: One of CS 116, 136, 138, 146. Students who have taken introductory computer courses outside the Math Faculty should consult a CS advisor to determine if they are prepared for this course.
• Successors: CS 234, CS 338, CS 370, CS 431 and CS 487.
• Conflicts: CS 341

Software/hardware used

• Python (Note: Students should check which version of Python will be used in class.)

Typical reference(s)

• Anany Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., Pearson, 2011.

Required preparation

• Use and follow mathematical reasoning and notation; in particular, work comfortably with simple predicate logic, functions, and elementary probability.
• Describe basic quadratic sorting algorithms, such as Selection Sort or Insertion Sort.
• Given a simple, well-specified computational task, write a program in a high-level imperative language (e.g., Python, C, or Java) and generate appropriate test cases. Use as appropriate simple types, built-in compound types and control idioms, such as selection, iteration, and recursion. These programs should not require more than a single routine, possibly together with a small number of additional helper routines.
• Define and write programs that work with recursively defined structures, such as binary trees.

Note: The course uses Python for its programming examples and assignments. Students will be expected to have background in an imperative programming language; materials detailing Python syntax will be provided.

Learning objectives

• Describe the steps taken in solving a real-world problem on a computer.
• Explain and use the concepts of asymptotic running time, order notation, worst-case, average-case, and best-case complexity, and lower and upper bounds. Given a simple algorithm written in pseudocode, determine and informally justify its asymptotic running time, as expressed in order notation.
• Describe situations in which the greedy paradigm is applicable and situations in which it yields an efficient algorithm. Given a simple problem, be able to form a greedy algorithm, and, when appropriate, form an example input that shows its inefficiency.
• Describe situations in which divide-and-conquer can be applied and those in which it is unsuitable. Given a suitable problem, form an algorithm that uses divide-and-conquer and analyze it using recurrence relations.
• Describe situations in which dynamic programming can be used. Given a suitable problem, form and analyze a dynamic-programming algorithm.
• Explain various methods for exploring the search space, including exhaustive search, backtracking, and branch-and-bound. Given a simple problem, form an algorithm using one of these methods and informally analyze the asymptotic running time, as expressed in order notation.
• Explain the notions of hardness, reduction, and lower bounds.
• Explain how various approaches, such as approximation algorithms and heuristics, can be used on hard problems.
• Write, test, and debug programs in the Python language that incorporate the ideas described above.

Typical syllabus

• Steps: real-world problem, formal statement, algorithms, analysis, implementation, testing
• Types of problems: decision, search, optimization, constraint-satisfaction, counting, enumeration
• Analysis of time and space requirements using asymptotic notation; solution of recurrence relations
• Python language review: basic data types, functions, branching, iteration, recursion, classes

• Exhaustive search
• Greedy algorithms
• Divide-and-conquer
• Dynamic programming
• Backtracking
• Branch-and-bound

• Lower bounds
• NP-completeness

• Fixed-parameter algorithms
• Randomized algorithms
• Approximation algorithms
• Heuristics
• On-line algorithms