# Lecture Notes for ENGR 213 - Discrete Structures-Comp Appl with Wang at Christopher Newport (CNU)

## Notes Information

 Material Type: Class Note Professor: Wang Class: ENGR 213 - Discrete Structures-Comp Appl Subject: Engineering University: Christopher Newport University Term: -- Keywords: Either...orContrapositivePropositionPropositionalExclusive OrConjunctionDefinitionsNecessary ConditionConsequenceSufficient Condition      ## Sample Document Text

Logic, Sets Section 1.1 Logic Logic 2 Introduction � Applications of discrete mathematics: � Formal Languages (computer languages) � Digital Circuits � Compiler Design � Data Structures � Computability � Algorithm Design � Relational Database Theory � Complexity Theory (counting) Logic 3 Example (counting) � The Traveling Salesman Problem, important in � Circuit design � Many other CS problems � Given: � n cities c 1 , c 2 , . . . , c n � Distance between city i and j, d ij � Find the shortest tour. Logic 4 Example (cont) � Assume a very fast PC: � 1 flop = 1 nanosecond = 10 -9 sec. = 1,000,000,000 ops/sec = 1 GHz. � A tour requires n-1 additions. How many different tours? � Choose the first city n ways, the second city n-1 ways, the third city n-2 ways, etc. Logic 5 Example (cont) � # tours = n (n-1) (n-2) . . . .(2) (1) = n! (Combinations) Total number of additions = (n-1) n! (Rule of Product) � If n=8, T(n) = 7.8! = 282,240 flops < 1/...

## Related Documents Definite Truth Values Notes Either...or Exam Social Security Tax Exam Either...or Exam Complicated Notes Valid Argument Exam Valid Argument Exam Either...or Notes Following Wffs Exam Either...or Notes Product Terms Notes     