Answers.Body: <p>The one thing I would <em>not</em> do is create a separate Math course oriented towards computer programming. A purely-math course with no programming is probably the best way to kill interest in one or the other. </p>
  
  <p>Introduce the math where it naturally fits in as you teach algorithmic concepts for real situations -- actual projects in your courses. Most programmers think no more about 'math' as a subject than Chefs think about Thermodynamics: they don't have to!</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-07T15:17:05.893Z
Answers.Text: I think your answer has validity, but I also note that most university curricula do, actually, have a discrete math course that is required of CS majors. It may be taught either by mathematicians (less programming) or by computer scientists (hopefully, more). In a similar vein, some university programs require at least some Calculus, usually from the math department. There are tradeoffs, of course. At a minimum, courses from the math department may give an alternate way of looking at problems - a good thing.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-07T16:45:50.643Z
Answers.Text: Welcome to [cseducators.se]! Your answer is quite interesting; If you could expand just a bit more upon your answer, it would surely be of higher quality.
Answers.UserDisplayName: ItamarG3
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-07T14:49:35.783Z
Answers.LastActivityDate: 2018-02-07T14:49:35.783Z
Answers.UserDisplayName: user4270
Answers.Body: <p>In the search for a "core set of concepts that is <em>discrete mathematics</em> as it applies to the study of Computer Science," I kept finding nebulous ideas, without concrete parameters. There seems to be a general consensus that there <em>is</em> the need for a firm foundation in discrete mathematics when studying CS. There is also a broad agreement that "graph theory, and other topics" is part of that foundation. Unfortunately the <em>other topics</em> portion of the requirements are seldom well specified, and seemingly never delineated with any specificity.</p>
  
  <p>I recognize that the question is in a high school (USA ages ~ 15-18) context. Be that as it may I've settled on a source from the university context for a solid, definitive, and delineated set of "core discrete mathematics material" to set as a touchstone.</p>
  
  <p><a href="https://www.williams.edu/" rel="noreferrer" title="Williams College home page">Williams College</a> requires that students who select "Computer Science" as their major demonstrate a proficiency in discrete mathematics. This requirement is usually met with a "C", or better, grade in their MATH 200 course. In Spring 2017, the Computer Science department added an alternate method of satisfying the requirement: A "Discrete Mathematics Proficiency Exam."</p>
  
  <p><a href="https://en.wikipedia.org/wiki/Williams_College" rel="noreferrer" title="Williams College entry on Wikipedia">Williams</a> is classified as "<a href="https://www.usnews.com/best-colleges/williams-college-2229" rel="noreferrer" title="U.S. News &amp; World Report article on Williams College">most selective</a>" by U.S. News &amp; World Report, admitting less than 20% of the applicants each year. As such it is expected that they have set standards, in all areas, rather high. However, I prefer to avoid the dangers alluded to by <a href="https://www.exkalibur.com/mondays-quote-week-sept-5/mon-quote-aim-too-low/" rel="noreferrer" title="Attributed to Michelangelo">Michelangelo</a> (<a href="https://en.wikiquote.org/wiki/Michelangelo#Disputed" rel="noreferrer" title="Maybe it was not said by Michelangelo, maybe not">disputed</a>): <em>The greatest danger for most of us is not that our aim is too high and we miss it, but that it is too low and we reach it.</em> If I were to choose a target, aiming "high" has the advantage that I might reach the target. If I fail to reach the target, I will know how high I can go. If the aim is low, however, and I reach <em>that</em> target, I still will not know if I <em>could have</em> reached higher. Therefore, using the <a href="https://csci.williams.edu/discrete-mathematics-preparation/" rel="noreferrer" title="Preparation for the Discrete Mathematics Proficiency Exam at Williams College">materials</a> from Williams College as a guide for a high school course seems worthwhile.</p>
  
  <p>All that being said, here is the "short list" of their subject areas, (taken from their <a href="https://csci.williams.edu/discrete-mathematics-preparation/" rel="noreferrer" title="Preparation for the Discrete Mathematics Proficiency Exam at Williams College">Preparing for the exam</a> web page.)</p>
  
  <ul>
  <li>Sets, Relations, and Functions</li>
  <li>Basic Logic</li>
  <li>Proof Techniques</li>
  <li>Basics of Counting</li>
  <li>Discrete Probability</li>
  <li>Measuring Algorithm Complexity</li>
  <li>Graphs and Trees</li>
  </ul>
  
  <p>There is, most assuredly, a lot of ground to cover there, and it does not look any "easier" with a full breakdown. The referenced web page (<a href="https://csci.williams.edu/discrete-mathematics-preparation/" rel="noreferrer" title="Preparation for the Discrete Mathematics Proficiency Exam at Williams College">ibid.</a>) lists a breakdown of the topics followed by the  learning outcomes. I think the learning outcomes likely to be more significant in answering the OP's instant question, and have reproduced them with their subjects below.</p>
  
  <hr>
  
  <h1>TL;DNR</h1>
  
  <p>The seven areas above have following <em>learning outcomes</em> listed in the <a href="https://csci.williams.edu/discrete-mathematics-preparation/" rel="noreferrer" title="Preparation for the Discrete Mathematics Proficiency Exam at Williams College">cited materials</a>:</p>
  
  <blockquote>
    <h3>Sets, Relations, and Functions</h3>
    
    <p><em>Learning Outcomes:</em></p>
    
    <ul>
    <li>Define, as well as explain with examples, the basic terminology of functions, relations, and sets.
    
    <ul>
    <li>Perform the operations associated with sets, functions, and relations.</li>
    <li>Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.</li>
    </ul></li>
    </ul>
    
    <h3>Basic Logic</h3>
    
    <p><em>Learning Outcomes:</em></p>
    
    <ul>
    <li>Convert logical statements from informal language to propositional (and quantified) logic expressions.
    
    <ul>
    <li>Apply formal methods of symbolic propositional logic, such as calculating validity of formulae and computing normal forms.</li>
    <li>Use the rules of inference to construct proofs in propositional logic.</li>
    </ul></li>
    </ul>
    
    <h3>Proof Techniques</h3>
    
    <p><em>Learning Outcomes:</em></p>
    
    <ul>
    <li>Identify the proof technique used in a given proof.
    
    <ul>
    <li>Outline the basic structure of each proof technique described in this unit.</li>
    <li>Apply each of the proof techniques correctly in the construction of a sound argument.</li>
    <li>Determine which type of proof is best for a given problem.</li>
    <li>Explain the parallel between ideas of mathematical induction to recursion and recursively defined sequences.</li>
    <li>Explain the relationship between weak and strong induction and give examples of the appropriate use of each.</li>
    <li>State the well-ordering principle and its relationship to mathematical induction.</li>
    </ul></li>
    </ul>
    
    <h3>Basics of Counting</h3>
    
    <p><em>Learning Outcomes:</em></p>
    
    <ul>
    <li>Apply counting arguments, including sum and product rules, inclusion-exclusion principle and arithmetic/geometric progressions.
    
    <ul>
    <li>Apply the pigeonhole principle in the context of a formal proof.</li>
    <li>Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application.</li>
    <li>Map real-world applications to appropriate counting formalisms, such as determining the number of ways to arrange people around a table, subject to constraints on the seating arrangement, or the number of ways to determine certain hands in cards (e.g., a full house).</li>
    <li>Solve a variety of basic recurrence relations.</li>
    <li>Analyze a problem to determine underlying recurrence relations.</li>
    <li>Perform computations involving modular arithmetic.</li>
    </ul></li>
    </ul>
    
    <h3>Discrete Probability</h3>
    
    <p><em>Learning Outcomes:</em></p>
    
    <ul>
    <li>Calculate probabilities of events for elementary problems such as games of chance.
    
    <ul>
    <li>Differentiate between dependent and independent events.</li>
    <li>Make a probabilistic inference in a real-world problem using Bayes’ theorem to determine the probability of a hypothesis given evidence.</li>
    </ul></li>
    </ul>
    
    <h3>Measuring Algorithm Complexity</h3>
    
    <p><em>Learning Outcomes:</em></p>
    
    <ul>
    <li>Be able to meaningfully compare the asymptotic growths of pairs of functions.</li>
    </ul>
    
    <h3>Graphs and Trees</h3>
    
    <p><em>Learning Outcomes:</em></p>
    
    <ul>
    <li>Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each type of graph/tree.
    
    <ul>
    <li>Be able to prove elementary results about graphs and trees, such as:</li>
    <li>In any graph, the sum of the degrees of the vertices equals twice the number of edges.</li>
    <li>In any tree, the number of edges is one less than the number of vertices.</li>
    <li>Model a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system.</li>
    </ul></li>
    </ul>
  </blockquote>
  
  <p><sup>Source: <a href="https://csci.williams.edu/discrete-mathematics-preparation/" rel="noreferrer" title="Preparation for the Discrete Mathematics Proficiency Exam at Williams College">Discrete Mathematics Preparation</a> from Williams College <a href="https://csci.williams.edu/" rel="noreferrer">Computer Science Department</a></sup></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-22T05:47:22.013Z
