Theory of Computing

EECS Professor Arvin Agah, left, and EECS doctoral student Christopher Redford have developed an innovative exchange in which interconnected sensor nodes provide simple summaries to the network in order to minimize power and costs.

EECS researchers are advancing the techniques for analyzing time and space complexity of software systems. They extend functional language technology, closing the gap between high level specifications and highly efficient implementations. Research in this area contributes to the understanding of basic techniques for specifying mathematical structures for describing software artifacts.

Associated Disciplines

 

Explore: Disciplines

Associated Programs

Associated Faculty

AT&T Foundation Distinguished Professor of Electrical and Computer Science and Director of the Information and Telecommunication Technology Center
785-864-8833
2022 Eaton Hall

Primary Research Interests

  • Formal Methods, Verification, and Synthesis
  • Trusted Computing
  • System-Level Design Languages and Semantics
  • Specification Languages
Associate Professor
785-864-8817
2024 Eaton Hall

Primary Research Interests

  • Functional Programming
  • Software Engineering
  • Compilers
  • Systems
  • FPGAs
785-864-4488
3014 Eaton Hall

Primary Research Interests

  • Knowledge Discovery
  • Data Mining
  • Machine Learning
  • Expert Systems
  • Reasoning Under Uncertainty
Associate Professor
785-864-7389
2038 Eaton Hall

Primary Research Interests

  • Algorithm Design and Analysis
  • Combinatorial Optimizations
  • Graph Algorithms
Associate Professor
785-864-8816
3016 Eaton Hall

Primary Research Interests

  • High Performance Scientific Computing Algorithms
  • Parallel Unstructured Mesh and Optimization Algorithms
  • Model Order Reduction
  • Computational Medicine
  • Image Processing

Associated Facilities

  • Computational cluster with over 1,000 processors connected to 37 TB of on-line storage

Program Objectives

  • Understand mathematical concepts of formal languages.
  • Understand techniques for analyzing time and space complexity of software systems.
  • Understand basic techniques for specifying mathematical structures for describing software artifacts.

Core Coursework (MS)

EECS 718 Graph Algorithms
This course introduces students to computational graph theory and various graph algorithms and their complexities. Algorithms and applications covered will include those related to graph searching, connectivity and distance in graphs, graph isomorphism, spanning trees, shortest paths, matching, flows in network, independent and dominating sets, coloring and covering, and Traveling Salesman and Postman problems. Prerequisite: EECS 560 or graduate standing with consent of instructor. LEC.

The class is not offered for the Spring 2019 semester.

EECS 762 Programming Language Foundation I
This course presents a basic introduction to the semantics of programming languages. The presentation begins with basic lambda calculus and mechanisms for evaluating lambda calculus terms. Types are introduced in the form of simply typed lambda calculus and techniques for type inference and defining type systems are presented. Finally, techniques for using lambda calculus to define, evaluate and type check common programming language constructs are presented. Prerequisite: EECS 662 or equivalent. LEC.

The class is not offered for the Spring 2019 semester.

EECS 764 Analysis of Algorithms
Models of computations and performance measures; asymptotic analysis of algorithms; basic design paradigms including divide-and-conquer, dynamic programming, backtracking, branch-and-bound, greedy method and heuristics; design and analysis of approximation algorithms; lower bound theory; polynomial transformation and the theory of NP-Completeness; additional topics may be selected from arithmetic complexity, graph algorithms, string matching, and other combinatorial problems. Prerequisite: EECS 660 or equivalent. LEC.
Spring 2019
Type Time/Place and Instructor Credit Hours Class #
LEC Zhong, Cuncong
TuTh 02:30-03:45 PM LEA 2111 - LAWRENCE
3 75478

Elective Coursework (MS)

