Foundations Track (FOCS) Flashcards
Overview
Broad education, problem solving
Future areas, good for grad school, may have classes not offered
Objectives
The Foundations of Computer Science track gives students a broad education on foundational concepts, tools, and techniques underlying existing and future areas of computer science.
Required Courses
All track requirements, regardless of department, must be completed with a grade of C or higher.
Course Title
CS 35200 Compilers: Principles and Practice
CS 38100 Introduction to the Analysis of Algorithms
Electives
Choose four courses from the following:
Course Title
CS 31400 Numerical Methods
CS 33400 Fundamentals of Computer Graphics
CS 35500 Introduction to Cryptography
CS 44800 Introduction to Relational Database Systems
CS 45600 Programming Languages
CS 47100 Introduction to Artificial Intelligence
CS 48300 Introduction to the Theory of Computation
One elective computer course at the 300, 400, 500 level or an independent study course approved by the track chair.
CS 352 - Compilers (REQ)
Difficulty level: 5.5 out of 5. Advanced look at 252.
Should not be taken concurrently with CS 354. The theory and practice of programming language translation, compilation, and run-time systems, organized around a significant programming project to build a compiler for a simple but nontrivial programming language. Modules, interfaces, tools. Data structures for tree languages. Lexical analysis, syntax analysis, abstract syntax. Symbol tables, semantic analysis. Translation, intermediate code, basic blocks, traces. Instruction selection, CISC and RISC machines. Liveness analysis, graph coloring register allocation. Supplemental material drawn from garbage collection, object-oriented languages, higher-order languages, dataflow analysis, optimization, polymorphism, scheduling and pipelining, memory hierarchies.
Learning Outcomes: 1. Provides students with an understanding of how a computer program is converted into elementary code that causes the computer to produce the output intended by the programmer.
Prerequisites:
Undergraduate level CS 25100 Minimum Grade of C and Undergraduate level CS 25200 Minimum Grade of C
CS 381 - Algorithms (REQ)
Difficulty: 4.8 out of 5
CS 38100 - Introduction To The Analysis Of Algorithms
Credit Hours: 3.00. Techniques for analyzing the time and space requirements of algorithms. Application of these techniques to sorting, searching, pattern-matching, graph problems, and other selected problems. Brief introduction to the intractable (NP-hard) problems.
Take what you are doing in CS 251 and prove it. 3/4 theory, technical brainstorming, math based.
Prerequisites: CS 251 and MA 261
CS 314 - Numerical Methods (ELECT)
CS 31400 - Numerical Methods
Credit Hours: 3.00. Iterative methods for solving nonlinear equations; direct and iterative methods for solving linear systems; approximations of functions, derivatives, and integrals; error analysis.
Fall/Summer only
Prerequisites: CS 180 and MA 265
CS 334 - Fundamentals Computer Graphics (ELECT)
CS 33400 - Fundamentals Of Computer Graphics
Credit Hours: 3.00. Fundamental principles and techniques of computer graphics. The course covers the basics of going from a scene representation to a raster image using OpenGL. Specific topics include coordinate manipulations, perspective, basics of illumination and shading, color models, texture maps, clipping and basic raster algorithms, fundamentals of scene constructions. CS 314 is recommended.
1/2 math, 1/2 programming
Prerequisites: CS 240 and MA 265
CS 355 - Intro to Cryptography (ELECT)
CS 35500 - Introduction To Cryptography
Credit Hours: 3.00. An introduction to cryptography basics: Classic historical ciphers including Caesar, Vigenere and Vernam ciphers; modern ciphers including DES, AES, Pohlig-Hellman, and RSA; signatures and digests; key exchange; simple protocols; block and stream ciphers; network-centric protocols.
Prerequisites: CS 251, MA 265 and/or STAT 350 can be taken concurrently
CS 182 material is a must to do well
Math heavy
CS 448 - Intro to Relational Database Systems (ELECT)
CS 44800 - Introduction To Relational Database Systems
Credit Hours: 3.00. An in-depth examination of relational database systems including theory and concepts as well as practical issues in relational databases. Modern database technologies such as object-relational and Web-based access to relational databases. Conceptual design and entity relationship modeling, relational algebra and calculus, data definition and manipulation languages using SQL, schema and view management, query processing and optimization, transaction management, security, privacy, integrity management.
Prerequisite: CS 251 (CS 348 recommended)
CS 456 - Programming Languages (ELECT)
CS 45600 - Programming Languages
Credit Hours: 3.00. Concepts for structuring data, computation, and whole programs. Object-oriented languages, functional languages, logic- and rule-based languages. Data types, type checking, exception handling, concurrent processes, synchronization, modularity, encapsulation, interfaces, separate compilation, inheritance, polymorphism, dynamic binding, subtyping, overloading, beta-reduction, unification.
Prerequisite: CS 352
CS 471 - Intro to Artificial Intelligence (ELECT)
CS 47100 - Introduction to Artificial Intelligence
Credit Hours: 3.00. Students are expected to spend at least three hours per week gaining experience with artificial intelligence systems and developing software. Basic problem-solving strategies, heuristic search, problem reduction and AND/OR graphs, knowledge representation, expert systems, generating explanations, uncertainty reasoning, game playing, planning, machine learning, computer vision, and programming systems such as Lisp or Prolog.
STAT 416 recommended before
Prerequisite: CS 251
CS 483 - Intro to Theory of Computation (ELECT)
CS 48300 - Introduction To The Theory Of Computation
Credit Hours: 3.00. Turing machines and the Church-Turing thesis; decidability; halting problem; reducibility; undecidable problems; decidability of logical theories; Kolmogorov complexity; time classes; P, NP, NP-complete; space classes; Savitch’s theorem, PSPACE-completeness, NL-completeness; hierarchy theorems; approximation theorems; probabilistic algorithms; applications of complexity to parallel computation and cryptography.
occasional offering
Prerequisite: CS 381