Answers.LastActivityDate: 2018-05-22T05:47:22.013Z
Answers.UserDisplayName: Gypsy Spellweaver
Answers.Body: <p>I'd say graph theory lies right in the sweet spot of the intersection of Discrete Math and CS - in fact, at my own university, the idea of graphs are introduced in CS courses before it goes into more depth in later math courses (in an intro to combinatorics course). There are some intuitive ways to provide motivation for the topics (e.g. path finding and taxonomy intuitively <em>feel</em> like they should be modeled with graphs and trees respectively), and then there are some problems which at first glance <em>don't</em> feel like they have anything to do with graphs, but one can interpret the problem as a graph - scheduling problems and graph colourings, or a node representing the state of a puzzle/game and edges representing actions being done in this puzzle/game, connecting to the node representing the state after the action is done.</p>
  
  <p>With the puzzles example, for appropriate puzzles, this representation could be used to "brute force" a solution to said puzzle, e.g. a Rubik's cube or sudoku. The "actions" for a Rubik's would be the possible rotations of the cube. The "actions" for a sudoku might be to fill in one of the empty boxes with some number. An important distinction between these two examples is that in a Rubik's cube, we can return to a state we previously had - the graph formed has cycles in it, so we have to take that into account. In the sudoku example, because we ALWAYS fill in a box with a number, the number of empty spaces always decreases by 1 for each "action" (we never <em>erase</em> a number), thus our graph representing the Sudoku puzzle's possible solutions is acyclic. In both, we'd like to stop our actions once the puzzle has been "solved", which we'd have to check for. Also, note that both graphs are directed graphs.</p>
  
  <p>There's a bunch more to be said about applications of graphs... What's important is, as the other answer points out, not just <em>learning</em> about graphs, but actually programming some algorithms with them. </p>
  
  <p>You may also want to cover some basic propositional logic and (finite) set theory. Reasoning about abstract logical statements as well as sets is fundamental to computer science just as it is mathematics. Unfortunately it may feel too abstract for some students... I had to take a CS course in Logic, and for part of this course, we used the proof assistant Coq (<a href="https://en.wikipedia.org/wiki/Coq" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Coq</a>). Unlike writing mathematical proofs by hand, writing in Coq feels more like writing a program (which is because Coq is (in a sense) <em>also a programming language</em>), and this might be a way to cater it to CS students - proving is programming.  </p>
  
  <p>Might add more stuff here if I can think of it... Thinking of linear algebra, which some mysteriously classify as discrete math. My high school used to do this, though I'll admit it has a discrete "feeling" to it versus Calculus or Analysis, and it also <em>can be</em> truly discrete with finite fields, or finite modules over a (discrete) ring. Maybe transformation matrixes being used in computer graphics, with 2D and/or 3D focus depending on the class's maturity. Not sure if this is the right fit for what you want though...</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-11T09:15:19.353Z
