Language, Logic, and Discrete Mathematics

Course Composition and Objectives

• Set , Relations, Functions, Numbers
  • Students will understand set operations, applications of relations, equivalence relations, function composition, inverse functions, logarithms, exponential function, number systems, applications of number theory.
  • Students will apply understandings of sets, relations, functions, and numbers to mathematical data types (integers, fractions, real numbers, tuples, function spaces); exponential growth; non-feasible algorithms; and/or public key encryption.
• Logic and Boolean Algebra
  • Students will understand predicates, quantifiers, formulas, interpretations, syllogisms, logical consequence, tableau method, Boolean connectives, Boolean functions, valuations, truth tables, and logic gates.
  • Students will apply understandings of logic and Boolean algebra to database query languages, specification languages, switching circuits, and/or Boolean search expressions.
• Combinatorics and Probability
  • Students will understand combination, permutation, and discrete probability.
  • Students will apply understandings of combinatorics and probability to lexicographic ordering, combinatorial explosions, lower bounds of algorithms, and/or reliability of computer systems .
• Graphs and Trees 
  • Students will understand directed and undirected graphs, weighted graphs, walks, paths, matrix representations, graph algorithms, spanning trees, rooted and structured trees, combining trees to form new trees, inserting nodes in trees, sorting, and searching.
  • Students will apply understandings of graphs and trees to flow diagrams, task scheduling, critical paths, network connectivity, finite state machines, parsing, derivation, and/or trees as data structures for storing information.
• Induction and Recursion
  • Students will understand induction and recursion on the natural numbers and other structures such as trees.
  • Students will apply understandings of induction and recursion to recursive evaluation of mathematical and Boolean expressions, recursive searching and sorting algorithms, and/or asymptotic analysis of algorithms.
• Grammars, Languages, and Finite State Machines
  • Students will understand alphabets, strings, grammars, languages, regular languages, regular expressions, finite state machines, and language recognizers.
  • Students will apply understandings of grammars, languages, and finite state machines to regular expression search and/or efficient pattern matching using finite-state machines.
• Instructors Choice: Instructors may choose topics and learning objectives that meet the spirit of the course as defined here. Instructors may choose to devote more time to the learning objectives listed above or to add additional, complimentary objectives. Supplementary material and objectives should not overlap with the defined content of other courses in the curriculum.

Course Description

IST 230 is one of the five introductory core courses for the baccalaureate degree program in Information Sciences and Technology. The purpose of IST 230 is to provide students with an understanding of an array of mathematical concepts and methods which form the foundation of modern information science, in a form that will be relevant and useful for IST students. Exams and assignments will be used to assess that understanding.

IST 230 will draw some of its material from several mathematical disciplines: formal language theory, mathematical logic, discrete mathematics. In-depth treatments of each of these subjects are offered elsewhere in the University as advanced mathematics and computer science courses. The difference is that IST 230 will present these concepts in a more elementary way, with much more emphasis on IST applications, and in a more eclectic, web-based format.