View source for CS 203

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

This page contains the syllabus for CS 203 for the most recent offering (spring 2025). Previous terms - [[CS 203 Fall 2024]], [[CS 203 Spring 2024]], [[CS 203 Fall 2023]].

=General Information=
'''Course website''' - https://cs.indstate.edu/web/index.php/CS_203

'''Your Instructor'''

[https://kinnejeff.com Jeff Kinne], [http://mailto:jkinne@indstate.edu jkinne@indstate.edu] <br>
''Office:'' Myers Technology Center (TC) 301D and in Microsoft Teams, phone 812-237-3394 <br>
''Instructor Office Hours:'' MWF 8-9am, 2-3pm, TR 10am-2pm<br>
''Meeting:'' https://cs.indstate.edu/jkinne-meeting

'''Graduate assistant help''' - Isaiah Bartlett supports this course. You can email him or set up an appointment - see https://cs.indstate.edu/web/index.php/ISU_CS_People#CS_Departmental_Graduate_Assistants

'''Lecture, Exam'''

''Lecture:'' WF 10-10:50am and 1-1:50pm in Myers Technology (TC) 307, and over Zoom (link in Canvas, see below), and recorded<br> 
''Mid-term exam:'' Friday February 28 10-10:50am and 1-1:50am<br> 
''Final exam:'' Wednesday May 7 1-2:50pm <br> 

'''Prerequisites''' - C or higher in CS 151.

'''CRN numbers''' - 12156 for the 001 face to face section, 12155 for the 301 online section

'''Required text'''
* We will use selections from the following free online sources.
* '''Primary text for the beginning of the course''' - '''[https://mfleck.cs.illinois.edu/building-blocks/index-sp2020.html Building Blocks for Theoretical Computer Science]''' by Margaret M. Fleck
* [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] by Eric Lehman, F Thomson Leighton, and Albert R Meyer
* [https://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf Introduction to Theory of Computation] by Anil Maheshwari and Michiel Smid
* Additional sources - as needed
** [https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation RSA Encryption (Operation)], [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm Extended Euclidean Algorithm], [https://en.wikipedia.org/wiki/Fermat%27s_little_theorem Fermat's Little Theorem], [https://en.wikipedia.org/wiki/Modular_exponentiation Modular Exponentiation]
** [https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) Master Theorem]
** [https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability 3SAT NP-complete problem], [https://www.geeksforgeeks.org/proof-that-clique-decision-problem-is-np-complete/ Clique NP-complete problem], [https://cgi.csc.liv.ac.uk/~igor/COMP309/3CP.pdf 3 Coloring NP-complete problem]

'''Class notes''' - Notes during class will mostly be kept in the documents in '''[https://sycamoresindstate-my.sharepoint.com/:f:/g/personal/jeffrey_kinne_indstate_edu/EiJJbQVND3FMr25IAoHydnUBADrC7z-tZH_OTaD1h_A8Ow this OneDrive folder]'''.  Note that you will need to authenticate with your ISU account to view the notebook.

=Announcements/Assignments/Quizzes/Exams=
'''HW and Labs'''
These are posted in Canvas. HWs are normally due 1 week after assigned. Labs are normally due the next class period after assigned (2 days after assigned). All times are Eastern US time.

'''Quizzes'''
Rules for quizzes - https://cs.indstate.edu/web/index.php/Jeff_Kinne_Course_Policies#Quizzes

Practice quizzes will be here - https://indstate.instructure.com/courses/12565/quizzes

'''Exams'''
Rules for exams - https://cs.indstate.edu/web/index.php/Jeff_Kinne_Course_Policies#Exams

'''Announcements'''
Announcements will normally be posted to the course in Canvas.

=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.  For letter grades I will use the usual breakdown as a starting point (90 is A-, 80 is B-, etc.), but will raise letter grades above this if I think it is needed (e.g., if assignments, exams, and quizzes are really tough).
* 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).

==Lab Help==
See https://cs.indstate.edu/web/index.php/Unix_Lab_and_Help 

==Course Announcements==
Announcements regarding the course will be made both during class and in Canvas. You should make sure your settings are such that you will be notified of these announcements (e.g., by email). You should regularly check your ISU 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. You should not be directly copy/pasting without prior approval; if you have approval you need to give a citation right at the point where it is used (i.e., in a comment) and at the top of your file.

''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. 

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

==Office hours==
You can contact me by email or Teams or come to my office during the hours I am normally there. If you want to be sure I am there you can sign up for an appointment. Note that I normally am available for online meetings SMTWR 8-10pm as well. 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.

==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, for getting to online lectures (which are done using Zoom), and for posting announcements.

==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).

For ISU's links to information on getting started with Zoom, see https://indstate.teamdynamix.com/TDClient/1851/Portal/KB/ArticleDet?ID=107534. 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, 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 most of my courses, you can join the lecture live at the same time as the face to face students (as long as you don't have a time conflict). If you do this, then you can ask questions during lecture. Or, if you choose to watch the lecture recordings (so you can pause as needed, or watch at 1.5x or 2x), then you should send me questions you have before the next scheduled lecture.