Answers.LastActivityDate: 2018-02-11T09:15:19.353Z
Answers.UserDisplayName: Umer Amjad
Answers.Body: <p>This question is hard to answer and especially hard to provide a <em>complete</em> answer. There are a lot of things that are good to know if you work with computers, though not everyone will use everything on anyone's list of favorites. </p>
  
  <p>However, some sorts of discrete/finite math are especially useful as they are useful for building models, independent of computers. The models can be programmed to solve useful problems in the world. I'll mention a few here. </p>
  
  <p>The basic idea here is that the more ways you have to <em>approach</em> a problem, the more likely it is that you can provide a solution. Even an approximate solution is often enough, especially in situations of uncertainty or when there are many variables and many constraints. </p>
  
  <p><a href="https://en.wikipedia.org/wiki/Markov_chain" rel="nofollow noreferrer">Markov Chains</a> and Markov Processing. These describe dynamic systems in which changes depend on only the current state and not a history. </p>
  
  <p><a href="https://en.wikipedia.org/wiki/Linear_programming" rel="nofollow noreferrer">Linear Programing</a>, and especially Integral Linear Programming where solutions must be integers. These are used for all sorts of optimization problems where constraints must be observed. </p>
  
  <p>Discrete Probability and <a href="https://en.wikipedia.org/wiki/Combinatorics" rel="nofollow noreferrer">Combinatorics</a> which has entries to many related fields (Graph Theory, Coding Theory, ...)</p>
  
  <p><a href="https://en.wikipedia.org/wiki/Decision_theory" rel="nofollow noreferrer">Decision Theory</a> and <a href="https://en.wikipedia.org/wiki/Decision_tree" rel="nofollow noreferrer">Decision Trees</a>, often used in algorithm design. Modeling under uncertainty. </p>
  
  <p><a href="https://en.wikipedia.org/wiki/Set_theory" rel="nofollow noreferrer">Set Theory</a> and, more generally, Mathematical Logic, used ubiquitously in programming and in Theoretical CS. </p>
  
  <p><a href="https://en.wikipedia.org/wiki/Game_theory" rel="nofollow noreferrer">Vectors and Matrices</a> (not strictly discrete, of course) but often used in proofs and models, especially models of physical systems. </p>
  
  <p><a href="https://en.wikipedia.org/wiki/Game_theory" rel="nofollow noreferrer">Game Theory</a>, again used in modeling and in predicting outcomes in complex situations. </p>
  
  <p><a href="https://en.wikipedia.org/wiki/Number_theory" rel="nofollow noreferrer">Number Theory</a> used in many things, especially cryptology. </p>
  
  <hr>
  
  <p>Often such courses are, indeed, best taught by mathematicians. But it is also possible for a CS department to negotiate with the Math department on content. Even more radical, is a collaborative course, taught jointly by a mathematician and a computer scientist in which programming is used to enhance the material and make it more concrete. It is also possible for it to be  team-project course in which different teams work on different problems, each emphasizing some different sort of mathematical modeling. A joint wrap up (science fair) can be very valuable. </p>
  
  <p>Also note that any of these topics could be a full course (or more). Some small subset of topics from several of these areas is enough to make up a course. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-11T13:32:24.293Z
