CS 203 Fall 2023

CS 203 Discrete Structures and Computing Theory is taken by CS majors after CS 151.

This page contains the syllabus for CS 203 and is used to keep track of assignments, etc. as well for the most recent offering (fall 2023). For announcements, click the link in the table of contents.

General Information

Course website - https://cs.indstate.edu/wiki/index.php/CS_203

Your Instructor

Jeff Kinne, jkinne@cs.indstate.edu
Office: Root Hall A-142 and in Microsoft Teams, phone 812-237-2126
Instructor Office Hours: MWF 10am-1pm, 2-2:45pm; TR 11-12:30pm, 1:30-2:45pm

Lecture, Exam

Lecture: MW 1-1:50pm, TR 12:30-1:20pm in Root Hall A-019, over Zoom (link in Canvas, see below), and recorded
Mid-term exam: TBA
Final exam: Wednesday, Dec 13, 1-2:50pm and/or Thursday, Dec 14 1-2:50pm

Prerequisites - C or higher in CS 151.

CRN numbers - 53030 for the 001 face to face section, 53036 for the 302 online section

Required text

• We will use selections from the following free online sources.
• Primary text for the beginning of the course - Building Blocks for Theoretical Computer Science by Margaret M. Fleck
• Mathematics for Computer Science by Eric Lehman, F Thomson Leighton, and Albert R Meyer
• Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid
• Additional sources - as needed
  • RSA Encryption (Operation), Extended Euclidean Algorithm, Fermat's Little Theorem, Modular Exponentiation
  • Master Theorem
  • 3SAT NP-complete problem, Clique NP-complete problem, 3 Coloring NP-complete problem

Class notes - Notes during class will mostly be kept in the OneNote notebook or older OneNote notebook and might be made available later as a PDF. Note that you will need to authenticate with your ISU account to view the notebook.

Announcements/Assignments/Quizzes

This section will be kept up to date with information about assignments, quizzes, and exams. This will be kept as a "stack" with the most recent at the top of the list.

Assignments

Exams

First exam

• Around 100 points total, so the first exam counts just a bit less than the hw's and quizzes so far. So the "Lecture Content" grade will be around 55% what we have so far and around 45% from the exam.
• Part A - 12:30-1:20 Sept 28.
  • Face to face students must be in the room on campus.
  • q1-q5 will be set so you can retake each during this time, with the higher grade counted (original or the retake).
  • Additional exam 1 part A to be taken in canvas and mostly auto-graded. This will include the following - Euclidean algorithm, fast modular exponentiation, extended Euclidean algorithm, converting bases. Practice Quiz.
• Part B - Sept 27 - 29
  • 20 minute interview slots, each student signs up for a different one, face to face students must do this face to face (meet at my office).
  • Outline...
    • Using rules of exponents and logarithms - 10 points
    • Compute binomial coefficients - 5 points
    • (h1) Given two different logical expressions, compute the truth tables of both and then discuss what we can say about them (are they logically equivalent, does one imply the other, etc.). 30 points.
    • (h2) Given primes p and q, go through the process of setting up the h2 assignment with these primes. This will not necessarily involve doing the computations but will certainly entail laying out the steps that need to be done. 15 points.
    • Online students - for working out problems "on the board", you can use a document, webcam or phone pointed at a piece of paper - just something where you are working it out and I can read what you are doing.
    • Online students - I will want your screen shared and video turned on, so hopefully you can find a place to do this from that is unobtrusive.
    • Scheduling - please sign up for a 20 minutes slot from https://cs.indstate.edu/jkinne-meeting that is on Wednesday, Thursday, or Friday.

Final exam

• Part A - Thursday, Dec 14, 1-2:50pm
  • Face to face students must be in the room on campus.
  • q6-q11 will be set so you can retake each during this time, with the higher grade counted (original or the retake).
  • Additional exam 2 part A to be taken in canvas and mostly auto-graded. This will include the following - TBD.
  • Grading...
    • Big O question: 21 items to rank, I compute the longest subsequence you have that is correct, add 2, divide by 21, times 15, to get your score on this problem (out of 15 points, so you can get 2 wrong and still get all of the points).
    • Induction problem: claim A didn't really make sense for n being even; it is false regardless, but anything you say for part A is fine as long as you say it is false. We'll call it 5 points for correctly saying that claim A is false and claim B is true, 5 points for the setup and base case of claim B, and 5 points for the inductive step of claim B.
• Part B - Dec 8-15
  • 15 or 30 minute interview slots, each student signs up for a different one, face to face students must do this face to face (meet at my office).
  • Outline...
    • Induction proof of the formula for the sum of the integers 1 to n, your irrational proof from h5, your proof of an uncountable set from h6, a few questions from q8, q9 (so be ready to answer those),
    • Ingenuity question(s) - only happens if time allows - induction proof h4 problem 5, give a RE/DFA/NFA for a given regular language
  • Online students - I will want your screen shared and video turned on, so hopefully you can find a place to do this from that is unobtrusive. You should also have something where you can write or type whatever I'm asking you to do.
  • Scheduling please sign up for one 30 minute or two 15 minute slots from https://cs.indstate.edu/jkinne-meeting that is between Dec 8-15.

Exercises

Exercises are suggested for you to do on your own. They will not be collected or graded. If you have something you would like me to look at, let me know.

• Do the proofs yourself on the board or on paper, like you're explaining to someone: sum of arithmetic series, sum of geometric series, sum of binomial coefficients.
• Write code for modular exponentation.
• Write a gcd function, it should be efficient and use the "Euclidean algorithm".
• Write a program to convert from decimal to any base. Easiest to use the algorithm that produces the rightmost digit first (repeatedly divide by the base, look at the remainder and the quotient). Start by doing a single base (e.g., base 2 or 8) and then make it work for any base from 2 to 36.
• Write a program to convert from any base to decimal.
• Practice estimating and using mental arithmetic to estimate log2, log10, 2 to a power, 10 to a power, max value of a number with a given # of bits, # of bits of a given decimal value. Use the rough estimate that log2(x) is around 3*log10(x), and that 2**10 is around 1000.

