Discrete
Mathematics, Significance of Discrete Mathematics in Computer
Engineering, Sets–Naïve Set Theory (Cantorian Set Theory),
Axiomatic Set Theory, Need for Sets, Representation of Sets, Set
Operations, cardinality of set, principle of inclusion and exclusion,
Types of Sets –Countable and Uncountable Sets, Finite and
Infinite Sets, Countably Infinite and Uncountably Infinite Sets.
Introduction to bounded and unbounded sets and multiset. Countability
of Rational Numbers Using Cantor Diagonalization Argument, power
set. Propositional Logic logic, Propositional Equivalences,
Application of Propositional LogicTranslating English
Sentences, Proof by Mathematical Induction and Strong Mathematical
Induction.
Relations
and Their Properties, nary Relations and Their Applications,
Representing Relations ,Closures
of Relations, Equivalence Relations, Partial Orderings, partitions,
Hasse Diagram,Lattices,
Chains and AntiChains, Transitive Closure and Warshall‘s
Algorithm, nAry Relationsand
their Applications. Functions
Surjective, Injective and Bijective functions, Inverse Functions and
Compositions of Functions,
The Pigeonhole Principle.
Unit III:Counting (09 Hours)
The Basics of Counting, rule of Sum and Product, Permutations and Combinations, Binomial Coefficients and Identities, Generalized Permutations and Combinations, Algorithms for generating Permutations and Combinations.
Unit IV:Graph Theory (09 Hours)
Graphs
and Graph Models, Graph Terminology and Special Types of Graphs,
Representing
Graphs and Graph Isomorphism, Connectivity, Euler and
Hamilton Paths, Single source shortest
path Dijkstra's Algorithm,
Planar Graphs, Graph Colouring. Case Study Web Graph, Google
map.
Unit V:Trees (09 Hours)
Introduction,
properties of trees, Binary search tree, decision tree, prefix codes
and Huffman
coding, cut sets, Spanning Trees and Minimum Spanning
Tree, Kruskal‘s and Prim‘s algorithms,
The Max flow Min Cut
Theorem (Transport network). Case Study Game Tree, MiniMax Tree.
Unit VI:Algebraic Structures and Coding Theory (09 Hours)
The
structure of algebra, Algebraic Systems, Semi Groups, Monoids,
Groups, Homomorphism and Normal
Subgroups, and congruence relations, Rings, Integral Domains and
Fields, coding theory,
Polynomial Rings and polynomial Codes, Case
Study Brief introduction to Galois Theory –Field Theory
and Group Theory.
RAYMOND SMULLYAN (BORN 1919) Raymond Smullyan dropped out of high school. He wanted to study what he was really interested in and not standard high school material. After jumping from one university to the next, he earned an undergraduate degree in mathematics at the University of Chicago in 1955. He paid his college expenses by performing magic tricks at parties and clubs. He obtained a Ph.D. in logic in 1959 at Princeton, studying under Alonzo Church. After graduating from Princeton, he taught mathematics and logic at Dartmouth College, Princeton University, Yeshiva University, and the City University of New York. He joined the philosophy department at Indiana University in 1981 where he is now an emeritus professor. Smullyan has written many books on recreational logic and mathematics, including Satan, Cantor, and Infinity; What Is the Name of This Book?; The Lady or the Tiger?; Alice in Puzzleland; To Mock a Mockingbird;Forever Undecided; and The Riddle of Scheherazade: Amazing Logic Puzzles, Ancient and Modern. Because his logic puzzles are challenging, entertaining, and thoughtprovoking, he is considered to be a modernday Lewis Carroll. Smullyan has also written several books about the application of deductive logic to chess, three collections of philosophical essays and aphorisms, and several advanced books on mathematical logic and set theory. He is particularly interested in selfreference and has worked on extending some of Gödel’s results that show that it is impossible to write a computer program that can solve all mathematical problems. He is also particularly interested in explaining ideas from mathematical logic to the public. Smullyan is a talented musician and often plays piano with his wife, who is a concertlevel pianist. Making telescopes is one of his hobbies. He is also interested in optics and stereo photography. He states “I’ve never had a conflict between teaching and research as some people do because when I’m teaching, I’m doing research.” Smullyan is the subject of a documentary short film entitled This Film Needs No Title
In 1953 Augusta Ada’s notes on the
Analytic Engine were republished more than 100 years after they were
written, and after
they had been long forgotten. In his work in the
1950s on the capacity of computers to think (and his famous Turing
Test), Alan
Turing responded to Augusta Ada’s statement that “The
Analytic Engine has no pretensions whatever to originate anything. It
can do
whatever we know how to order it to perform.” This
“dialogue” between Turing and Augusta Ada is still the subject of
controversy.
Because of her fundamental contributions to computing,
the programming language Ada is named in honor of the Countess of
Lovelace.  ARISTOTLE (384 b.c.e.–322 b.c.e.) Aristotle was born in Stagirus (Stagira) in northern Greece. His father was the personal physician of the King of Macedonia. Because his father died when Aristotle was young, Aristotle could not follow the custom of following his father’s profession. Aristotle became an orphan at a young age when his mother also died. His guardian who raised him taught him poetry, rhetoric, and Greek. At the age of 17, his guardian sent him to Athens to further his education. Aristotle joined Plato’s Academy, where for 20 years he attended Plato’s lectures, later presenting his own lectures on rhetoric. When Plato died in 347 B.C.E. ,Aristotle was not chosen to succeed him because his views differed too much from those of Plato. Instead,Aristotle joined the court of King Hermeas where he remained for three years, and married the niece of the King. When the Persians defeated Hermeas, Aristotle moved to Mytilene and, at the invitation of King Philip of Macedonia, he tutored Alexander, Philip’s son, who later became Alexander the Great. Aristotle tutored Alexander for five years and after the death of King Philip, he returned to Athens and set up his own school, called the Lyceum. Aristotle’s followers were called the peripatetics, which means “to walk about,” because Aristotle often walked around as he discussed philosophical questions. Aristotle taught at the Lyceum for 13 years where he lectured to his advanced students in the morning and gave popular lectures to a broad audience in the evening. When Alexander the Great died in 323 B.C.E. , a backlash against anything related to Alexander led to trumpedup charges of impiety against Aristotle. Aristotle fled to Chalcis to avoid prosecution.He only lived one year in Chalcis, dying of a stomach ailment in 322 B.C.E .Aristotle wrote three types of works: those written for a popular audience, compilations of scientific facts, and systematic treatises. The systematic treatises included works on logic, philosophy, psychology, physics, and natural history. Aristotle’s writings were preserved by a student and were hidden in a vault where a wealthy book collector discovered them about 200 years later. They were taken to Rome, where they were studied by scholars and issued in new editions, preserving them for posterity. AUGUSTUS DE MORGAN (1806–1871) Augustus De Morgan was born in India, where his father was a colonel in the Indian army. De Morgan’s family moved to England when he was 7 months old. He attended private schools, where in his early teens he developed a strong interest in mathematics. De Morgan studied at Trinity College, Cambridge, graduating in 1827. Although he considered medicine or law, he decided on mathematics for his career. He won a position at University College, London, in 1828, but resigned after the college dismissed a fellow professor without giving reasons. However, he resumed this position in 1836 when his successor died, remaining until 1866. De Morgan was a noted teacher who stressed principles over techniques. His students included many famous mathematicians, including Augusta Ada, Countess of Lovelace, who was Charles Babbage’s collaborator in his work on computing machines. De Morgan was an extremely prolific writer, publishing more than 1000 articles in more than 15 periodicals. De Morgan also wrote textbooks on many subjects, including logic, probability, calculus, and algebra. In 1838 he presented what was perhaps the first clear explanation of an important proof technique known as mathematical induction, a term he coined. In the 1840s De Morgan made fundamental contributions to the development of symbolic logic. He invented notations that helped him prove propositional equivalences, such as the laws that are named after him. In 1842 De Morgan presented what is considered to be the first precise definition of a limit and developed new tests for convergence of infinite series. De Morgan was also interested in the history of mathematics and wrote biographies of Newton and Halley. In 1837 De Morgan married Sophia Frend, who wrote his biography in 1882. De Morgan’s research, writing, and teaching left little time for his family or social life. Nevertheless, he was noted for his kindness, humor, and wide range of knowledge. GEORGE
BOOLE (1815–1864) George Boole, the son of a cobbler, was born in
Lincoln, England, in November 1815. Because of his family’s
difficult financial situation, Boole struggled to educate himself
while supporting his family. Nevertheless, he became one of the most
important mathematicians of the 1800s. Although he considered a
career as a clergyman, he decided instead to go into teaching, and
soon afterward opened a school of his own. In his preparation for
teaching mathematics, Boole—unsatisfied with textbooks of his day
decided to read the works of the great mathematicians. While reading
papers of the great French mathematician Lagrange, Boole made
discoveries in the calculus of variations, the branch of analysis
dealing with finding curves and surfaces by optimizing certain
parameters.  JOHN WILDER TUKEY (1915–2000)Tukey, born in New Bedford, Massachusetts, was an only child. His parents, both teachers, decided home schooling would best develop his potential. His formal education began at Brown University, where he studied mathematics and chemistry. He received a master’s degree in chemistry from Brown and continued his studies at Princeton University, changing his field of study from chemistry to mathematics. He received his Ph.D. from Princeton in 1939 for work in topology, when he was appointed an instructor in mathematics at Princeton. With the start of World War II, he joined the Fire Control Research Office, where he began working in statistics. Tukey found statistical research to his liking and impressed several leading statisticians with his skills. In 1945, at the conclusion of the war, Tukey returned to the mathematics department at Princeton as a professor of statistics, and he also took a position at AT&T Bell Laboratories. Tukey founded the Statistics Department at Princeton in 1966 and was its first chairman. Tukey made significant contributions to many areas of statistics, including the analysis of variance, the estimation of spectra of time series, inferences about the values of a set of parameters from a single experiment, and the philosophy of statistics. However, he is best known for his invention, with J. W. Cooley, of the fast Fourier transform. In addition to his contributions to statistics, Tukey was noted as a skilled wordsmith; he is credited with coining the terms bit and software. Tukey
contributed his insight and expertise by serving on the President’s
Science Advisory Committee. He chaired several important committees
dealing with the environment, education, and chemicals and health. He
also served on committees working on nuclear disarmament. Tukey
received many awards, including the National Medal of Science.
HENRY MAURICE SHEFFER (1883–1964) Henry Maurice Sheffer, born to Jewish parents in the western Ukraine, emigrated to the United States in 1892 with his parents and six siblings. He studied at the Boston Latin School before entering Harvard, where he completed his undergraduate degree in 1905, his master’s in 1907, and his Ph.D. in philosophy in 1908. After holding a postdoctoral position at Harvard, Henry traveled to Europe on a fellowship. Upon returning to the United States, he became an academic nomad, spending one year eachat the University of Washington, Cornell, the University of Minnesota, the University of Missouri, and City College in New York. In 1916 he returned to Harvard as a faculty member in the philosophy department. He remained at Harvard until his retirement in 1952. Sheffer introduced what is now known as the Sheffer stroke in 1913; it became well known only after its use in the 1925 edition of Whitehead and Russell’s Principia Mathematica. In this same edition Russell wrote that Sheffer had invented a powerful method that could be used to simplify the Principia. Because of this comment, Sheffer was something of a mystery man to logicians, especially because Sheffer, who published little in his career, never published the details of this method, only describing it in mimeographed notes and in a brief published abstract. Sheffer was a dedicated teacher of mathematical logic. He liked his classes to be small and did not like auditors. When strangers appeared in his classroom, Sheffer would order them to leave, even his colleagues or distinguished guests visiting Harvard. Sheffer was barely five feet tall; he was noted for his wit and vigor, as well as for his nervousness and irritability. Although widely liked, he was quite lonely. He is noted for a quip he spoke at his retirement: “Old professors never die, they just become emeriti.” Sheffer is also credited with coining the term “Boolean algebra” (the subject of Chapter 12 of this text). Sheffer was briefly married and lived most of his later life in small rooms at a hotel packed with his logic books and vast files of slips of paper he used to jot down his ideas. Unfortunately, Sheffer suffered from severe depression during the last two decades of his life.
CHARLES
LUTWIDGE DODGSON (1832–1898) We know Charles Dodgson as Lewis
Carroll—the
pseudonym he used in his literary works. Dodgson, the
son of a clergyman, was the third of 11 children,all
of whom stuttered. He was uncomfortable in the company of adults and
is said to have spoken without
stuttering only to young girls, many
of whom he entertained, corresponded with, and photographed
(sometimes
in poses that today would be considered inappropriate).
Although attracted to young girls, he was extremely
puritanical and
religious. His friendship with the three young daughters of Dean
Liddell led to his writing Alice
in Wonderland, which brought him
money and fame.
Dodgson graduated from Oxford in 1854 and obtained
his master of arts degree in 1857. He was appointed
lecturer in
mathematics at Christ Church College, Oxford, in 1855. He was ordained in the Church of England in 1861 but never practiced his ministry. His writings published under this real name include articles and books on geometry, determinants, and the mathematics of tournaments and elections. (He also used the pseudonym Lewis Carroll for his many works on recreational logic.)