Answers.LastActivityDate: 2018-02-11T15:11:08.937Z
Answers.LastEditDate: 2018-02-11T15:11:08.937Z
Answers.UserDisplayName: Buffy
Body: <p>Is there an accepted core set of concepts that is <em>discrete mathematics</em> as it applies to the study of Computer Science? The math department in my school is thinking about creating a course, they asked for our input, and I wasn't sure what to point them to.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-04T09:27:14.287Z
Comments.Text: See this for english A-level (level-3, below 1st year undergrad) spec. It has some modules that it calls decision maths. This spec has been superseded the new one does not seem to have these modules.
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-04T17:40:58.420Z
Comments.Text: @ctrl-alt-delor Are you missing a link from this comment?
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-04T21:59:44.900Z
Comments.Text: sorry here is the link http://www.aqa.org.uk/subjects/mathematics/as-and-a-level/mathematics-6360 (I also not I said English A-level. Which as what I meant the Maths A-level in England. However in England “English A-level” means an A-level in literature and/or language, in the native language of English.
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-05T09:26:42.587Z
Comments.Text: I self-studied two modules (well, one and a half, because I couldn't find any materials for the other half) of "discrete maths" as part of Further Maths A-level, and some "discrete maths" in the first year of undergraduate CS. They were about completely unrelated topics. Given the ambiguity of the word "*school*", which of the two courses would be relevant to this question?
Comments.UserDisplayName: Peter Taylor
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-21T16:39:20.503Z
Comments.Text: Let me note here that MathEducators has several questions on discrete mathematics, some of which are relevant here: https://matheducators.stackexchange.com/questions/tagged/discrete-math. MathEducators in general overlaps with this site on all similar questions. Check it out.
Comments.UserDisplayName: Buffy
Tags: <secondary-education><undergraduate><discrete-math>
Title: What are the core concepts of discrete mathematics within CS?
ThreadText: # What are the core concepts of discrete mathematics within CS?
  
  (Asked by: username_0 on 2018-02-04)
  
  Is there an accepted core set of concepts that is *discrete mathematics* as it applies to the study of Computer Science? The math department in my school is thinking about creating a course, they asked for our input, and I wasn't sure what to point them to.
  
  **Tags:** secondary-education, undergraduate, discrete-math
  
  > **Comments:**
  > **username_1**: See this for english A-level (level-3, below 1st year undergrad) spec. It has some modules that it calls decision maths. This spec has been superseded the new one does not seem to have these modules.  
  > **username_0**: @username_1 Are you missing a link from this comment?  
  > **username_1**: sorry here is the link http://www.aqa.org.uk/subjects/mathematics/as-and-a-level/mathematics-6360 (I also not I said English A-level. Which as what I meant the Maths A-level in England. However in England “English A-level” means an A-level in literature and/or language, in the native language of English.  
  > **username_2**: I self-studied two modules (well, one and a half, because I couldn't find any materials for the other half) of "discrete maths" as part of Further Maths A-level, and some "discrete maths" in the first year of undergraduate CS. They were about completely unrelated topics. Given the ambiguity of the word "*school*", which of the two courses would be relevant to this question?  
  > **username_3**: Let me note here that MathEducators has several questions on discrete mathematics, some of which are relevant here: https://matheducators.stackexchange.com/questions/tagged/discrete-math. MathEducators in general overlaps with this site on all similar questions. Check it out.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_6 on 2018-05-22. Score: 5 | Accepted answer
  
  In the search for a "core set of concepts that is *discrete mathematics* as it applies to the study of Computer Science," I kept finding nebulous ideas, without concrete parameters. There seems to be a general consensus that there *is* the need for a firm foundation in discrete mathematics when studying CS. There is also a broad agreement that "graph theory, and other topics" is part of that foundation. Unfortunately the *other topics* portion of the requirements are seldom well specified, and seemingly never delineated with any specificity.
  
  I recognize that the question is in a high school (USA ages ~ 15-18) context. Be that as it may I've settled on a source from the university context for a solid, definitive, and delineated set of "core discrete mathematics material" to set as a touchstone.
  
  [Williams College](https://www.williams.edu/ "Williams College home page") requires that students who select "Computer Science" as their major demonstrate a proficiency in discrete mathematics. This requirement is usually met with a "C", or better, grade in their MATH 200 course. In Spring 2017, the Computer Science department added an alternate method of satisfying the requirement: A "Discrete Mathematics Proficiency Exam."
  
  [Williams](https://en.wikipedia.org/wiki/Williams_College "Williams College entry on Wikipedia") is classified as "[most selective](https://www.usnews.com/best-colleges/williams-college-2229 "U.S. News & World Report article on Williams College")" by U.S. News & World Report, admitting less than 20% of the applicants each year. As such it is expected that they have set standards, in all areas, rather high. However, I prefer to avoid the dangers alluded to by [Michelangelo](https://www.exkalibur.com/mondays-quote-week-sept-5/mon-quote-aim-too-low/ "Attributed to Michelangelo") ([disputed](https://en.wikiquote.org/wiki/Michelangelo#Disputed "Maybe it was not said by Michelangelo, maybe not")): *The greatest danger for most of us is not that our aim is too high and we miss it, but that it is too low and we reach it.* If I were to choose a target, aiming "high" has the advantage that I might reach the target. If I fail to reach the target, I will know how high I can go. If the aim is low, however, and I reach *that* target, I still will not know if I *could have* reached higher. Therefore, using the [materials](https://csci.williams.edu/discrete-mathematics-preparation/ "Preparation for the Discrete Mathematics Proficiency Exam at Williams College") from Williams College as a guide for a high school course seems worthwhile.
  
  All that being said, here is the "short list" of their subject areas, (taken from their [Preparing for the exam](https://csci.williams.edu/discrete-mathematics-preparation/ "Preparation for the Discrete Mathematics Proficiency Exam at Williams College") web page.)
  
  * Sets, Relations, and Functions
  * Basic Logic
  * Proof Techniques
  * Basics of Counting
  * Discrete Probability
  * Measuring Algorithm Complexity
  * Graphs and Trees
  
  There is, most assuredly, a lot of ground to cover there, and it does not look any "easier" with a full breakdown. The referenced web page ([ibid.](https://csci.williams.edu/discrete-mathematics-preparation/ "Preparation for the Discrete Mathematics Proficiency Exam at Williams College")) lists a breakdown of the topics followed by the learning outcomes. I think the learning outcomes likely to be more significant in answering the OP's instant question, and have reproduced them with their subjects below.
  
  ---
  
  # TL;DNR
  
  The seven areas above have following *learning outcomes* listed in the [cited materials](https://csci.williams.edu/discrete-mathematics-preparation/ "Preparation for the Discrete Mathematics Proficiency Exam at Williams College"):
  
  > ### Sets, Relations, and Functions
  >
  > *Learning Outcomes:*
  >
  > * Define, as well as explain with examples, the basic terminology of functions, relations, and sets.
  >   + Perform the operations associated with sets, functions, and relations.
  >   + Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.
  >
  > ### Basic Logic
  >
  > *Learning Outcomes:*
  >
  > * Convert logical statements from informal language to propositional (and quantified) logic expressions.
  >   + Apply formal methods of symbolic propositional logic, such as calculating validity of formulae and computing normal forms.
  >   + Use the rules of inference to construct proofs in propositional logic.
  >
  > ### Proof Techniques
  >
  > *Learning Outcomes:*
  >
  > * Identify the proof technique used in a given proof.
  >   + Outline the basic structure of each proof technique described in this unit.
  >   + Apply each of the proof techniques correctly in the construction of a sound argument.
  >   + Determine which type of proof is best for a given problem.
  >   + Explain the parallel between ideas of mathematical induction to recursion and recursively defined sequences.
  >   + Explain the relationship between weak and strong induction and give examples of the appropriate use of each.
  >   + State the well-ordering principle and its relationship to mathematical induction.
  >
  > ### Basics of Counting
  >
  > *Learning Outcomes:*
  >
  > * Apply counting arguments, including sum and product rules, inclusion-exclusion principle and arithmetic/geometric progressions.
  >   + Apply the pigeonhole principle in the context of a formal proof.
  >   + Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application.
  >   + Map real-world applications to appropriate counting formalisms, such as determining the number of ways to arrange people around a table, subject to constraints on the seating arrangement, or the number of ways to determine certain hands in cards (e.g., a full house).
  >   + Solve a variety of basic recurrence relations.
  >   + Analyze a problem to determine underlying recurrence relations.
  >   + Perform computations involving modular arithmetic.
  >
  > ### Discrete Probability
  >
  > *Learning Outcomes:*
  >
  > * Calculate probabilities of events for elementary problems such as games of chance.
  >   + Differentiate between dependent and independent events.
  >   + Make a probabilistic inference in a real-world problem using Bayes’ theorem to determine the probability of a hypothesis given evidence.
  >
  > ### Measuring Algorithm Complexity
  >
  > *Learning Outcomes:*
  >
  > * Be able to meaningfully compare the asymptotic growths of pairs of functions.
  >
  > ### Graphs and Trees
  >
  > *Learning Outcomes:*
  >
  > * Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each type of graph/tree.
  >   + Be able to prove elementary results about graphs and trees, such as:
  >   + In any graph, the sum of the degrees of the vertices equals twice the number of edges.
  >   + In any tree, the number of edges is one less than the number of vertices.
  >   + Model a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system.
  
  Source: [Discrete Mathematics Preparation](https://csci.williams.edu/discrete-mathematics-preparation/ "Preparation for the Discrete Mathematics Proficiency Exam at Williams College") from Williams College [Computer Science Department](https://csci.williams.edu/)
  
  
  ---
  
  ### Answer by username_7 on 2018-02-11. Score: 3
  
  I'd say graph theory lies right in the sweet spot of the intersection of Discrete Math and CS - in fact, at my own university, the idea of graphs are introduced in CS courses before it goes into more depth in later math courses (in an intro to combinatorics course). There are some intuitive ways to provide motivation for the topics (e.g. path finding and taxonomy intuitively *feel* like they should be modeled with graphs and trees respectively), and then there are some problems which at first glance *don't* feel like they have anything to do with graphs, but one can interpret the problem as a graph - scheduling problems and graph colourings, or a node representing the state of a puzzle/game and edges representing actions being done in this puzzle/game, connecting to the node representing the state after the action is done.
  
  With the puzzles example, for appropriate puzzles, this representation could be used to "brute force" a solution to said puzzle, e.g. a Rubik's cube or sudoku. The "actions" for a Rubik's would be the possible rotations of the cube. The "actions" for a sudoku might be to fill in one of the empty boxes with some number. An important distinction between these two examples is that in a Rubik's cube, we can return to a state we previously had - the graph formed has cycles in it, so we have to take that into account. In the sudoku example, because we ALWAYS fill in a box with a number, the number of empty spaces always decreases by 1 for each "action" (we never *erase* a number), thus our graph representing the Sudoku puzzle's possible solutions is acyclic. In both, we'd like to stop our actions once the puzzle has been "solved", which we'd have to check for. Also, note that both graphs are directed graphs.
  
  There's a bunch more to be said about applications of graphs... What's important is, as the other answer points out, not just *learning* about graphs, but actually programming some algorithms with them.
  
  You may also want to cover some basic propositional logic and (finite) set theory. Reasoning about abstract logical statements as well as sets is fundamental to computer science just as it is mathematics. Unfortunately it may feel too abstract for some students... I had to take a CS course in Logic, and for part of this course, we used the proof assistant Coq (<https://en.wikipedia.org/wiki/Coq>). Unlike writing mathematical proofs by hand, writing in Coq feels more like writing a program (which is because Coq is (in a sense) *also a programming language*), and this might be a way to cater it to CS students - proving is programming.
  
  Might add more stuff here if I can think of it... Thinking of linear algebra, which some mysteriously classify as discrete math. My high school used to do this, though I'll admit it has a discrete "feeling" to it versus Calculus or Analysis, and it also *can be* truly discrete with finite fields, or finite modules over a (discrete) ring. Maybe transformation matrixes being used in computer graphics, with 2D and/or 3D focus depending on the class's maturity. Not sure if this is the right fit for what you want though...
  
  
  ---
  
  ### Answer by username_3 on 2018-02-11. Score: 3
  
  This question is hard to answer and especially hard to provide a *complete* answer. There are a lot of things that are good to know if you work with computers, though not everyone will use everything on anyone's list of favorites.
  
  However, some sorts of discrete/finite math are especially useful as they are useful for building models, independent of computers. The models can be programmed to solve useful problems in the world. I'll mention a few here.
  
  The basic idea here is that the more ways you have to *approach* a problem, the more likely it is that you can provide a solution. Even an approximate solution is often enough, especially in situations of uncertainty or when there are many variables and many constraints.
  
  [Markov Chains](https://en.wikipedia.org/wiki/Markov_chain) and Markov Processing. These describe dynamic systems in which changes depend on only the current state and not a history.
  
  [Linear Programing](https://en.wikipedia.org/wiki/Linear_programming), and especially Integral Linear Programming where solutions must be integers. These are used for all sorts of optimization problems where constraints must be observed.
  
  Discrete Probability and [Combinatorics](https://en.wikipedia.org/wiki/Combinatorics) which has entries to many related fields (Graph Theory, Coding Theory, ...)
  
  [Decision Theory](https://en.wikipedia.org/wiki/Decision_theory) and [Decision Trees](https://en.wikipedia.org/wiki/Decision_tree), often used in algorithm design. Modeling under uncertainty.
  
  [Set Theory](https://en.wikipedia.org/wiki/Set_theory) and, more generally, Mathematical Logic, used ubiquitously in programming and in Theoretical CS.
  
  [Vectors and Matrices](https://en.wikipedia.org/wiki/Game_theory) (not strictly discrete, of course) but often used in proofs and models, especially models of physical systems.
  
  [Game Theory](https://en.wikipedia.org/wiki/Game_theory), again used in modeling and in predicting outcomes in complex situations.
  
  [Number Theory](https://en.wikipedia.org/wiki/Number_theory) used in many things, especially cryptology.
  
  ---
  
  Often such courses are, indeed, best taught by mathematicians. But it is also possible for a CS department to negotiate with the Math department on content. Even more radical, is a collaborative course, taught jointly by a mathematician and a computer scientist in which programming is used to enhance the material and make it more concrete. It is also possible for it to be team-project course in which different teams work on different problems, each emphasizing some different sort of mathematical modeling. A joint wrap up (science fair) can be very valuable.
  
  Also note that any of these topics could be a full course (or more). Some small subset of topics from several of these areas is enough to make up a course.
  
  
  ---
  
  ### Answer by username_4 on 2018-02-07. Score: 1
  
  The one thing I would *not* do is create a separate Math course oriented towards computer programming. A purely-math course with no programming is probably the best way to kill interest in one or the other.
  
  Introduce the math where it naturally fits in as you teach algorithmic concepts for real situations -- actual projects in your courses. Most programmers think no more about 'math' as a subject than Chefs think about Thermodynamics: they don't have to!
  
  > **Comments:**
  > **username_3**: I think your answer has validity, but I also note that most university curricula do, actually, have a discrete math course that is required of CS majors. It may be taught either by mathematicians (less programming) or by computer scientists (hopefully, more). In a similar vein, some university programs require at least some Calculus, usually from the math department. There are tradeoffs, of course. At a minimum, courses from the math department may give an alternate way of looking at problems - a good thing.  
  > **username_5**: Welcome to [cseducators.se]! Your answer is quite interesting; If you could expand just a bit more upon your answer, it would surely be of higher quality.  
  
  ---
  
  