Prof. Alex Tuzhilin

KMEC 8-84

998-0832

atuzhili@stern.nyu.edu

Course Overview

The goal of the course is to provide students with sufficient background in a variety of topics in computer science to enable them to understand and possibly conduct research in technical areas of Information Systems. One of the immediate goals of the course is to develop sufficient technical skills so that the students could read intelligently and critically technical IS papers that they may encounter in the Rolling Reading seminars, in the technical IS courses and technical IS literature, and later on in their professional life.

After a general introduction to the research issues in technical Information Systems, the course will cover a broad set of topics in computer science, including set theory, computability, finite automata, Turing machines, analysis of algorithms, elements of logic, databases, coding and information theory.

Course Materials

The main book for the course is Discrete Mathematics for Computer Scientists by John Truss, 2nd edition, Addison-Wesley Publishing. Additional books for various topics are specified below.

There will be several homework assignments in the class and a take-home exam. The students are expected to do their assignments on time.

Class Schedule

Week 1: Research Issues in Technical Information Systems;

Sets, Relations, Functions

Reading: Chapters 1 and 3

Supplemental reading: Halmos, P. R. Naïve Set Theory. Van Nostrand, 1960.

Week 2 - 4: Elements of Theoretical Computer Science

Computable functions, Turing machines, grammars and finite automata

Reading: Chapter 9

Supplemental reading:

1. Davis, M. and Weyuker, E. Computability, Complexity, and Languages. Academic Press (Chapters 1-9.)

2. Hopcroft, J., Motwani, R. and Ullman, J. Introduction to Automata Theory, Languages, and Computation, 2^nd edition, Addison-Wesley.

Week 5 - 7: Introduction to Algorithms

Sorting, data structures (trees, hash tables, etc.), directed and undirected graphs, algorithm design techniques (divide-and-conquer, dynamic programming, greedy algorithms), analysis of algorithms and complexity theory.

Reading: Chapters 6, 8, 10.

Supplemental reading:

1. Cormen, T., Leiserson, C. and Rivest, R. Introduction to Algorithms. The MIT Press.

2. Aho, A., Hopcroft, J. and Ullman, J. Data Structures and Algorithms. Addison-Wesley.

Week 8 - 9: Logic

Overview of propositional logic; basic concepts of first-order logic (alphabet, well-formed formulas, interpretations, models, validity, satisfiability), logical consequence, axioms of first-order logic, deductions, soundness and completeness of deductive calculus, elements of logic programming.

Reading: Chapters 2 and 7.

Supplemental reading:

Enderton, H. A Mathematical Introduction to Logic. Academic Press.

Week 10 -- 12: Elements of Databases

I assume familiarity with the foundations of relational databases, including some basic knowledge of SQL and the elements of database design theory. This module will cover other aspects of relational databases and will focus on the theory of object-relational and deductive databases. We will also cover some basics of OLAP, data warehousing and physical database design.

Recommended books:

1. Garcia-Molina, H., Ullman, J. and Widom, J. Database systems: The Complete Book. Prentice Hall, 2001.

2. Ramakrishnan, R. and Gehrke, J. Database Management Systems, 3nd edition, McGraw-Hill, 2002.

3. Stonebreaker, M. and Brown, P. Object-relational DBMSs: Tracking the next great wave. 2nd edition, Morgan Kaufmann, 1999.

4. Abiteboul, S., Hull, R. and Vianu, V. Foundations of databases, Addison-Wesley, 1995.

Week 13 - 14: Coding and Information Theory

Basic concepts of coding theory, including error-correcting codes; elements of information theory, including the concepts of entropy and information, data compression, channel capacity and Shannon’s Theorem.

Reading: Chapter 11

Recommended books:

Cover, T. Elements of Information Theory, Wiley-Interscience, 1991.