CS 303 Discrete Structures and Programming Assessment: Difference between pages

From Computer Science at Indiana State University
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
m 1 revision imported
 
wiki_previous>Jkinne
No edit summary
 
Line 1: Line 1:
== Catalog Description ==
A C programming assessment is given at the end of each of the following courses: CS 202, 499, 500, 685, 695, 699. Examples of the assessments are at [http://cs.indstate.edu/info/files/programmingAssessmentSample.pdf], [http://cs.indstate.edu/info/files/programmingAssessmentSample2.pdf].  
This course is an introduction to discrete mathematics for computer science. The course covers the basic topics from set theory (including functions and relations), logic, number theory, counting, graph theory, and discrete probability. It involves a detailed study of proof techniques. Prerequisite - C or better in CS 201.


== Prerequisites ==
Note - we are currently working up a [[Python Assessment]] that will be used potentially for CS 201, 401, 501.  Stay tuned...
* Willingness to work hard.


== Standard Content ==
= Grading/Scoring =
===Course Outline ===
The assessment consists of 5 programming problems in C from basic programming and data structures. The assessment is given on paper with no calculator, computer, etc., and students are given at least 45 minutes to complete the assessment. A student passes the assessment if both of the following hold: answers to all 5 questions are at least partially correct, and at least 3 answers are completely correct.
* Logic: proof tables, existential quantification, universal quantification, proposition, propositional function, De Morgan’s law (R. Ch. 1 - “R.” refers to the Rosen book, see below.)
* Basic set theory: sets, intersection, union, complement, Venn diagram, inclusion-exclusion principle (R. Ch. 2)
* Proof techniques: direct proof, contrapositive proof, proof by contradiction, weak induction, strong induction (P. Part 2 and R. Ch. 5 - “P.” stands for the “Book of Proof”, see below.)
* Counting: permutations, combinations, binomial theorem, identities (e.g. {Pascal’s identity) pigeonhole principle and applications, double counting (R. Ch. 6)
* Discrete probability: sample space, events experiments, outcomes, distributions, conditional probability, random variables, independence, expectation, linearity of expectation (R. Ch. 7)
* Optional topics: Monty Hall problem, 100 prisoners problem, probabilistic method to prove lower bound on Ramsey numbers
* Number theory: modular arithmetic division algorithm, modular exponentiation, primes, sieve or Eratosthenes, gcd, lcm, Euclidean algorithm, Bezout’s theorem, inverses, fundamental theorem of arithmetic, solving linear congruences, affine cipher, RSA (R. Ch. 4)
* Graph theory: basic graph terminology, undirected graphs, bipartite graphs, degree of a vertex, handshaking theorem, matchings, Hall’s marriage theorem (optional) (R. Ch. 10)


===Learning Outcomes===
The programming assessment is graded very strictly so that there are no judgement calls in grading it - answers are only scored as correct if they are free from any kind of error, and are only scored as half correct if your answer has (i) the right start and (ii) does not have anything that makes little sense or clearly conveys that you are not on the right track. Passing the assessment is only meaningful if it is scored this way - when you pass we can say with 0 doubt that you mastered these problems. This also removes subjectivity from the scoring.
* Capable of constructing rigorous mathematical proofs using direct proof, proof by contradiction, induction, etc.


We realize this grading is strict, so we do everything possible to get you ready for the assessment. The assessment is offered multiple times throughout the semester, failed attempts do not count against you, programming review sessions are offered many times, faculty will give you feedback on your attempts any time you ask, and the unix lab is open most business hours with a lab assistant on duty who can help you practice. Take advantage of all of this as needed.


===Important Assignments and/or Exam Questions===
= Policies =
* What is the decryption function for an affine cipher if the encryption function is c = (15p + 13) mod 26?
The following are in effect.
* Show that if 7 integers are selected from {1,2,3, ..., 12}, then there must be a pair of these integers with a sum equal to 13. What if only 6 integers are selected rather than 7? Can you still conclude that there must be a pair of these integers with a sum equal to 13?
* CS 202: grade of C requires passing the programming assessment.
* A k-regular graph G is one such that deg(v) = k for all v ∈ G. Prove that if G is a k-regular bipartite graph with k > 0 and the bipartition of G is A and B, then |A| = |B|.
* CS 500: grade of greater than C requires passing the programming assessment.
* What is the probability of these events when we randomly select a permutation of 1,2,3,4?
* CS 499, 685, 695, 699: passing the course requires passing the programming assessment.
** 1 precedes 4
* The programming assessment will be given four times per semester, around the 5th, 10th, 12th, and 14th weeks. The assessment will not be given any extra times for those who weren't able to pass, so you should definitely not miss any of these chances.
** 4 precedes 1
* The programming assessment needs to be passed only once as an undergraduate and once as a graduate student. If you pass in CS 202 you don't need to take it in CS 499. If you pass it in CS 500 you don't need to pass it in CS 685/695/699.
** 4 precedes 1 and 4 precedes 2
** 4 precedes 1, 4 precedes 2, and 4 precedes 3
** 4 precedes 3 and 2 precedes 1.
* Let Xn be the random variable that equals the number of tails minus the number of heads when n fair coins are flipped. Compute the expected value of Xn. (Hint: Define a set of a random variables and express Xn in terms of these random variables. Then use linearity of expectation. Explain clearly everything you do.)
* Prove by induction that for any positive integer n, the inequality (1 + x)n ≥ 1 + nx holds for all x ∈ R with x > −1.
* Suppose that the domain of the propositional function P(x) consists of the integers −1, 0, and 1. Write out each of these propositions using disjunctions, conjunctions, and negations: (a) ∃xP(x), (b) ∃x¬P(x), (c) ¬∃xP(x), (d) ¬∀xP(x).  


=== Standard resources ===
Note that in particular this means a CS student cannot graduate without passing the programming assessment.
* [https://www.amazon.com/Discrete-Mathematics-Its-Applications-Seventh/dp/0073383090/ref=sr_1_1?dchild=1&keywords=978-0073383095&qid=1621279949&sr=8-1 “Discrete mathematics and its applications”, 7th edition, by Kenneth Rosen. ISBN: 978-0073383095 (R.)]
 
* [https://www.people.vcu.edu/~rhammack/BookOfProof/ Book of Proofs (P.)]
'''** UPDATE 2021''' - the CS major has been updated to have a concentration where CS 202 is not required.  The faculty are figuring out what to do with the programming assessment for that concentration.  Stay tuned...
* Experimental resource: [http://www.zybooks.com/ discrete math course of zyBooks]
 
MWF noon is normally free for most CS students as a time to give the assessment; though some students have non-CS classes at this time.  The class time for CS 202, 499, 500, 685 are also potential good times.  It is best to pick the times and days for the assessment early in the semester and get them onto the calendar on the CS homepage.
 
There have been many questions and some anxiety about the programming assessment. Replies to some FAQs are below. 
 
=Practice Problems=
See /u1/junk/ProgrammingAssessment on the server for more practice problems, and more previous versions of the assessment. Also, see a [https://www.youtube.com/watch?v=b5EcHJ9YPQI&list=PLXFP6J47Bp0fe6g5rQV0ka-AKDLdVvZ56&index=8 youtube video] by Jeff Kinne with advice and answers for one of the versions of the assessment. Additional previous assessment problems are also at http://cs.indstate.edu/~sternfl/assess/
 
= How to Make Sure You'll Pass =
If review sessions are offered, come to all of them.
 
Take the assessment each time it is offered. You don't really know what it will be like until you try to take it for real. Any failed attempts do not count against you.
 
Pick a problem type that is easiest for you, and practice just that type of problem. Visit the lab and ask the GAs to take a look at what you have. Come ask one of the CS faculty to take a look. Once you have that problem type mastered, pick the next easiest for you.
 
Follow tutorials online for C programming (not C++, this is in C). Watch videos. There are many options to choose from.
Form a study group with others in your class, work on problems together and help each other out (not during the test itself, of course).
 
= What if You Cannot Pass it =
The policy will be enforced, you will be given an incomplete with a due date of the first day of the next semester, you might be given one last chance to take the assessment before the grade becomes the default (F for 685, 695, 699, C for 500 [assumomg there isn't some other reason you would get an F], C- or lower for 202, U for 499).
 
The policy is the following: for CS 499, 685, 695, 699 you must pass the assessment to pass the class, for CS 202 you need to pass the assessment to get at least a C, and for CS 500 you need to pass the assessment to get higher than a C. Note that for all of those, there could be other reasons to earn a low final grade (e.g., even if you pass the assessment, if you fail your exams, don't come to class, etc. you would be given the grade you earned based on your coursework). The assessment is given multiple times per semester. You need to take this seriously and follow the above advice.
 
'''** UPDATE 2021''' - the CS major has been updated to have a concentration where CS 202 is not required.  The faculty are figuring out what to do with the programming assessment for that concentration.  Stay tuned...
 
= Why =
A computer science degree is different than information technology, computer information systems, and other degrees that are computing-related. A person with a CS degree should have many useful and important skills and knowledge - programming, problem solving, how computer systems work, debugging techniques, abstract thinking, etc. If we were to pick one single skill a CS graduate should have, it is to have mastered basic programming (which does require a bit of problem solving, debugging, abstract thinking, etc.).
 
The programming assessment is a single well-defined objective that all CS faculty can agree all graduating CS students should be able to pass. This is a minimum standard that we expect of all of our graduates. Enforcing this standard is good for students because - (a) it clearly communicates expectations, and (b) allows students and faculty to say that uniformly any ISU CS graduate can do basic programming.

Revision as of 13:13, 13 March 2021

A C programming assessment is given at the end of each of the following courses: CS 202, 499, 500, 685, 695, 699. Examples of the assessments are at [1], [2].

Note - we are currently working up a Python Assessment that will be used potentially for CS 201, 401, 501. Stay tuned...

Grading/Scoring

The assessment consists of 5 programming problems in C from basic programming and data structures. The assessment is given on paper with no calculator, computer, etc., and students are given at least 45 minutes to complete the assessment. A student passes the assessment if both of the following hold: answers to all 5 questions are at least partially correct, and at least 3 answers are completely correct.

The programming assessment is graded very strictly so that there are no judgement calls in grading it - answers are only scored as correct if they are free from any kind of error, and are only scored as half correct if your answer has (i) the right start and (ii) does not have anything that makes little sense or clearly conveys that you are not on the right track. Passing the assessment is only meaningful if it is scored this way - when you pass we can say with 0 doubt that you mastered these problems. This also removes subjectivity from the scoring.

We realize this grading is strict, so we do everything possible to get you ready for the assessment. The assessment is offered multiple times throughout the semester, failed attempts do not count against you, programming review sessions are offered many times, faculty will give you feedback on your attempts any time you ask, and the unix lab is open most business hours with a lab assistant on duty who can help you practice. Take advantage of all of this as needed.

Policies

The following are in effect.

  • CS 202: grade of C requires passing the programming assessment.
  • CS 500: grade of greater than C requires passing the programming assessment.
  • CS 499, 685, 695, 699: passing the course requires passing the programming assessment.
  • The programming assessment will be given four times per semester, around the 5th, 10th, 12th, and 14th weeks. The assessment will not be given any extra times for those who weren't able to pass, so you should definitely not miss any of these chances.
  • The programming assessment needs to be passed only once as an undergraduate and once as a graduate student. If you pass in CS 202 you don't need to take it in CS 499. If you pass it in CS 500 you don't need to pass it in CS 685/695/699.

Note that in particular this means a CS student cannot graduate without passing the programming assessment.

** UPDATE 2021 - the CS major has been updated to have a concentration where CS 202 is not required. The faculty are figuring out what to do with the programming assessment for that concentration. Stay tuned...

MWF noon is normally free for most CS students as a time to give the assessment; though some students have non-CS classes at this time. The class time for CS 202, 499, 500, 685 are also potential good times. It is best to pick the times and days for the assessment early in the semester and get them onto the calendar on the CS homepage.

There have been many questions and some anxiety about the programming assessment. Replies to some FAQs are below.

Practice Problems

See /u1/junk/ProgrammingAssessment on the server for more practice problems, and more previous versions of the assessment. Also, see a youtube video by Jeff Kinne with advice and answers for one of the versions of the assessment. Additional previous assessment problems are also at http://cs.indstate.edu/~sternfl/assess/

How to Make Sure You'll Pass

If review sessions are offered, come to all of them.

Take the assessment each time it is offered. You don't really know what it will be like until you try to take it for real. Any failed attempts do not count against you.

Pick a problem type that is easiest for you, and practice just that type of problem. Visit the lab and ask the GAs to take a look at what you have. Come ask one of the CS faculty to take a look. Once you have that problem type mastered, pick the next easiest for you.

Follow tutorials online for C programming (not C++, this is in C). Watch videos. There are many options to choose from. Form a study group with others in your class, work on problems together and help each other out (not during the test itself, of course).

What if You Cannot Pass it

The policy will be enforced, you will be given an incomplete with a due date of the first day of the next semester, you might be given one last chance to take the assessment before the grade becomes the default (F for 685, 695, 699, C for 500 [assumomg there isn't some other reason you would get an F], C- or lower for 202, U for 499).

The policy is the following: for CS 499, 685, 695, 699 you must pass the assessment to pass the class, for CS 202 you need to pass the assessment to get at least a C, and for CS 500 you need to pass the assessment to get higher than a C. Note that for all of those, there could be other reasons to earn a low final grade (e.g., even if you pass the assessment, if you fail your exams, don't come to class, etc. you would be given the grade you earned based on your coursework). The assessment is given multiple times per semester. You need to take this seriously and follow the above advice.

** UPDATE 2021 - the CS major has been updated to have a concentration where CS 202 is not required. The faculty are figuring out what to do with the programming assessment for that concentration. Stay tuned...

Why

A computer science degree is different than information technology, computer information systems, and other degrees that are computing-related. A person with a CS degree should have many useful and important skills and knowledge - programming, problem solving, how computer systems work, debugging techniques, abstract thinking, etc. If we were to pick one single skill a CS graduate should have, it is to have mastered basic programming (which does require a bit of problem solving, debugging, abstract thinking, etc.).

The programming assessment is a single well-defined objective that all CS faculty can agree all graduating CS students should be able to pass. This is a minimum standard that we expect of all of our graduates. Enforcing this standard is good for students because - (a) it clearly communicates expectations, and (b) allows students and faculty to say that uniformly any ISU CS graduate can do basic programming.

Retrieved from "https://cs.indstate.edu/web/index.php?title=CS_303_Discrete_Structures&oldid=328"