CSCI140 HM - Algorithms

Credit(s): 3

Instructor(s): Boerkoel, Montañez, Randolph, Schofield, Stone

Offered: Fall and Spring

Description: Algorithm design, analysis, and correctness. Design techniques including divide-and-conquer and dynamic programming. Analysis techniques including solutions to recurrence relations and amortization. Correctness techniques including invariants and inductive proofs. Applications including sorting and searching, graph theoretic problems such as shortest path and network flow, and topics selected from arithmetic circuits, parallel algorithms, computational geometry, and others. An introduction to computational complexity, NP-completeness, and approximation algorithms. Proficiency with programming is expected as some assignments require algorithm implementation. (Crosslisted as MATH168 HM)

Prerequisite(s): ((CSCI070 HM and (MATH055 HM/CM/PZ/SC) and (MATH019 HM or MATH032 CM/PO/PZ/SC or MATH032S PO or MATH067 PO) and (MATH073 HM or MATH060 CM/PO/PZ/SC or MATH060C CM)) or ((CSCI060 HM or CSCI042 HM) and MATH131 HM)) or (CSCI062 PO and CSCI054 PO). CSCI081 HM is recommended.