How to count really well (until we fall asleep. How to abstract using mathematical objects such as sets, relations, functions, trees and graphs. In this course, we will cover the mathematical foundations that will help us formulate solutions to some of the real problems above. Problems and it would be nice to see efficient solutions in thisĬentury. No one knows if there are easy solutions to these Some of these problems are really hard to solve using a computer. Write a program to check if a program is “correct” (keeps your instructor awake at night!). Write a program to play go (and play better than the best human champion?). Understand how to sequence the human genome.įind all the prime factors for really large number ( ). How many people are in this clique? Who are they? Search for web pages (better than google, bing or your favorite search engine?)įind the biggest clique on facebook. Route a packet reliably from one server to another on the internet (faster than existing protocols? even when routers can fail on us?)
That keep many computer scientists awake at night: Why Discrete Structures?Ĭomputer Science is all about solving interesting problemsĮfficiently and cheaply, using computers! Here are some real problems Will be foundational for future courses including algorithms,Īrtificial intelligence, programming languages, automata theory,Ĭomputer systems, cryptography, networks, computer/network security,ĭatabases, and compilers. The course covers fundamental ideas from discrete mathematics,Įspecially for computer science students. Trees, counting trees, Pruffer sequences and Catalan numbers Graph Theory: Basic introduction, paths, cycles, walks, tours, Eulerian toursĬonnected components, bipartite graphs, and coloring. Recursive Counting: Setting up recurrences Unordered Choice with replacement Quiz # 4 Permutations: Ordered choice with replacement.Ĭombinations: Unordered choice without replacementīinomial Theorem & Unordered with Replacement Growth of functions: Big-OH, Big-Omega and Big-Theta Quiz # 3įunctional Programming Lecture # 1: Devin Coughlinįunctional Programming Lecture # 2: William Mortlįunctional Programming Wrapup #3: Nick Vanderweit Types of relations: reflexive, symmetric, transitive, anti-symmetric, partial and total orders. Infinite sets, countability, degrees of infinity Sets: power sets, proving properties Functions and Relations Sets: cardinality, inclusion-exclusion principle, subsets Wrap up of induction: Induction on programs Induction proofs: weak and strong induction. Strategies for proving statements: universal statements, implications, existential statements. Implications and Primer on proofs (continued)Ĭommon mistakes during proofs. Implications, Converse, Contrapositives and a primer on proofs Models of Predicate Logic Formulas (continued). Start discussion on models of predicate logic. Wrap up propositional and predicate logic. Start predicate logic: predicates, quantifiers. Logic: Compound connectives (from previous lecture). No class due to campus holiday for Martin Luther King day Start Propositional Logic: Propositions, Connectives and Truth Tables Summations, Products (from previous lecture). Through them, and come prepared for class. Will strive to post all material well in advance. Post lecture notes for most topics and videos for selected topics. The schedule of lectures shown below is subject to change. Programming Assignment (Due date: Friday, Ap midnight ). Important Note: These problems are in addition to questions for onlineĪssignment that are posted on our private coursera site.Īssignment 1 (Due date: Jan 22nd, 2014 10 AM in class).Īssignment 2 (Due date: Jan 29nd, 2014 10 AM in class).Īssignment 3 (Due date: 10 AM in class).Īssignment 4 (Due date: 10 AM in class).Īssignment 5 (Due date: Ma 10 AM in class).Īssignment 6 (Due date: Ma 10 AM in class).Īssignment 7 (Due date: Ap 10 AM in class).Īssignment 8 (Due date: Monday, Ap 10 AM in class). One part online on Coursera private site and other part posted here. Special office hours on Tuesday from 12:30 - 2:00 PM Engg. : No class or office hours on monday Jan 20th, due to MLK day campus holiday. Quiz # 1 will be held on (Friday) (15 minutes, in class quiz covering assignments 1, 2). Quiz # 2 will be held on Friday (20 minutes, covering assignments 3,4). It will cover proofs by contradiction, pigeon hole principle, sets and functions. It will cover functions, relations, one-to-one onto functions, and different types of relations. It will cover all of combinatorics: counting, product rule, permutations, combinations, unordered counting, and binomial theorem.
0 kommentar(er)
