# ICS 311: Algorithms

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.