**Description**: Design and correctness of algorithms, including divide-and-conquer, greedy and dynamic programming methods. Complexity analyses using recurrence relations, probabilistic methods, and NP-completeness. Applications to order statistics, disjoint sets, B-trees and balanced trees, graphs, network flows, and string matching.

**Objectives**

- To introduce a variety of topics in discrete mathematics
- To develop ability of modeling, reasoning, proving, analysis, and algorithmic problem solving
- To present examples of applications of discrete mathematics to computer science
- To have students learn mathematical writing as the basis of technical writing

**Course Learning Outcomes**

- Students are aware of fundamental algorithms of computer science, and their associated data structures and problem solving techniques.
- Students can compose a problem formulation of a real-world problem mathematically.
- Students can decide whether given pseudocode is correct for a given problem formulation; construct a counterexample if the given pseudocode is incorrect; and outline a proof for its correctness otherwise.
- Students can design a correct algorithm for a given problem and describe the algorithm as pseudocode in a given pseudocode syntax.
- Students can analyze the worst-case and best-case space and time complexities of a given algorithm.
- Students can create a software program for accurately implementing an algorithm specified in pseudocode. Students can implement software objects meeting Abstract Data Type specifications.
- Students can produce a software product including documentation for given requirements & design specifications.

**Program Learning Outcomes**

- a. Students can apply knowledge of computing and mathematics appropriate to the discipline
- b. Students can analyze a problem, and identify and define the computing requirements appropriate to its solution
- c. Students can design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs
- f. Students can communicate effectively with a range of audiences

**Prerequisites**: 211 and 241, or consent.

**Textbook(s)**: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009.

**Grading**: 3 projects (worth 10% each)
3 midterms (worth 10% each)
in-class assignments (worth 20% total)
final exam (worth 20%)

**Policies**: 10% in-class
90% midterms and final

**Schedule**

- Week 1: Introduction
- Week 2: Growth of functions
- Week 3: Abstract data types
- Week 4: Probabilistic analysis
- Week 5: Hash tables
- Week 6: Divide and conquer algorithms
- Week 7: Binary search trees
- Week 8: Heap sort
- Week 9: Quick sort
- Week 10: Balanced trees
- Week 11: Dynamic programming
- Week 12: Greedy algorithms
- Week 13: Graphs
- Week 14: Amortized analysis
- Week 15: Disjoint sets
- Week 16: Review
- Week 17: Final exam

Each week requires reading one chapter from the text, approximately 30 pages on average per week.