Discrete Struc CECS 228
Popular in Course
Popular in Computer Science and Engineering
This 6 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 228 at California State University - Long Beach taught by Darin Goldstein in Fall. Since its upload, it has received 22 views. For similar materials see /class/218749/cecs-228-california-state-university-long-beach in Computer Science and Engineering at California State University - Long Beach.
Reviews for Discrete Struc
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/05/15
CECS 228 Discrete Structures With Computer Science Applications Darin Goldstein 1 Contact info 0 Instructor Darin Goldstein 0 Phone 5629851507 0 Email dgoldste csulbedu 0 Of ce ECS 546 0 Of ce hours MW 600630pm TTh 300330 pm 600630 pm HOW ever expect to be kicked out of my of ce 5 minutes beforehand so that I can make it to class on time You Will have priority during the of ce hours just before lecture Web page httpWWWcecscsulbedudaring Textbook Discrete Mathematics and Its Applications 6th Edition by Kenneth Rosen 2 Course Description Credits Credit for this course syllabus7 course materials7 etc all go to Todd Ebert the course coordinator for CECS 228 This course provides an introduction to the fascinating world of discrete mathematics in its relation to solving problems in computer science and engi neering The topics covered include logic set theory functions integers mod ular arithmetic mathematical reasoning and proofs recursive de nitions and algorithms basic counting principles relations graphs and trees 21 Course Objectives 0 An ability to model statements and systems using propositional and pred icate logic translate between English sentences and propositionalpredicate logic determine the consistency of a set of logical statements solve logic puzzles from a set of given statements 0 An ability to de ne a set and perform set operations nd the Cartesian product of sets and the power set of a given set represent a set as a binary vector and de ne vectorset operations recognize wellknown set identi ties and determine the relationship between two sets equal subset etc identify when a relationship between two sets represents a function nd the domain and range of a function and determine whether or not it is 11 onto or both describe the growth of a function using bigO notation nd composite and inverse functions use special functions including the oor and ceiling functions understand and write recursive de nitions and algorithms determine the cardinality of a set using the sum rule product rule principle of inclusionexclusion generalized pigeonhole principle per mutations and combinations solve linear recurrence relations represent a binary relation using set notation ordered pairs a directed graph and a matrix understand nary relations and their applications determine if a given relation is re exive irre exive symmetric antisymmetric asym metric and transitive determine if a relation on a given set is an equiva lence relation determine if a relation on a given set is a partial ordering apply equivalence relations and partial orderings to some common prob lems represent a graph using an adjacency list an adjacency matrix and an incidence matrix recognize some special graphs including complete graphs cycles wheels ncubes bipartite graphs use simple properties to rule out two graphs being isomorphic determine the connectivity of a given graph recognize a tree and compute various properties of a tree including internal vertices leaves and heig t An ability to apply a rule of inference in an argument construct an argument using rules of inference to show the conclusion is valid nd all possible conclusions one can deduce from a set of statements using rules of inference identify fallacies in an argument construct a mathematical proof using mathematical induction cases the direct method the indirect method and proof by contradiction prove the correctness of recursive algorithms and de nitions using mathematical induction 22 Topics Foundations Logic Propositional equivalences Predicates and quanti ers Sets Functions Algorithms Growth of functions and bigO notation 0 Mathematical Reasoning rules of inference and fallacies recursive de nitions recursive algorithms mathematical induction with application to correctness proof of recursive algorithms and de nitions mathematical proof techniques counting techniques recurrence relations 0 Basic Discrete Structures relations applications and representations equivalence relations partial orderings graphs terminology and appli cations representing graphs connectivity in graphs trees terminology and applications 3 Lectures Some good news for this course is that you will never be explicitly penalized for missing a lecture I will never give any popquizzes that are not announced at least the lecture beforehand You will be noti ed of any graded material other than quizzes at least two weeks in advance or else it will be mentioned somewhere in this page On the other hand this is de nitely a lecturebased course If you choose to miss a lecture I will not penalize you for it or hold it against you in any way but you are fully responsible for any material that I go over IfI mention something in lecture that is not in the book YOU ARE STILL RESPONSIBLE FOR KNOWING IT I will not redo a lecture for people that missed it the rst time It is your responsibility to get the notesinformation If you miss any kind of instructions about assignments that are given during lecture including but not limited to due dates methods for submission for assignments etc it is STILL your responsibility to be aware of what occurred in lecture 4 Grading Examquiz questions are not required to look anything like the homework ques tions Examsquizzes will be given to test whether you are able to APPLY the knowledge that you have learned The policies I follow in terms of grading short answer questions are as follows 0 Partial credit will only be given out for steps LEADING TO THE COR RECT ANSWER The answer itself is meaningless without clear reason ingi This means that if your reasoning is incorrect or not explicitly on the page the ANSWER BY ITSELF WILL NOT BE COUNTED AS CORRECT 0 Write out every step of your reasoning If it is not on the page you will not get credit for it Clearly mark out anything you don7t want gradedi If it is on your page and not crossed out it will be graded as if its part of your answer If there is more than one answer on your page I WILL GRADE THE INCORRECT ANSWER Points will be deducted for anything incorrect written on the page that is not crossed out even if the nal answer is correct For multiple choice questions you are required to get the answer entirely correct In other words if the answer is B an D and you choose only B or BCD or anything other than BD then your answer is incorrect No partial credit is given for multiple choice questions 5 Homework Quizzes Exams Programming As signments Homework will not be turned it However 1 highly recommend doing it if you want to do well on the exams If you choose not to do the homework you will not be explicitly penalized but you should plan on not doing well in the course The homework assignments are as follow Note that not all lectures have per fectly corresponding homework assignments so you may want to do the practice problems on the web site as well 0 Do problems 135 odd 4563 odd from Section 11 and problems 159 odd in Section 0 Section 13 145 odd 51 53 odd 0 Section 21 121 odd Section 22 141 odd 51 52 0 Section 21 2331 odd Section 82 19 odd 0 Do problems 119 odd from Section 23 0 Section 81 119 odd 2529 odd 33 0 Section 85 115 1947 odd 86 127 odd 91 119 odd 0 Section 92 125 odd 30 37 Section 93 3543 odd Section 94 111 odd 19 21 0 Section 101 123 odd Section 51 161 odd Section 52 119 odd Sections 53 141 odd 0 Section 54 125 odd Section 16 135 odd Section 43 117 odd 2339 odd The tentative breakdown for grading is as follows 1 Midterm 1 13 2 Midterm 2 13 3 Final Exam 13 The class will be graded on a curve Independent of the curve if you get 90 of the total points or above you get an automatic A 80 of the total points or above you get an automatic B and so on 1 do not round points The curve can only help your grade Usually independent of the actual score the top personpeople get As 1 then go down the grades and determine where the rst big break in the grades is and after the rst big break we start the 13 s This continues all the way down Generally speaking of ce hours are pretty crowded the day before exams l was a college student once and am very familiar with the concept of cramming for an exami During of ce hours I will try to help as many people as I can However the chances are pretty good that if you leave all of your questions for the last minute they may go unansweredi Please take this into account when you start your studyingi 6 Cheating You may not leave the room during any inclass exami You may not use any communication device cell phones etc during any inclass exami For takehome exams you are allowed to use calculators and any nonhuman help you need If you receive help in any way from any human being including any help at all from the Internet human help using an electronic or other intermediary is still considered human help it will be considered cheating and will be dealt with as outlined belowi If you have any questions about whether or not something is considered human help77 it is your responsibility to come see me before you receive such help You will not receive any leniency after the fact please consider this one of the rare occasions when it is easier to get permission than forgiveness Failure to observe these rules will result in an F in the course Cheating on any graded material in the course will lead to an automatic grade of F in the course I don7t give warningsi 7 The nal word If there is anything on this page that you have a question or comment about it is very important to let me know about it on the FIRST DAY OF CLASSES After the rst day of classes I will assume that you are aware of the grading policiesi Any grading misunderstandings you have after the rst day of classes are your responsibility Good luck 8 Syllabus These have a onetoone correspondence to lectures The lectures correspond to 1 Propositional Logic 2 Predicate Logic 3 Sets 4 i Functions 5 Review of lntegers i Midterm 1 gt10 Modular Arithmetic 5000 HHHHHHHH rooo ozmhuwm i Logical Reasoning Proofs i Mathematical Induction i Recursion i Midterm 2 i Basics of Counting i Permutations and Combinations i Introduction to Graphs i Trees i Relations i More on Relations i Final Exam Midterm 3