skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · courses · catalog · 
 

Course Catalog: Theory of Computation

 
Hide Descriptions Show Descriptions
CSCI 2824 (3). Discrete Structures

Covers foundational material 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. Prerequisites: CSCI 2270. Offered Fall 2011 and Spring 2012.

CSCI 3104 (4). Algorithms

Studies 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. Prerequisites: CSCI 2824 and two semesters of calculus. Offered Fall 2011 and Spring 2012.

CSCI 3434 (3). Theory of Computation

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. Prerequisites: CSCI 3104 and CSCI 3155. Offered Spring 2012.

CSCI 4314 (3). Algorithms for Molecular Biology

Surveys combinatorial algorithms used to understand DNA, RNA, and proteins. Introduces students to methods used to process genomic data. Topics covered include a review of algorithms and molecular biology, sequence analysis, RNA and protein structure analysis, and comparative genomics. Students will get hands-on experience processing recent genomic data. Same as MCDB 4314. Prerequisites: CSCI 2270 and one of CSCI 3104, CHEM 4711, IPHY 4200 or MCDB 3500. Offered Fall 2011.

CSCI 5314 (3). Algorithms for Molecular Biology

Surveys combinatorial algorithms used to understand DNA, RNA, and proteins. Introduces students to methods used to process genomic data. Topics covered include a review of algorithms and molecular biology, sequence analysis, RNA and protein structure analysis, and comparative genomics. Students will get hands-on experience processing recent genomic data. Same as MCDB 5314. Prerequisites: CSCI 2270 and one of CSCI 3104, CHEM 4711, IPHY 4200 or MCDB 3500. Offered Fall 2011.

CSCI 5444 (3). Introduction to Theory of Computation

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. Prerequisites: Graduate standing or instructor consent. Offered Fall 2011.

CSCI 5454 (3). Design and Analysis of Algorithms

Techniques for algorithm design, analysis of correctness and efficiency; divide and conquer, dynamic programming, etc. Advanced data structures, algorithms in graph theory, geometry, VLSI, linear algebra, etc. Lower bounds, NP-completeness, intractability. Prerequisites: CSCI 2270 or equivalent. Offered Spring 2012.

CSCI 5654 (3). Linear Programming

Presents algorithms, simplex, and modifications. Examines theory -- duality and complementary slackness. Involves network flow algorithms. Introduces integer programming Prerequisites: Linear algebra. Offered Fall 2011.

CSCI 5714 (3). Formal Languages

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. Prerequisites: CSCI 5444 or consent of instructor.

CSCI 6454 (3). Advanced Algorithms

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. Prerequisites: CSCI 5454.

CSCI 7154 (3). Topics in Theory of Computation

Selected topics of current interest in theory of computation. Prerequisites: Consent of instructor.

 CSCI 7154. Complexity of Computations
 CSCI 7154. Data Structures
 CSCI 7154. Foundations of Cyber Physical Systems
 CSCI 7154. Genetics
 CSCI 7154. Natural Computing
 CSCI 7154. Readings in Formal Methods
 CSCI 7154. Research Problems in Theoretical Computer Science
 CSCI 7154. Software Engineering Theory
 
See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Questions/Comments?
Send email to

Engineering Center Office Tower
ECOT 717
+1-303-492-7514
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:12)
 
.