Note that exams are required to be taken at the same time as the face to face students. These dates and times are given near the top of the syllabus.

For attendance when you are not in the room... If joining by zoom, you should 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 should 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 should participate at least as much as "no questions from me right now".

=ISU Required Syllabus Items=
The items in this section are required and are the same for every ISU course.

==Americans with Disabilities Act (ADA) Statement==

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’s Accessibility & Advocacy Resources 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. The Accessibility & Advocacy Resources Office is located at HMSU room 816. They can be contacted at 812-237-3829 or isu-aaro@indstate.edu. Appointments to discuss accommodations with the Accessibility Resources Office staff are encouraged.

Once a faculty member is notified by the Accessibility Resources Office that a student is qualified to receive academic accommodations, a faculty member is obligated to provide or allow a reasonable classroom accommodation under ADA.

==Non-Discrimination, Harassment, and Sexual Misconduct==
''Standard ISU language required in all syllabi...''

Indiana State University is committed to inclusive excellence. To further this goal, the university does not tolerate discrimination in its programs or activities on the basis of: race, color, national origin, gender, age, sexual orientation, gender identity or expression, disability, veteran status, or any other protected class. Title IX of the Educational Amendments of 1972 in particular prohibits discrimination based on sex in any educational institution that receives federal funding. This includes sexual violence, sexual misconduct, sexual harassment, dating violence, domestic violence, and stalking. If you witness or experience any form of the above discrimination, you are asked to report the incident immediately to Public Safety: 812-237-5555 or to The Office of Equal Opportunity & Title IX: 812-237-8954. With respect to sexual discrimination, instructors, faculty, and some staff are required by law and institutional policy to report what you share with them to The Office of Equal Opportunity & Title IX. You do, however, have the option of sharing your information with the following confidential resources on campus:
* Student Counseling Center: 812-237-3939; Gillum Hall, 2nd Floor
* Victim Advocate: 812-237-3849 or 812-243-7272 (cell); HMSU 8th Floor

For more information about discrimination and the support resources available to you visit the Office of Equal Opportunity and Title IX website. Please direct any questions or concerns to: Title IX Coordinator; 812-237-8954; Rankin Hall 426; ISU-equalopportunity-titleix@indstate.edu.

==TimelyCare==
''The ISU dean of students asked faculty and staff spread the word about this, so I am including it here in the syllabus.''

