Covers foundational materials for computer science that is often assumed in advanced courses. Topics include set theory, Boolean algebra, functions and relations, graphs, propositional and predicate calculus, proofs, mathematical induction, recurrence relations, combinatorics, discrete probability. Focuses on examples based on diverse applications of computer science. Requisites: Requires prerequisite or corequisite course of CSCI 2270 and a prerequisite course of MATH 1300 or MATH 1310 or APPM 1350 or APPM 1345 (minimum grade C-).
Covers advanced data structures, computational geometry, cryptography, dynamic programming, greedy algorithms, divide-and-conquer, graph algorithms (e.g., depth-first search), network algorithms (e.g., shortest paths), approximation algorithms. Requisites: Requires prerequisite courses of CSCI 2270 and APPM 1360 or MATH 2300 and one of the following: CSCI 2824, ECEN 2703, APPM 3170 or MATH 2001 (all minimum grade C-).
Introduces the foundations of formal language theory, computability, and complexity. Shows relationship between automata and various classes of languages. Addresses the issue of which problems can be solved by computational means, and studies complexity of solutions. Requisites: Requires prerequisite courses of CSCI 3104 and CSCI 3155 (all minimum grade C-).
Surveys molecular biology and combinatorial algorithms used to understand DNA, RNA, and proteins. Students work in groups to define and tackle meaningful biological problems and learn to collaborate effectively with scientists in other disciplines. Recommended prereq., comfort with mathematics and/or programming experience, and more advanced understanding (upper undergraduate level) of any relevant discipline. Same as CSCI 5314, MCDB 4314 and MCDB 5314. Requisites: Requires a prerequisite course of CSCI 3104 (minimum grade C-).
Surveys molecular biology and combinatorial algorithms used to understand DNA, RNA, and proteins. Students work in groups to define and tackle meaningful biological problems and learn to collaborate effectively with scientists in other disciplines. Same as CSCI 4314 and MCDB 5314. Requisites: Restricted to Computer Science (CSEN) graduate students or Computer Science Concurrent Degree majors only.
Reviews regular expressions and finite automata. Studies Turing machines and equivalent models of computation, the Chomsky hierarchy, context-free grammars, push-down automata, and computability. Requisites: Restricted to Computer Science (CSEN) graduate students or Computer Science Concurrent Degree majors only.
Techniques for algorithm design, analysis of correctness and efficiency; divide and conquer, dynamic programming, probabilistic methods, advanced data structures, graph algorithms, etc. Lower bounds, NP-completeness, intractability. Recommended prereq., CSCI 2270 or equivalent. Requisites: Restricted to Computer Science (CSEN) graduate students or Computer Science Concurrent Degree majors only.
Explores context-free languages: pumping lemma and variants, closure properties, and decision properties. Involves parsing algorithms, including general and special languages, e.g., LR. Additional topics chosen by instructor. Recommended prereq., CSCI 5444 or instructor consent required. Requisites: Restricted to Computer Science (CSEN) graduate students or Computer Science Concurrent Degree majors only.
Topics include matching and network flows, matroids, computational geometry, parallel computation (PRAM, hypercube, mesh). Also includes Vlsi, database theory, distributed computation, cryptography, robotics, scheduling, probabilistic algorithms, approximation algorithms, average case, and amortized analysis, time permitting. Requisites: Requires prerequisite course of CSCI 5454 (minimum grade B). Restricted to graduate students only.
Selected topics of current interest in theory of computation. Requisites: Requires prerequisite course of CSCI 5454 (minimum grade B). Restricted to graduate students only.