EECS 649 Introduction to Artificial Intelligence
General concepts, search procedures, two-person games, predicate calculus and automated theorem proving, nonmonotonic logic, probabilistic reasoning, rule based systems, semantic networks, frames, dynamic memory, planning, machine learning, natural language understanding, neural networks. Prerequisite: Corequisite: EECS 368. LEC.
Spring 2019
Type Time/Place and Instructor Credit Hours Class #
LEC Williams, Andrew
W 06:10-09:00 PM LEEP2 2415 - LAWRENCE
3 75465
EECS 660 Fundamentals of Computer Algorithms
Basic concepts and techniques in the design and analysis of computer algorithms. Models of computations. Simple lower bound theory and optimality of algorithms. Computationally hard problems and the theory of NP-Completeness. Introduction to parallel algorithms. Prerequisite: EECS 560 and either EECS 461 or MATH 526. LEC.
Spring 2019
Type Time/Place and Instructor Credit Hours Class #
LEC Zhong, Cuncong
TuTh 08:00-09:15 AM EATN 2 - LAWRENCE
3 61233
EECS 662 Programming Languages
Formal definition of programming languages including specification of syntax and semantics. Simple statements including precedence, infix, prefix, and postfix notation. Global properties of algorithmic languages including scope of declaration, storage allocation, grouping of statements, binding time of constituents, subroutines, coroutines, and tasks. Run-time representation of program and data structures. Prerequisite: EECS 368 and EECS 388 and EECS 560. LEC.
Spring 2019
Type Time/Place and Instructor Credit Hours Class #
LEC Morris, John
TuTh 01:00-02:15 PM LEA 1136 - LAWRENCE
3 61234
EECS 738 Machine Learning
"Machine learning is the study of computer algorithms that improve automatically through experience" (Tom Mitchell). This course introduces basic concepts and algorithms in machine learning. A variety of topics such as Bayesian decision theory, dimensionality reduction, clustering, neural networks, hidden Markov models, combining multiple learners, reinforcement learning, Bayesian learning etc. will be covered. Prerequisite: Graduate standing in CS or CoE or consent of instructor. LEC.
Spring 2019
Type Time/Place and Instructor Credit Hours Class #
LEC Kuehnhausen, Martin
M 05:15-07:45 PM LEA 3153 - LAWRENCE
3 75477
EECS 742 Static Analysis
This course presents an introduction to techniques for statically analyzing programs. Converge includes theoretical analysis, definition and implementation of data flow analysis, control flow analysis, abstract interpretation, and type and effects systems. The course presents both the underlying definitions and pragmatic implementation of these systems. Prerequisite: EECS 665 or EECS 662 or equivalent. LEC.
Spring 2019
Type Time/Place and Instructor Credit Hours Class #
LEC Alexander, Perry
TuTh 01:00-02:15 PM LEA 3150 - LAWRENCE
3 78378
EECS 762 Programming Language Foundation I
This course presents a basic introduction to the semantics of programming languages. The presentation begins with basic lambda calculus and mechanisms for evaluating lambda calculus terms. Types are introduced in the form of simply typed lambda calculus and techniques for type inference and defining type systems are presented. Finally, techniques for using lambda calculus to define, evaluate and type check common programming language constructs are presented. Prerequisite: EECS 662 or equivalent. LEC.

The class is not offered for the Spring 2019 semester.

EECS 741 Computer Vision
This course gives a hands-on introduction to the fundamentals of computer vision. Topics include: image formation, edge detection, image segmentation, line-drawing interpretation, shape from shading, texture analysis, stereo imaging, motion analysis, shape representation, object recognition. Prerequisite: EECS 672 or EECS 744. LEC.

The class is not offered for the Spring 2019 semester.

EECS 755 Software Modeling and Analysis
Modern techniques for modeling and analyzing software systems. Course coverage concentrates on pragmatic, formal modeling techniques that support predictive analysis. Topics include formal modeling, static analysis, and formal analysis using model checking and theorem proving systems. Prerequisite: EECS 368 or equivalent. LEC.

The class is not offered for the Spring 2019 semester.