''Attention all faculty and staff!'' Indiana State University is now partnered with [https://app.timelycare.com/auth/login TimelyCare] to deliver a new virtual health and well-being platform for students. This service is in addition to the in-person counseling services offered in the Student Counseling Center, 2nd floor Gillum Hall.  The service provides 24/7 access to virtual care at no cost! Remind your students to take advantage of the TimelyCare services when they feel stressed or overwhelmed. We’ve included a slide that you can attach to emails, input in Canvas and present to students before and after class.  

In addition to services for students, TimelyCare offers Faculty Support — a service for faculty and staff that is designed to equip you with information to help students who may be struggling. It’s available 24/7/365 for free so you can get the guidance on how to support a student in need of care. Access Faculty Support by calling 833-4-TIMELY, ext. 2.  

''How can students access TimelyCare?'' Students can go to https://timelycare.com/indianastate or directly download the TimelyCare app from the app store to register with their school email address by clicking the "Get registered" link. It is important that our students all register in advance on the platform-- and this is where you can help us!  Students can then start visits from any web-enabled device – smartphone, tablet, laptop, or desktop – anywhere in the United States. 

''Who can use TimelyCare?'' Any enrolled student.  

''What services are available?'' TalkNow - 24/7, on-demand emotional support. Scheduled Counseling - Select the day, time, and mental health provider of your choice. (6 visits per year). Self-Care Content - 24/7 access to self-care tools and resources, such as meditation and yoga sessions, helpful videos, and short articles from experts. 

''How much does a visit cost?'' TimelyCare services are available at no cost to students.


==Getting Help==
You are also strongly encouraged to take advantage of Indiana State’s Writing Center. The Writing Center offers a variety of services designed to help students succeed in their classes and careers. The Writing Center is available to assist all registered ISU students with any area of reading or writing for any class. They can also help with personal projects like short stories or personal statements. They offer one-on-one consultations, drop-in services, and online appointments as well as group study tables.  All services are free of charge. Students can make appointments by calling (812) 237-2989 or by using the link on the Writing Center website. Please prepare for your appointment by bringing your textbook, relevant notes and materials, and a printed copy of the writing you have attempted so far.

The Math Lab provides free tutoring for math students through on-campus and virtual meetings. By providing a judgement-free environment, students can build their confidence and view learning math as positive and rewarding. The Math Lab is located in Root Hall, room A009. The hours vary so be sure to check the  Math Lab’s website (current link still needed, after website refresh in fall 2024) to see when tutoring hours are available for your particular math course. If you have any questions, email ISU-MathLab@indstate.edu or call (812) 237-2130.

Student support and accountability: https://sycamoresindstate.sharepoint.com/sites/STU-StudentSupportandAccountability

Accessibility and Resource Office: https://indianastate.edu/life-state/dean-students/aaro#request-accommodations

Student Affairs: https://indianastate.edu/life-state/dean-students

Writing Center: https://sycamoresindstate.sharepoint.com/sites/STU-WritingCenter

==Commitment to Career Readiness==
 
The administration, faculty, and staff at Indiana State University believe that in addition to educating students in academic content, it is important to prepare them to be professional and competent employees in the job market. We are committed to incorporating the eight career competencies outlined by the National Association of Colleges and Employers (NACE) as being necessary to success in the job search and workplace. Many of these eight career readiness competencies will be taught and integrated into your classroom learning:

Critical Thinking/Problem Solving, Oral/Written Communications, Teamwork/Collaboration, Digital Technology Application, Leadership, Professionalism/Work Ethic, Career Management, Global/Intercultural Fluency.

For additional assistance with your career development and preparation, please contact the Career Center (ISU-Career-Center@indstate.edu) or visit the [https://indianastate.edu/about/engagement/career-center Career Center's website].

==Artificial Intelligence in the Classroom==

Indiana State University recognizes the transformative potential of generative artificial intelligence programs and encourages faculty and students to develop literacy regarding these programs.

Your instructor may decide how to best pursue that goal within the following levels:

'''Most Restrictive: AI use not permitted.'''
Any use of generative AI without explicit permission will be considered academic misconduct and may result in disciplinary action, including but not limited to failing the assignment, course, or even expulsion from the university.

'''Moderately Restrictive: AI use permitted, but all usage must be documented.'''
Students must follow their assigned citation method for attributing ideas from outside sources, including generative AI.
Failure to document AI usage may result in incomplete assignments, a lower grade, or a requirement to re-do the assignment. Assignments that rely too heavily on AI without sufficient student input may receive reduced grades.

'''Least Restrictive: AI use required for some course assignments.'''
Some assignments will require students to explore generative AI tools and platforms.

Please note that the Indiana State University Office of Information Technology cannot provide support for artificial intelligence platforms, so faculty should carefully consider how to respond to students in the event of technical problems.

Your instructor may provide more explicit instructions regarding AI usage as part of the course syllabus and assignment descriptions.

As a student, you need to assess the validity and applicability of any generative AI output you use; you bear the final responsibility for all work you submit.

Policies clarifying methods of enforcement against the use of AI tools should be made available in the syllabus. Faculty are discouraged from relying solely on AI-detection programs since such programs can be unreliable and prone to bias.

Several programs and applications have options to view the edit history of a file. If a student is suspected of using an AI tool in violation of course policy, they should be given the opportunity to present this history as evidence. Additionally, students should be able to explain their work and reasoning on the assignment during an in-person meeting with their instructor.

You should always protect your data when using generative AI platforms. Do not share what you do not want easily found by others; this includes but is not limited to: private information, sensitive material, any text protected by copyright, or any course content (lecture notes, assignment descriptions, etc.) without the explicit permission of your instructor.

Generative AI platforms are part of a rapidly developing field, and policies listed here may need to change to reflect those technological advances.