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.