PART 3: Programming Constructs

Compilers form the most important, as well as most complicated software ever designed.   In this course, our  emphasis is not so much on "writing yet another compiler for a toy language" but we shall expose you to the body of knowledge developed by Computer Scientists for designing the compilers.  This course is one of the "basic" courses in traditional computer science.  In the long term career of software engineer, this course should give you an "eye opener" view to exemplary approaches based on theoretical principles for clean software design of complex soft wares, and the design of efficient algorithms. Traditional applications of these techniques (in last two decades or so) are: database interfaces, document preparation and conversion, text analysis of biblical texts, corpora analysis, machine translation, typesetting chemical formulae, and chromosome recognition, etc.  Self-extracting search engines,  enabling architectures, VoiceXML (useful for the modeling of automated telephone call centers, the so called "talking heads" etc.), are a few applications in the last decade where the concepts in this course have extensively been used.

Plan of the lectures ( with links to video lectures )  COURSE REVIEW SLIDES

Sample questions on Compiler Techniques, MIPS Instruction Set   Optimizing Compilers,  Natural Language Processing,

 &&&&&&&&&&&********************

link to (audio + text) lectures on ALGORITHMS from Stony Brook Univ (Comp Sci deptt)

link to Microsoft Video library (contains various video lectures:  ranging from Engg & Comp Sci  Expository to Research level topics)

*********************************************************

My Book on Discrete Mathematics (published by Pearson - Prentice Hall, Singapore, Aug 2005) 
Sample questions on Discr Math,   Discrete Math I ,   Discr Math II,  Mathematics for Computation,  Logic and Proof,  Information Retrieval, Information Theory and Coding, Computational Number Theory

***********************************************************   
If I ran a school, I'd give the average grade to the ones who gave me all the right answers, for being good parrots. I'd give the top grades to those who made a lot of mistakes and told me about them, and then told me what they had learned from them.
                                   - R. Buckminster Fuller 

This subject introduces the basic concepts of logic, set theory, functions, relations and graph theory. The main focus is on understanding the concepts in formal terms and theoretical results. It also attempts to introduce various proof techniques.

 Upon completion of the subject, the student should be able to:

 1.                  Achieve a level of mathematical maturity necessary in formulating valid logical arguments in elementary mathematical terms, and have little difficulty in verifying the validity of logical arguments.

2.                  Introduced to foundational topics essential to subsequent mastery of other topics in the Computer Engineering curriculum.

3.            Develop and apply rigors, possibly abstraction as well, in the development of solutions of problems.

Course Details

 Course Introduction and Place for Discrete Strurctures in Computer Science. (1 lecture) 

Propositional  Logic (5 lectures) and valid arguments.  Predicate Logic (4 lectures): Quantified statements, multiple quantifiers, negations, valid arguments.. 

Basic Discrete Structures: Sets (2 lectures): Basic notations, set operations, partitions, Cartesian products, power sets. Relations (3 lectures) : n-ary relations and relational Databases; Binary relations; Reflexive, transitive and Symmetric relations.  Equivalences and Partitions.  Posets and Hasse Diagrams.

Proof Techniques:  Basic Proof techniques (1 to 1.5 formal lecture + 1 to 2 additional tut/review lectures) (direct proof, indirect proof, proof by contradiction, and exhaustive proof techniques), proof of quantified statements,  and Inductive proof techniques (1 to 1.5 lecture).  

( links to video lectures for earlier offering .... )  L1: 07 Aug 06    L2: 08 Aug 06   L3: 10 Aug 06  L4: 14 Aug 06  L5: 15 Aug 06  L6: 18 Aug 06   L7: 21 Aug 06  L8: 22 Aug 06 L10:25 Aug, L11:29 Aug (no recording?)   L11: 31 Aug 06  L12: 01 Sept 06 L13: 04 Sept 06  L14: 05 Sept 06 L15:08 Sept (no recording?)  L16: 12 Sept 06  L17:14 Sept, L18:15 Sept (no recording?)

Elementary number theory (1 lecture): Prime numbers; Modulo arithmetic operations, Eular Totient function.

Functions (4 lectures): Basic concepts, one-to-one and onto functions, Inverse functions, Pigeon hole Principles, compositions.

 Graph theory (8 lectures): Basic notions, degrees, paths, subgraphs, components, representations. Eulerian and Hamiltonian circuits. Graph Isomorphism. Trees : Rooted trees, binary trees

Recursion (4 lectures): Recursively defined sequences, general recursive definitions, solving recurrence relations by iteration, second-order linear homogeneous recurrence relations with constant coefficients.

Text:  (1) Narendra S. Chaudhari, Discrete Mathematics: A concise Introduction Pearson Prentice Hall, 2005.
(2) Grimaldi, R.P. Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Pearson Education (Addison Wesley) 2004.

References:  (1) Epp Sussana,  Discrete Mathematics with Applications, Third edition, Thomson learning: Brooks/Cole Pub. Co., 2004.

(2) Rosen: Discrete Mathematics and its applications, Fifth Edition Mc Graw Hill,  2003.

This subject has two parts. The first part is roughly same as CSC106, but covered at rapid pace.  Second part is introduction to standard topics in algorithms like analysis of algorithms, big-oh notation, etc.  Recursive algorithms for standard problems like tree traversal, Towers of Hanoi, and Quicksort, Mergesort.  Analysis of sorting and searching techniques (binary search, hash search).   
Sample Questions on:  Data Structures and Algorithms, Algorithms,  Complexity, Advanced Algorithms,  Algebraic Manipulation, Math Methods in computation, Computational Number Theory

This subject introduces the basic concepts of logic, set theory, functions, relations and graph theory. The main focus is on understanding the concepts in formal terms and theoretical results. It also attempts to introduce various proof techniques.