HW

Normally due 1 week after assigned, graded once to give feedback, after second due date will be graded for final time.

• h1 - Truth table proofs - due Sept 12. Do the "Assignment 1" listed on that page. Submit in canvas. Corrections due Sept 19.
• h2 - RSA - due Sept 19. Do the assignment listed on that page. Submit in canvas.
• h2b - RSA v2 - for 2 ingenuity points, due in maybe a week or so. People can get started and see how it goes. It is due when someone is finished or Oct 31, whichever is sooner.
• h3 - Functions and Relations - due Oct 18.
• h4 - Induction - released Oct 23, due Oct 30.
• h5 - proofs of irrational - due Nov 27.
• h6 - proofs of uncountable - due Nov 27.
• h7 - graphs - due Dec 1, will only be graded once.
• h8 - big O - due Dec 1, will only be graded once.

graphs, big O, proofs of irrational, prove something is uncountable

Who's who of classic proofs/problems in discrete math / CS (aka favorites that we'll get to and put into assignments)

• logic
  • truth table to show equivalent logical formulas (De Morgan's, distributing AND over OR and vice versa)
  • logical fallacies - disproving with truth table
• number theory
  • euclidean algorithm for gcd (including running time)
  • brute force primality testing (in sqrt(x) time)
  • fast modular exponentiation
  • fermat pseudo-primality test
  • RSA encryption - proof that it works
  • there are infinitely many prime numbers (multiple different proofs)
• set theory, proofs, proof by contradiction
  • sqrt(2) is irrational
  • the real numbers are uncountable
  • the rational numbers are countable
  • most real numbers are not rational
  • there are uncomputable computational problems
• probability - birthday paradox, odds in playing cards / dice / coin flips, prosecutor's fallacy
• induction
  • summation formulas
• graphs - BFS, DFS, MST, shortest path
• regular languages - using regular expressions, equivalent definitions of regular languages
• complexity theory - computational problem being in L, P, BPP, RP, NP, PSPACE, EXP
• an NP-complete problem
• Turing-complete - basic idea, what is a Turing machine

Quizzes

Will normally be taken Mondays at 1:30pm.

• q11 - Complexity classes and running time - Dec 7
• q10 - Regular languages - Nov 30.
• q9 - Big O asymptotics - Nov 2.
• q8 - graphs - Oct 19.
• q7 - functions and relations - Oct 12.
• q6 - Sets - Oct 5.
• q5 - Number Theory - Sep 21.
• q4 - Logic - Sept 7. min, mean, median, max - 16.66666667, 58.66666667, 58.33333333, 100.
• q3 - Miscellaneous Math - see the link in q1 for Math for CS Review. Aug 31, 12:30pm. min, mean, median, max scores - 55.55555556, 90.59111111, 96.27777778, 100.
• q2 - Math and Bases - see the link in q1 for Math for CS Review. Aug 31, 12:30pm. min, mean, median, max scores - 75, 95, 100, 100.
• q1 - Math Notation - that link is a practice quiz, the real one will be in our course in Canvas. See also Math for CS Review for a study guide of sorts. Open book, open internet, not "open other person". Sep 7, 12:30pm. min, mean, median, max score percentages - 73.46938776, 96, 97.95918367, 100.
• q0 - course policies - that is a link to a practice quiz. Can be completed any time once released, can be taken as many times as needed to get 100%. Required to get 100% on this quiz before Aug 28.

Announcements

• For next term - start with a fresh OneNote notebook each term, put announcements in Canvas or keep them like this? Put everything in Canvas, or keep something separate outside of Canvas like this page? Lots more practice with rules of algebra where it has to be done without computer assistance (fractions, exponents, logs, solving equations, distributive law with polynomials, factoring, what does summation formula mean (autograded)). Use something other than OneNote since that broke eventually. Start with simulations of things when possible (ask google for a simulator and use one of those). Time quota for instructor for the course/week and stick to it (can't go over, don't go under either). Arrange things so instructor spends more time on things they enjoy the most (as long as it still supports student learning) - types of examples/projects, types of grading, etc. Go back to not taking late work, so we can go over solutions in class soon after turned in (and couple that with more frequent, smaller assignments). Induction - some auto-graded things about setting up. Maybe same for proofs by contradiction. What is the most important thing - highlight that throughout the term? Practice/interview questions - lots of those.
• Requested additional topics: quantum computing
• Jeff remember to - record, unmute, say something about me.
• Note - something other than OneNote? Google docs??
• Still to do - complexity classes, NP, computability, counting and probability
• Dec 14 - 1-2:50pm, final exam. Online people join the zoom meeting. Face to face people, be in the room.
• Dec 13 - 1-2:50pm, review. I'll be in the room and on zoom if you have questions about anything.
• Dec 7 - if I were going to give a few more HW assignments, this is what they would be.
• Dec 7 - rules of counting and discrete probability, some classic problems with coin flips, dice rolls, playing cards, birthday problem. And we go through what we got through...
• Dec 7 - quiz on complexity and running times.
• Dec 6 - grab bag of topics - Turing machine (can do anything Python can do, though takes a factor n more time, roughly). DFA simulator. RE tester. Graph BFS/DFS simulator. more simulators - see minimum spanning tree, shortest path.
• Dec 6 - BFS - breadth first search, use a queue to keep track of new vertices to explore, gives a tree and shortest # of edges to each vertex from the start vertex, O(n+m) time.
• Dec 6 - Turing machine - DFA for control (that's the program), memory is a tape that you can only read/write one symbol at a time and move one spot on the tape at a time; with that you can simulate Python, although it will be about a quadratic amount slower. Who cares? It is a really simple way to compute, so maybe math is easy on it (want to prove things about it), and math folks are crazy - TM is about the simplest computing device that can still do Python. "Turing-complete" means something can do anything a TM can do. "javascript is Turing-complete". html is not Turing-complete.
• Dec 5 - continuing on with lecture - complexity classes, q11 questions. Final exam - see above. Note - you will need to sign up for either two 15 minute slots or one 30 minute meeting with me between Dec 8-15, face to face students are required for this to be an in person meeting. Signup link - https://cs.indstate.edu/jkinne-meeting
• Dec 5 - letter grade estimate in blackboard - what you would get if the semester ended today. If you have a C- there, you are close and should try to finish the semester well to end up at C or higher.
• Dec 4 - h4 corrections are due Dec 9. h5 corrections due Dec 10. h6 corrections due Dec 10. h7 and h8 will be graded starting on Wednesday, in case people want to make any changes or ask questions before then.
• Dec 4 - no lecture, check email later in the day.
• Nov 30 - quiz on regular languages, 15 minutes, from 12:30-12:45. Continuing on.
• Nov 29 - same as yesterday - finish regular expressions, any questions about hw's.
• Nov 28 - Questions on HWs? Finish DFAs (see To Be Continued from yesterday), NFAs, prove a language is not regular. Next topic after that is complexity classes.
• Nov 27 - questions on any of the hw's due today and Friday? Today's lecture content - regular languages, the other two definitions, proving a language is not regular. quiz on regular languages this Thursday.
• Nov 16 - note that notes from class are also here - https://cs.indstate.edu/~cs203/ regardless of whether OneNote is behaving itself or not.
• Nov 15 - next hw assignment(s) - see above, with some due Nov 27 and some due Dec 1. Note - the ones due Dec 1 will only be graded once (so make sure to get started earlier, ask questions, get them submitted on time). State diagrams and regular languages.
• Nov 14 - finish off looking at whether the real numbers are countable.
• Nov 13 - advising questions - note that CS 302 is not offered in the spring, it will be fall only now. You can take spring courses that require it (but not 458) if you need to in order to fill out your schedule, then take 302 in the fall. If you are in the data science or computing science concentrations.
• Nov 13 - Next on the greatest hits list - the reals are uncountable, but the rationals are countable.
• Nov 9 - no quiz today. Lecture. h2b - you can do this any time before the end of the semester, just let me know. Today's lecture - countable sets.
• Nov 8 - proofs by contradiction - infinitely many primes. h2b graded - a few got it, one got it halfway, most did not submit anything.
• Nov 7 - proofs by contradiction - sqrt(2) is irrational. comments on h3. h3 resubmission due Nov 13.
• Nov 6 - no lecture, catching up on grading.
• Nov 2 - big O / asymptotics quiz, and you get 15 minutes for it. Few examples from last time with recursion tree? Solving recurrences with the master theorem.
• Nov 1 - recursion trees, master theorem. Note - using a different OneNote notebook - link is above and also can get to in canvas by going to the course and then "Class Notebook" on the left.
• Oct 31 - note on proofs - if you are trying to prove a formula (e.g., some of the h4 HW problems), start with one side of the formula, then through a series of steps show it is equal to the other side; do not just start by writing that the formula is true.
• Oct 30 - note that Nov 6 is drop or change to pass/fail deadline - but you should get at least a C in here if you can.
• Oct 30 - finishing up big O, let's do some examples of algorithms and their running times (from BB). Note - you already know everything you need for the big O quiz.
• Oct 26 - definition of big O, verify Jeff's rules, examples with algorithm running times.
• Oct 25 - next topic - big O running times (and we'll include some things from the BB chapters between induction and big O here as well).
• Oct 24 - no lecture this day, I will be available for office hours remotely.
• Oct 23 - h4 on induction due in a week (see link to assignment above). More induction proofs. h3 still not graded yet.
• Oct 19 - quiz on graphs. More induction proofs. h4 on induction coming soon.
• Oct 19 - finish the last picture from yesterday, tiling with triominoes and how the inductive argument would actually do it for an 8x8 example.
• Oct 18 - finish up proof of sum of binomial coefficients formula, on to proofs from the Building Blocks chapter on induction.
• Oct 18 - question from online - please go over the first two parts of hw3 again.
• Oct 17 - questions on h3 or h2b? Finish induction proof of geometric sum, continue with more induction proof examples. Remember - read the chapter in Building Blocks before and/or after we do it in lecture.
• Oct 16 - finish proof from last time (2-way bounding, the triangle). On to the next thing - induction.
• Oct 16 - questions on h3, h2b? Due date for h2b - Oct 31 or when someone is finished (whichever comes first). Second-round-of-grading due date - will be 1 week after on time due date from now on (including for h2b, h3).
• Oct 12 - note the partial solar eclipse on Saturday, 11:30-2:30pm, hopefully it's clear at some point during that.
• Oct 12 - quiz over functions and relations. Any questions about h2b, h3, graphs quiz? Note - applications of graphs (interesting and useful). Today - a cute result in the 2-way bounding chapter of the book.
• Oct 11 - finish talking about h3, due Oct 18. From here on out, the second due date is 1 week after the 1st one. "on time" h3 is due Oct 18, and "last chance" is Oct 25. Taking a look at the quiz on graphs.
• Oct 10 - h3. You should have read the chapter on graphs, check out the quiz on graphs.
• Oct 9 - questions on h2i? pair and meet - anyone still need a partner, pick times to meet. Graphs - building blocks chapter 9.
• Oct 5 - quiz on sets. I sent you cs203xy logins, anyone have issues logging in? hw assignment with proofs (onto, 1-1 proofs)?
• Oct 4 - any questions on quiz? relations proofs. Prove: some math function is onto, 1-1. Prove: some relation is a partial order (subseteq), equivalence relation. Prove: any strictly increasing function is 1-1 (Claim 35 in Chapter 8).
• Oct 3 - h2b, for ingenuity. Interim letter grades. Will send out cs203xy accounts later. Relations. Quiz questions.
• Oct 2 - exam grades. meet with Jeff and classmate assignment, for professionalism. sets quiz on Thursday. Chapters 6, 7, 8 in Building Blocks; let's look at those quizzes and some of the proofs.
• Sep 28 - first exam... see above.
• Sep 27 - no lecture, I'll just be here to answer questions.
• Sep 26 - exam questions? h2 questions? Last chance for h2 corrections is tomorrow, Sep 27.
• Sep 25 - let's talk about the exam, see above.
• Sep 25 - people in the face to face course that did not come to the room to take q5, what am I going to do? If you didn't get permission to take remotely, probably 0, since I have said you need to take quizzes in the room if you're in the face to face section.
• Sep 21 - q5. Continuing sets and looking at q6. Grade calculations for the course. Comments on h1 logical fallacy question, difference between the two questions.
• Sep 20 - just answering questions today, lecture optional, go to the job fair.
• Sep 19 - lecture is online only on zoom (or watch later).
• Sep 19 - q5 on Thursday. Let's look at sets and q6 as well.
• Sep 15 - mistake in the modular exponentiation from class?
• Sep 14 - Modular exponentiation, RSA assignment (finally). Note - h2 and corrections for h1 due Sep 19.
• Sep 14 - your primes for h2 - you should have received an email, ask me if you didn't.
• Sep 13 - go/no-go for h2 being due on Sep 19. Continuing with number theory - proving that Euclidean algorithm is correct and fast, extended Euclidean algorithm, fast modular exponentiation, rules for modular arithmetic. h1 - will have initial grades and comments tonight, then you can resubmit.
• Sep 13 - quiz and assignment stats - you can see this by going to Grades, then click on the little box next to the grade. It should have min, median, mean, max, and also first and third quartile.
• Sep 12 - h1 due today. h2 - let's make it do probably Sep 19, depending on how much we get through today and tomorrow. No quizzes this week, we'll have the quiz on number theory next week.
• Sep 11 - number theory, RSA. quiz scores - see above. h1 due tomorrow - any questions?
• Sep 7 - q1 and q4. Number theory. h2 will be due Sep 14.
• Sep 6 - reminder, q1 and q4 tomorrow.
• Sep 5 - h1 on logic. Starting number theory, with h2 on RSA as our motivation. Reminder - q1 and q4 Thursday.
• Sep 4 - no class.
• Aug 31 - see Exercises above, when I add to it I'll mention it. Also, if I notice people on Zoom showing up very late or leaving very early, I won't count that for attendance. And people in the face to face section need to be in class for quizzes.
• Aug 31 - both q2 and q3 from 12:30-1pm. Logic, looking at q4.
• Aug 30 - Jeff adds everyone individually to the notebook, share with ISU apparently is broken for this notebook.
• Aug 29 - combinations, pigeon-hole principle, contrapositive, math notation. notebook link? q2 and q3 for Thursday.
• Aug 28 - reminder to get 100% on q0 by today.
• Aug 28 - which quiz(zes) we'll have Thursday - probably q2, q3.
• Aug 28 - OneNote notebook link - some people can access, so should work. Need to be logged in with your ISU account.
• Aug 28 - continue where we left off with logarithms, move on to combinatorics, logic. If we finish all that, then on to math notation.
• Aug 24 - when we will do quizzes - Thursdays at 12:30pm looks good.
• Aug 24 - picking up where we left off on converting bases, check that quiz, and moving on through math review.
• Aug 24 - any issues on q0 that people want to ask about?
• Aug 23 - online students, make sure to reply to my email about best slots for weekly quizzes.
• Aug 23 - questions on q0? Today - math review, getting ready for q1, q2, q3.
• Aug 22 - reading assignment is q1, q2, q3 practice quizzes, and information linked about those. Also, chapter 1 of Building Blocks.
• Aug 22 - when we will have quizzes - I will poll the online students to pick a time that hopefully works for all of them. Check email today or tonight.
• Aug 22 - assignments and quizzes - see due dates above.
• Aug 22 - attendance for when you are not in the room... If joining by zoom, you need to post a comment in the chat to say if you have any questions about the current assignments, reading, the last lecture, etc. If watching the lecture, you need to watch it before the next lecture and send me a message by Teams or email saying if you have any questions or want any more examples about a particular topic. So, if not in the room, you have to participate at least as much as "no questions from me right now" to get credit for attendance. Also, if joining by zoom, set a profile picture so that I will see a picture of you in the list of zoom participants (like mine); or leave your video one - in either case, so I can associate a face with the name.
• Aug 22 - first day of class - how the course will work, cheating policy (automatic F for the course), practice quizzes, math notation.
• Aug 20 - page created, made some changes from last term.

Course Description and Content

Course Description

The catalog description for this course is: "Mathematics content that is foundational to and useful for computer science. Topics include axioms and proofs, induction, graph theory, probability, finite automata, regular expressions, Turing machines, and the Church-Turing thesis." The two main goals are (a) being able to reason about computation (mathematical objects and algorithms), (b) familiarity with the topics listed in the description which are important in later courses.

Course Outline

• We will start the course by following along in the order of Building Blocks for Theoretical Computer Science, see link above.

Learning Outcomes

• Basic math - ability to use basic algebra, properties of numbers, rules of exponents and logarithms
• Proofs - understanding of what a proof is, ability to use the following methods of proof as needed - direct proof / by construction, by contradiction, by induction, by decomposition
• Logic - ability to use the rules of logic (truth tables, DeMorgan's laws, etc.) in arguments
• Integers - can use the properties of the integers to write algorithms and reason about their correctness
• Sets, relations, functions - can apply the definitions of these concepts in proofs
• Graphs, trees - understanding of standard definitions related to graphs and trees, able to argue basic properties
• Asymptotic resource analysis (big-O) - can apply the definitions of big-O notation to compare different running time formulae, to simplify expressions, and to determine the big-O running time of algorithms
• Complexity theory - understanding of definitions of basic complexity classes (L, P, NP, PSPACE, EXP), understanding of canonical problems in each class, can reason about these complexity classes
• Notions of infinity - understanding of difference between countably and uncountably infinite, can use these in proofs
• Probability - knowledge of basic definitions and properties of discrete probability, can apply to the analysis of randomized algorithms and processes
• Regular languages - understanding of DFAs, NFAs, regular expressions and ability to produce models for commonly encountered languages
• General models of computation - understanding of Turing-complete models of computation (Turing machine, circuits, programming languages) and implications
• Computability - can give arguments whether a given problem is computable or not (e.g., the halting problem)
• Notation - proper use of math notation (sets, logic, functions, summations, proofs, etc.)

Assessment of Prior Learning

• For those that request an assessment of prior learning to "test out of" CS 203, the following are items that could be included on the test.
• Practice quizzes that are available for this course - rules of exponents/logs, math notation, converting bases, integer algorithms (gcd, extended gcd, modular exponentiation), rules of logic, rules of set theory, big O asymptotics, regular languages, complexity classes and running time.
• Essay questions similar to HW assignments - using truth tables to prove logical identities, demonstrating RSA, properties of functions and relations, proofs by induction, proving a number is irrational, proving the reals are uncountable, graph algorithms (BFS, DFS, shortest path, MST), constructing DFAs / NFAs / REs, proving a language is not regular, proving a problem is in NP, proving a problem is NP-complete, rules of probability and counting

Course Policies, Grading

See Jeff Kinne Course Policies for course policies and how your overall letter grade will be determined.

Assignments

Start Assignments and Quiz Studying Early - I suggest attempting an assignment the day it is given, or the day after, so that if you have a problem you can ask early. If you continue to have problems in trying to complete the assignment, you will have time to ask again. Many of the assignments require thought and problem solving, which takes "time on the calendar" not just "time on the clock". By that I mean that spending an hour on 3 consecutive days is likely to be more productive than trying to spend 3 hours at once on the assignment.

Expected Amount of Work - My expectation is that an average student will spend about 5-10 hours OUTSIDE of class each week (that is in addition to class time or viewing lecture videos) WORKING PRODUCTIVELY/EFFICIENTLY (not just staring at the computer) to complete their coursework for this class. Some students may spend less time than this, and some students will spend more.

This is the foundation for the rest of CS, so it definitely pays off to do your best here.

Note - please find a way to spend enough time on this class (the investment will pay off in terms of skills, being able to get a job, etc.).

Grade Meanings

The letter grades are intended to have the following rough meaning. The list of achievements needed for each was chosen with this in mind.

• A+/A: You understand everything and probably could teach the course yourself.
• B+/A-: You understand nearly everything, and should be all set to use this knowledge in other courses or in a job.
• C/C+/B-/B: Some things you understand very well and others you don't (more towards the former for a B and more towards the latter for a C).
• D-/D+/C-: You did put some effort in, and understand many things at a high level, but you haven't mastered the details well enough to be able to use this knowledge in the future.
• F: Normally, students that get an F simply stopped doing the required work at some point.

CS-Specific Items

This section contains items that are generally the same for all CS courses (and in particular those taught by this instructor).

CS Course Policies

Note that this course follows all standard CS course policies. In particular, (a) cheating/plagiarism by graduate students results in an F in the course, (b) and there will be no makeup exams. See http://cs.indstate.edu/info/policies.html for details.

Lab Help

We have a few lab assistants who are available to help students in beginning computer science courses. Please see https://cs.indstate.edu/wiki/index.php/Unix_Lab_and_Help for details. The lab hours are in a calendar on the CS homepage, at http://cs.indstate.edu/info/index.php#lab_hours. You can join the lab when working on your programs. You can ask the lab assistants to look at your programs, and you can work with any other CS students that are there (you could use the lab as a regular meeting place to work with your classmates).

Course Announcements

Announcements regarding the course will be made both during class and via email to your @sycamores.indstate.edu email address. You should regularly check this email account or have it forwarded to an account that you check regularly. You can set the account to forward by logging into your indstate.edu email online (if you aren't able to find the option, try a different browser or search online for things like - outlook online forward email setting).

Classroom conduct

You may not use cell phones, iPods/music players, etc. during class. You should be civil and respectful to both the instructor and your classmates, and you should arrive to class a few minutes before the scheduled lecture so you are ready for lecture to begin on time. You may use your computer during class if you are using it to follow along with the examples that are being discussed. You should avoid spending time on email, Facebook, work on other courses, etc. during the lecture for this class (be fully present wherever you are, make the most of each experience).

Academic Integrity

See also Jeff Kinne Course Policies for additional information for more specifics about how I am handling these things for this course.

Please follow these guidelines to avoid problems with academic misconduct in this course:

Homework: You may discuss the homework assignments, but should solve and finish them on your own. To make sure you are not violating this, if you discuss with someone, you should DESTROY any work or evidence of the discussion, go your separate ways, SPEND at least an hour doing something completely unrelated to the assignment, and then you should be able to RECREATE the program/solution on your own, then turn that in. If you cannot recreate the solution on your own, then it is not your work, and you should not turn it in.

Note on sources: if you use some other source, the web or whatever, you better cite it! Not doing so is plagiarism.

Exams: This should be clear no cheating during exams. Each instructor has different rules for what is allowed on exams in terms of notes, etc. If not noted otherwise, you should assume that a quiz or exam is closed notes, no computer, no calculator.

Projects: You should not copy from the Internet or anywhere else. The project should be your own work. It will be fairly obvious to me if you do copy code from the Internet, and the consequences will be at the least a 0 on the project. If cheating is observed, you will at the least receive a 0 for the assignment (and may receive an F for the course), and I will file a Notification of Academic Integrity Violation Report with Student Judicial Programs, as required by the university's policy on Academic Integrity. A student who is caught cheating twice (whether in a single course or different courses) is likely to be brought before the All University Court hearing panel, which can impose sanctions up to and including suspension/expulsion. See http://www.indstate.edu/sjp/docs/code.pdf and http://www.indstate.edu/academicintegrity/ for more information.

Please ask the instructor if you have doubts about what is considered cheating in this course.

Office hours (using Teams)

Office hours will be through Microsoft Teams by default. If you would like to meet in person you should reserve an appointment using http://cs.indstate.edu/jkinne-meeting to reserve an in person meeting with Jeff Kinne. I am normally in my office during my listed office hours, but by making an appointment you can be more certain. For meeting through Teams, you should start Teams in your browser or start the application. You should be logged in using your ISU credentials. Once you have Teams open you can message me to ask me questions or to ask to talk. We can use Teams to message (better than emailing back and forth repeatedly if you have questions about something that you just want to write about) or to talk and share screens (e.g., to take a look at your code). I normally have Teams open on my computer all of the time, including during my office hours. During my office hours I will normally reply right away; at other times I will reply when I get a chance.

Canvas

The course has a canvas site. Click https://indstate.instructure.com/ to go to canvas. You should see this course listed under your courses for the current term. If you don't you may need to click on the Courses icon and then click the "All courses" link. The canvas site is used for giving you your grades, for quizzes/exams, and for getting to online lectures (which are done using Zoom). Announcements will be sent through canvas and to your university email. Links and such will be kept on this website.

Lectures (using Zoom)

Here at ISU section numbers starting with the number 3 (e.g.3xx: 301, 302, etc.) are generally online sections. There are 2 types of online sections, synchronous online and asynchronous online. Sections that are synchronous should be joined at the regularly scheduled time of the course, whereas sections that are asynchronous generally keep up with the material independently without regularly scheduled meetings. In general async sections are more difficult to stay on top of, and require a great deal of self-discipline (it is much easier to think "I can watch the videos tomorrow" and just get behind). So if you are in one of these sections make sure you get off to a strong start, and ask for help sooner rather than later. If you are in an online section, check your course schedule for course meeting times; if you have a meeting time, then your section is synchronous, otherwise it is asynchronous (or there is an error in the system).

This course has a 301 section (synchronous online) and 001 section (face to face). Students in either section can participate in whatever way you need to.

For ISU's links to information on getting started with Zoom, see https://indstate.teamdynamix.com/TDClient/1851/Portal/KB/ArticleDet?ID=107534. You can also see the information linked at https://www.indstate.edu/services/student-success/cfss. You will get to the lectures for this course by going to Canvas, select this course, click Modules on the menu on the left, and click on the Zoom module. Once there you should see a schedule of lectures and be able to view recorded lectures. Note that you should install the Zoom application for your computer, and you will need to be logged into to Zoom with your ISU credentials to be able to connect. Also note that the lectures are recorded and only available to those in our class. Recorded lectures normally appear later the same day as the lecture.

Note that if you have not used Zoom with your ISU account previously, you need to go to https://indstate-edu.zoom.us and login with your ISU email address and password to get it setup.

Participating online

If you are participating online, please see the information at https://www.indstate.edu/services/student-success/cfss about participating in online courses. You are expected to either join lectures live through Zoom or watch the recordings once they are available. You will complete assignments, quizzes, and exams on the same schedule as the rest of the class.

For quizzes, I will try to find a time each week that works for everyone to take the quizzes at the same time. The mid-term will be scheduled when it gets closer.

For attendance when you are not in the room... If joining by zoom, you need to post a comment in the chat to say if you have any questions about the current assignments, reading, the last lecture, etc. If watching the lecture later, you need to watch it before the next lecture and send me a message by Teams or email saying if you have any questions or want any more examples about a particular topic. So, if not in the room, you have to participate at least as much as "no questions from me right now" to get credit for attendance. Also, if joining by zoom, please set a profile picture so that I will see a picture of you in the list of zoom participants (like mine); or leave your video on - in either case, so I can associate a face with the name; if you have a good reason to not do either of these let me know.

ISU Required Syllabus Items

The items in this section are required and are the same for every ISU course.

COVID-19 Information

Information specific to CS courses - Start of Term Announcements

Standard ISU language required in all syllabi (read this all once, then skim for your other courses)...

Students are expected to adhere to course attendance policies, as stated in the course syllabus. Documented COVID-related absences will be treated like any other serious medical issue. Following University policy, students with a documented, serious medical issue must contact the Office of the Dean of Students for assistance. The Office of the Dean of Students will supply documentation for faculty. Students with a documented serious medical issue should not be penalized and will be given a reasonable chance to complete exams or assignments. Once notification is made, faculty will make reasonable efforts to accommodate the student’s absence and will communicate that accommodation directly to the student. Please note that faculty are not required to accommodate a serious medical issue with virtual content options, like streaming or recorded lectures. To avoid the potential of missing significant class time, students are strongly encouraged to receive the COVID vaccination that has been made available on campus. For more information about the vaccines or to find a vaccination site, go to: https://ourshot.in.gov. The ISU Health Center also administers COVID-19 vaccines by appointment.

Students should contact the Office of the Dean of Students with questions by calling 812-237-3829.

The information provided in this section of the syllabus is subject to modification based on guidance by public health authorities. Changes to Covid-related policies or updated information will, as always, be posted on the ISU website and communicated in multiple ways.

Special Needs / Disability Services

Standard ISU language required in all syllabi...

Indiana State University recognizes that students with disabilities may have special needs that must be met to give them equal access to college programs and facilities. If you need course adaptations or accommodations because of a disability, please contact us as soon as possible in a confidential setting either after class or in my office. All conversations regarding your disability will be kept in strict confidence. Indiana State University's Student Support Services (SSS) office coordinates services for students with disabilities: documentation of a disability needs to be on file in that office before any accommodations can be provided. Student Support Services is located on the lower level of Normal Hall in the Center for Student Success and can be contacted at 812-237-2700, or you can visit the ISU website under A-Z, Disability Student Services and submit a Contact Form. Appointments to discuss accommodations with SSS staff members are encouraged.

Once a faculty member is notified by Student Support Services that a student is qualified to receive academic accommodations, a faculty member is obligated to provide or allow a reasonable classroom accommodation under ADA.

Disclosures Regarding Sexual Misconduct

Standard ISU language required in all syllabi...

Indiana State University Policy 923 strictly prohibits discrimination on the basis of: age, disability, genetic information, national origin, pregnancy, race/color, religion, sex, gender identity or expression, sexual orientation, veteran status, or any other class protected by federal and state statutes in ISU programs and activities or that interferes with the educational or workplace environment.

Title IX of the Educational Amendments of 1972 prohibits discrimination based on sex, including sexual harassment. Sexual harassment includes quid pro quo harassment, unwelcome verbal or physical conduct, sexual assault, dating violence, domestic violence, and stalking.

If you witness or experience any forms of the above discrimination, you may report to:

Office: Equal Opportunity & Title IX; (812) 237-8954; Rankin Hall, Room 426
Email: ISU-equalopportunity-titleix@mail.indstate.edu
Online: https://cm.maxient.com/reportingform.php?IndianaStateUniv&layout_id=10

Disclosures made to the following confidential campus resources will not be reported to the Office of Equal Opportunity and Title IX:
ISU Student Counseling Center: (812) 237-3939; Gillum Hall, 2nd Floor
Victim Advocate: (812) 237-3829; HMSU 7th Floor
UAP Clinic/ISU Health Center: (812) 237-3883; 567 N. 5th Street

HW Assignments

Some additional hw assignments that do not live somewhere else are put here.

h3 - Functions and Relations

Note that the total points will be scaled before entering into Canvas, so the assignment is worth 20 points in Canvas.

1. Relations (8 points). For each of the following relations, indicate whether the relation is any of the following: reflexive, irreflexive, symmetric, anti-symmetric, transitive. For the properties that the relation does not have, give a counter-example. Conclude also whether the relation is any of the following: partial order, linear order, strict partial order, equivalence relation. It is probably easiest to put this all into a table.
   1. Family: set of all people (who have ever been alive), and (x, y) is in the relation Family if x is y's parent, y is x's parent, or x and y share a common parent. We consider a person to be in a family with themself. Parent - thinking biological.
   2. Teacher: set of all people, and (x, y) is in the relation Teacher if y was ever in a course taught by x. Let us assume that a person cannot be in a course that they are teaching.
   3. Ancestor: set of all people, and (x, y) is in the relation Ancestor if x is an ancestor of y. A person is not an ancestor of themself.
   4. Alumni: (x, y) is in the relation Alumni if person x earned a degree from university y.
   5. Location: (x, (latitude, longitude)) is in the relation Location if person x lives at coordinates latitude, longitude. Set of all living people. Each living person has exactly 1 place they live (with exact coordinates, the center of their building).
   6. Translate: (x, y) is in the relation Translate if the English word x is translated as the Spanish word y. Note a single English word can have more than 1 translation (like the -> el, la, los, las). We include proper nouns as well (mexico city -> mexico DF). Two words are considered to be the same if they are spelled exactly the same (including accent marks). It is possible to have an English word to be the same in Spanish (e.g., internet). Words that are borrowed into English from Spanish (e.g., jalapeño) are also considered the same. In terms of what to do about ñ, you decide and say what you're doing.
   7. Person-Picture: (picture1, picture2) is in the relation Person-Picture if picture1 and picture2 are images that contain at least one person that is the same in each. Let the pictures be the set of all pictures that exist (digital or physical pictures).
   8. Dominates: (f1, f2) is in the relation Dominates if function f1 and f2 are such that f1(x) >= f2(x) for all x. Let the functions be the set of all functions from the real numbers to the real numbers.
2. (8 points) For each of the relations above, pick one of the properties that it does have and give a proof that the relation has that property.
3. (2 points) For each of the relations above, indicate whether the relation is a function or not. If not, give a counter example.
4. Functions (5 points). For each of the following functions, indicate whether the function is one to one, onto, and total. If the function does not have property, give a counter-example. Each of the functions is from the real numbers to the real numbers. It is probably easiest to give this information in a table. You should graph the functions (on desmos or something else) to help see what the answers should be.
   1. f(x) = x²
   2. f(x) = x³
   3. f(x) = x³ - x
   4. f(x) = x³ + x
   5. f(x) = x³ + x²
   6. f(x) = x³ - x²
   7. f(x) = x² + x
   8. f(x) = x⁵ + 3x
   9. f(x) = x⁵ + x³
   10. f(x) = sqrt(x)
5. (2 points) Conjecture. Consider the set of polynomials with integer exponents (like the functions above). Based on your answers to the functions, make a conjecture about the polynomials that end up being one to one.

Grading notes...

• For the ones that ask for a counter-example, give a specific example that shows the answer is "no".
• Some of the relations have two different types of things (e.g., Alumni has people and universities), so many of the properties do not hold because it doesn't make any sense to switch the order on the relation.
• For the proofs, you need to argue in general. You can say what happens with an example, but you also need to argue what happens in general.
• Vacuously true - maybe vacuously true for transitive property for Alumni, Location, Translate.
• There is a difference between "not symmetric" and "anti-symmetric".

h4 - Induction

Note - see the beginning of the lecture on Oct 23 for explanations of these problems. Some problems may be from MCS. For Building Blocks, see BB. For all of the following, give a complete proof (using complete sentences, including stating what you are proving). Note that the total # points for the assignment is 21.

1. (1.5 points) Set up an induction proof. For MCS problem 5.8, prove the base case and set up the inductive step (say what the induction hypothesis would be, and what would need to be proved in the inductive step). Just set up the induction, you don't need to prove the inductive step.
2. (1.5 points) Set up an induction proof. For MCS problem 5.14, do the same as the last problem - prove the base case and set up the inductive step.
3. (3 points) Prove a formula. Use induction to prove that the summation of (2i-1), with i going from 1 to n, is equal to n². Note that this is the sum of the first n odd integers.
4. (3 points) Prove a formula. Use induction to prove that the summation of log(i), with i going from 1 to n, is equal to log(n!).
5. (3 points) Prove a formula. Use induction to prove that the summation of i * (n choose i), with i going from 0 to n, is equal to n * (2^n-1).
6. (3 points) Prove an inequality. MCS Problem 5.31, an inequality proved using strong induction.
7. (3 points) Prove something geometric. MCS problem 5.13, the area of the Koch snowflake.
8. (3 points) Work out an inductive/recursive construction. Consider the problem of tiling a grid with triominoes. Suppose we want to tile the 8x8 grid with triominoes, leaving only the left/upper inner corner piece uncovered (the one on the fourth row from the top, fourth column from the left). Show the tiling produced by the inductive argument of Claim 40 in Building Blocks for this.

h5 - Proofs of Irrational

Each student is given their own real number to prove is not rational. The assignment is to write a proof that the number is not rational. This will be similar to what we did in class (proving sqrt(2) is not rational), but will not be identical. You should use complete sentences and structure your writing like we do in class (state the Claim, then give the Proof).

Check your email for a message from cs203@cs.indstate.edu that will have your assigned irrational number.

Grading - 10 hw points, with half of the points for having the correct algebra/analysis and half of the points for good writing (complete sentences, clearly explain, etc.).

h6 - Proofs of Uncountable

Each student is given their own set of real numbers to prove is not countable. The assignment is to write a proof that the set is not countable. This will be similar to what we did in class (proving that the set of real numbers between 0 and 1 is not countable), but will not be identical. You should use complete sentences and structure your writing like we do in class (state the Claim, then give the Proof).

Check your email for a message from cs203@cs.indstate.edu that will have your assigned uncountable set of real numbers.

Grading - 10 hw points, with half of the points for setting it up properly (having the write picture, etc.) and half of the points for good writing (complete sentences, clearly explain, etc.).

h7 - Graphs

Problems from Mathematics for Computer Science (MCS).

1. MCS Problem 12.2, but instead of 20, use (first two letters of your last name, add them up, % 10, *2, +10). Kinne: Ki, 10+8, 18, %10 = 8, *2 = 16, +10 = 26. Note: simple graph is unweighted, undirected, no self loops.
2. MCS Problem 12.12 (ungraded). Bipartite: 2 parts.
3. MCS Problem 12.23 and note that Chi(G) is the chromatic number of G - the smallest number of colors that can be used to color the vertices of the graph.
4. MCS Problem 12.25. Connected component - can get from any vertex in the component to any other in the component, and cannot go outside the component.
5. MCS Problem 12.46. Base case: 1 vertex graph, 2 vertex graph, 3 vertex graph.
6. MCS Problem 12.50. Diameter - largest distance between any two vertices. Note - "degrees of separation", "Erdos number". Note that a tree is a connected graph without any cycles.

Grading - 20 hw points, 4 per problem (not the ungraded one).

h8 - Big O

Problems from Mathematics for Computer Science (MCS).

1. MCS Problem 14.18. Find the least non-negative integer n to make each statement true. Note that n=0 is theoretically a possible answer for some of these.
2. MCS Problem 14.19. For each cell in the table, indicate whether the asymptotic statement is true or not. Note that for the ones that have sin, you have to pay attention to the precise definition of big O. For the one with n! you can use Sterling's approximation (any of the variations will be good enough).
3. MCS Problem 14.25. Indicate which cells in the table are true. Note that for functions f(n) and g(n), the notation "f ~ g" means that the limit of f(n)/g(n) approaches 1 as n goes to infinity (this is like them being Theta of each other with a constant factor of 1). For the one with n! you can use Sterling's approximation.
4. MCS Problem 14.26. Arrange the functions in increasing big-O order. For some of these you also need to pay attention to the precise definition of big O.

Grading - 20 hw points, 5 per problem.

Note - for problem 14.26, the grade will be based on the largest set from your answers that are in the right order with respect to each other. There are 24 items total, and the grade will be: 20-24 is 5/5, 16-19 is 4/5, 12-15 is 3/5, 8-11 is 2/5, anything else is 1/5.

Regular languages

• Give a DFA for __ - one the same for everyone, one different for everyone
• Give a RE for __ - one the same for everyone, one different for everyone
• Which of the following are regular languages?