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 CS 203 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.

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.

• 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.
• h2 - RSA - due Sept 12. Do the assignment listed on that page. Submit in canvas.

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 -
• q10 - Regular languages -
• q9 - Big O asymptotics -
• q8 - graphs -
• q7 - functions and relations -
• q6 - Sets -
• q5 - Number Theory -
• 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

• Requested additional topics: quantum computing
• Jeff remember to - record, unmute, say something about me.
• Sep 11 - number theory, RSA. quiz scores - see above.
• 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.)

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