EECS 767 Information Retrieval
This class introduces algorithms and applications for retrieving information from large document repositories, including the Web. Topics span from classic information retrieval methods for text documents and databases, to recent developments in Web search, including: text algorithms, indexing, probabilistic modeling, performance evaluation, web structures, link analysis, multimedia information retrieval, social network analysis. Prerequisite: EECS 647 or permission of instructor. LEC.

The class is not offered for the Spring 2019 semester.

EECS 830 Advanced Artificial Intelligence
A detailed examination of computer programs and techniques that manifest intelligent behavior, with examples drawn from current literature. The nature of intelligence and intelligent behavior. Development of, improvement to, extension of, and generalization from artificially intelligent systems, such as theorem-provers, pattern recognizers, language analyzers, problem-solvers, question answerers, decision-makers, planners, and learners. Prerequisite: Graduate standing in the EECS department or Cognitive Science or permission of the instructor. LEC.

The class is not offered for the Spring 2019 semester.

EECS 837 Data Mining
Extracting data from data bases to data warehouses. Preprocessing of data: handling incomplete, uncertain, and vague data sets. Discretization methods. Methodology of learning from examples: rules of generalization, control strategies. Typical learning systems: ID3, AQ, C4.5, and LERS. Validation of knowledge. Visualization of knowledge bases. Data mining under uncertainty, using approaches based on probability theory, fuzzy set theory, and rough set theory. Prerequisite: Graduate standing in CS or CoE or consent of instructor. LEC.

The class is not offered for the Spring 2019 semester.

EECS 839 Mining Special Data
Problems associated with mining incomplete and numerical data. The MLEM2 algorithm for rule induction directly from incomplete and numerical data. Association analysis and the Apriori algorithm. KNN and other statistical methods. Mining financial data sets. Problems associated with imbalanced data sets and temporal data. Mining medical and biological data sets. Induction of rule generations. Validation of data mining: sensitivity, specificity, and ROC analysis. Prerequisite: Graduate standing in CS or CoE or consent of instructor. LEC.
Spring 2019
Type Time/Place and Instructor Credit Hours Class #
LEC Grzymala-Busse, Jerzy
TuTh 11:00-12:15 PM LEA 2133 - LAWRENCE
3 73453
EECS 843 Programming Language Foundation II
This course presents advanced topics in programming language semantics. Fixed point types are presented followed by classes of polymorphism and their semantics. System F and type variables are presented along with universal and existential types. The lambda cube is introduced along with advanced forms of polymorphism. Several interpreters are developed implementing various type systems and associated type inference algorithms. Prerequisite: EECS 762. LEC.

The class is not offered for the Spring 2019 semester.

EECS 940 Theoretic Foundation of Data Science
A review of statistical and mathematical principles that are utilized in data mining and machine learning research. Covered topics include asymptotic analysis of parameter estimation, sufficient statistics, model selection, information geometry, function approximation and Hilbert spaces. Prerequisite: EECS 738, EECS 837, EECS 844 or equivalent. LEC.

The class is not offered for the Spring 2019 semester.

EECS 776 Functional Programming and Domain Specific Languages
An introduction to functional programming. Topics include learning how to program in Haskell; IO and purity in software engineering; functional data structures and algorithms; monads and applicative functors; parsing combinators; Domain Specific Languages (DSLs) and DSL construction; advanced type systems; making assurance arguments; testing and debugging. Prerequisite: EECS 368 or equivalent or consent of instructor. LEC.

The class is not offered for the Spring 2019 semester.

Explore: EECS Courses


Department Events
KU Today
High school seniors can apply to the SELF Program, a four-year enrichment and leadership experience
Engineering students build concrete canoes, Formula race cars, unmanned planes, and rockets for competitions nationwide
More first and second place awards in student AIAA aircraft design contests than any other school in the world
One of 34 U.S. public institutions in the prestigious Association of American Universities
44 nationally ranked graduate programs.
—U.S. News & World Report
Top 50 nationwide for size of library collection.
—ALA
23rd nationwide for service to veterans —"Best for Vets," Military Times