Difference between revisions of "CS 303 Fall 2022"

From Computer Science
Jump to: navigation, search
(→‎Announcements/Assignments/Quizzes)
m (Jkinne moved page CS 303 to CS 303 Fall 2022 without leaving a redirect: archive previous term's course)
 
(142 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
'''Note - just copy/pasted from CS 500 page, will be updating to put in CS 303 information soon.'''
 
−
 
 
CS 303 Discrete Structures and Computing Theory is taken by CS majors after CS 151.  
 
CS 303 Discrete Structures and Computing Theory is taken by CS majors after CS 151.  
  
−
This page contains the syllabus for CS 303 and is used to keep track of assignments, etc. as well for the most recent offering (fall 2022).
+
This page contains the syllabus for CS 303 and is used to keep track of assignments, etc. as well for the most recent offering (fall 2022).  For announcements, click the link in the table of contents.
  
 
=General Information=
 
=General Information=
Line 16: Line 14:
 
'''Lecture, Exam'''
 
'''Lecture, Exam'''
  
−
''Lecture:'' MW 1:50 and TR 12:30-1:20 in Root Hall A-019, over Zoom (link in Canvas, see below), and recorded<br>  
+
''Lecture:'' MW 1-1:50 and TR 12:30-1:20 in Root Hall A-019, over Zoom (link in Canvas, see below), and recorded<br>  
 
''Mid-term exam:'' TBA <br>  
 
''Mid-term exam:'' TBA <br>  
 
''Final exam:'' Wednesday, Dec 7, 1-2:50am and/or Tuesday, Dec 6 1-2:50pm <br>  
 
''Final exam:'' Wednesday, Dec 7, 1-2:50am and/or Tuesday, Dec 6 1-2:50pm <br>  
Line 27: Line 25:
 
'''Required text'''
 
'''Required text'''
 
* We will use selections from the following free online sources.
 
* We will use selections from the following free online sources.
−
* [https://mfleck.cs.illinois.edu/building-blocks/index-sp2020.html Building Blocks for Theoretical Computer Science] by Margaret M. Fleck
+
* '''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://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
 
* [https://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf Introduction to Theory of Computation] by Anil Maheshwari and Michiel Smid
−
* Additional sources - as needed.
+
* Additional sources - as needed
 +
** [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 '''[https://sycamoresindstate-my.sharepoint.com/:o:/g/personal/jeffrey_kinne_indstate_edu/Ei0RjIshxhlLmcwB-qhatPUBGDXtwXxc4O_-nVKPHoKrOw?e=yQKG51 CS 303 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.
 
'''Class notes''' - Notes during class will mostly be kept in the '''[https://sycamoresindstate-my.sharepoint.com/:o:/g/personal/jeffrey_kinne_indstate_edu/Ei0RjIshxhlLmcwB-qhatPUBGDXtwXxc4O_-nVKPHoKrOw?e=yQKG51 CS 303 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.
 +
 +
'''Microsoft Teams''' - There is Team for our course.  If you post questions there, these can be answered by anyone in the class, and everyone can see the Q&A that are coming up.  You should see a CS 303 team in your teams list, or the direct link is [https://teams.microsoft.com/l/team/19%3axsr-vl20lv2Ps3_OnloH1zP1t47Of162S78K3yfhhDA1%40thread.tacv2/conversations?groupId=86499d5a-005d-4cca-994e-58509a1fd097&tenantId=3eeabe39-6b1c-4f95-ae68-2fab18085f8d CS 303 MS teams direct link]
  
 
=Announcements/Assignments/Quizzes=
 
=Announcements/Assignments/Quizzes=
 
This section will be kept up to date with announcements of assigned reading, assignments, quizzes, etc.  This will be kept as a "stack" with the most recent at the top of the list.
 
This section will be kept up to date with announcements of assigned reading, assignments, quizzes, etc.  This will be kept as a "stack" with the most recent at the top of the list.
 +
 +
==Assignments==
 +
* '''[[CS 303 final]]''' - final exam information, including the "interview question"
 +
* '''[[Graphs]]''', '''[[Asymptotics]]''', '''[https://cs.indstate.edu/wiki/index.php/CS_303_final#Last_HW_assignment_problems Additional Problems]''' - due Dec 4, I will try to look at whatever is handed in as of Thursday Dec 1 and send out comments.
 +
* '''[[Induction]]''' - assignment at the bottom.  Due maybe Oct 17.  Get started and let's see.
 +
* '''[[Pair and meet]]'''.  Due Oct 2.  To set a time to meet, use this - https://cs.indstate.edu/scheduler.  Note - no submission, you get the points after you meet with Jeff and your partner.
 +
* '''[https://cs.indstate.edu/wiki/index.php/Truth_table_proofs#Assignment_2 Truth tables assignment 2]''', '''[https://cs.indstate.edu/wiki/index.php/Math_for_CS_Review#Other_Assignments Math for CS - Other Assignments]'''. Due Sept 28.
 +
* '''Puzzle/Challenge problems 1''' - [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] problems 1.2, 1.6, 1.8.
 +
* '''[[Truth table proofs]]''', '''[[Proofs of irrationality]]''', '''[[Applying euclid's algorithm for gcd]]'''.  Due Sept 2 (but use the weekend/Monday if you need it).
 +
* Quiz on "math notation" and "math and bases".  The "Assignment" section at the bottom of '''[[Math for CS Review]]''' has a link where you can take the quizzes for practice. When you are ready, take the quizzes in Canvas.  Due Aug 29.
 +
* Hello unix lab.  Follow instructions in '''[[Hello Unix Lab]]'''.  Due Aug 24.
 +
 +
==Announcements==
 +
* 2022-12-07 - Final exam quizzes.  To get to the quizzes, go to canvas, then Quizzes, then look for the quizzes that are labeled as "final exam" quizzes. These will become available to take at 1pm, and they must be submitted by 3pm. Reminder that you should start with any previous ones you did not have an 80% on yet (according to the letter grade email), and then take the new ones, and then take any old ones you did not have a 90% on yet. Good luck!
 +
* 2022-12-06 - last 3 assignments due (last chance) Dec 8.
 +
* 2022-12-05 - [[CS 303 final]] updated to have links to practice quizzes to the new quizzes (graphs, big O asymptotics, complexity classes / running times, regular languages / expressions).  Note that probability will '''not''' be on the final (no quiz for this).
 +
* 2022-12-07 - 1-3pm, canvas quizzes exam.  Check canvas/zoom for the zoom link.
 +
* 2022-12-06 - 1-3pm, review session, and honors conversion project presentation on Mersenne primes and perfect #s.  Check canvas/zoom for the zoom link.
 +
* 2022-12-01 - when are the last HW's "drop dead" due?  If nobody needs my answers early next week, then it could Dec 7 or 8.  After the first round of grading, if you have an opinion let me know.  Default to be due Dec 7 or 8, pending what you think after the first round of feedback.
 +
* 2022-11-27 - discrete probability - we have to do at least some of this, so will start that today or tomorrow.  See the OneNote notebook for notes and suggested reading.
 +
* 2022-11-27 - [[CS 303 final]] - a bit updated with how the final letter grade will be determined.
 +
* 2022-11-27 - [[Induction]] assignment - grading notes were emailed to everyone.  You can submit again in Canvas up through Dec 4, and then I can do a video going over correct solutions.  Of course, you can ask questions in lecture or by email/Teams as well. On the first time through, the highest was getting 5/10 correct.
 +
* 2022-11-22 - new assignments (see above) that are due Dec 4, start working on them soon.  Also, have filled in an outline for the [[CS 303 final]].  I will get caught up on grading and then fill in the details for the final.  The canvas part will be Wed Dec 7 from 1-3pm (and required to be face to face if you are in the face to face section, unless you get approval from me), and everyone will take the canvas part at the same time (unless you get approval from me).  The interview portion will be available early next week up through Dec 9 at noon; those in the face to face section need to do it in person (unless you get approval from me).
 +
* 2022-11-16 - some assignments or quizzes or something.  Working version of that - [[CS 303 final]].
 +
* 2022-11-15 - reading - chapter 2 (regular languages) in [https://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf Theory of Computation]
 +
* 2022-11-14 - reading - halting problem in [https://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf Theory of Computation, pg 163]
 +
* 2022-11-10 - binomial theorem, ch 20.  Next time - finish up uncountability, applications to programming.  Next time - on to regular languages.
 +
* 2022-11-09 - no lecture today
 +
* 2022-11-08 - fun, which is bigger - 3^(1000!) or (3^1000)!
 +
* 2022-11-07 - no lecture tomorrow in this class, since it's election day.
 +
* 2022-11-07 - read up through ch. 18 in BB.
 +
* 2022-11-07 - note that for the final exam, the "interview" part - for those registered face to face, the interview will need to be in person.  Just a head's up, and that will likely be for any time during exam week.
 +
* 2022-11-03 - NP-completeness reduction for Clique from SAT
 +
* 2022-11-01 - chapters on NP and contradiction in BB. Questions on scheduling classes?
 +
* 2022-10-27 - no class, take the exam today/tomorrow.
 +
* 2022-10-26 - MCS2 #7 - how to finish it, what was wrong yesterday (nothing, just didn't put it all together).
 +
* 2022-10-24 - [[Truth table proofs]] assignment 2 and [[Math for CS Review]] other assignments - submissions up through tomorrow 12:30pm, we can go over my solutions tomorrow.
 +
* 2022-10-24 - midterm exam - see [[CS 303 midterm]] for practice quizzes and more details.  Try out the practice quizzes and if you don't understand how to do any of them, ask in class (or send questions by email/teams).  If you think there are any mistakes let me know.  Reminder - sign up for slot for midterm part 2 - '''https://cs.indstate.edu/scheduler'''
 +
* 2022-10-20 - no lecture today, I will be available for questions.
 +
* 2022-10-19 - update on midterm timing - canvas part will be open Oct 27-28, sign up for interview slot for after you will have taken the canvas part.  Last 2 HW assignments (TT and MCS2) last chance due on Sunday (Oct 23), and then I'll give my solutions soon after.
 +
* 2022-10-18 - midterm outline - [[CS 303 midterm]].  That will be updated with more information (practice quizzes, sample questions) as it becomes available.
 +
* 2022-10-17 - '''midterm''' - timed on canvas part will be available Oct 27-28, you will have an interview portion with me as well.  For the interview, sign up for a slot off of '''https://cs.indstate.edu/scheduler''' for some time after you plan to do the canvas part of the exam.
 +
* 2022-10-17 - a bit more in big O, start the Algorithms chapter in Building Blocks. Assignment for Induction is in Canvas now, so you can submit your work.  I'll probably be looking at them on Wednesday.
 +
* 2022-10-13 - no lecture today.
 +
* 2022-10-12 - discuss problems 6 and 7 on the Induction assignment. Updates on grading "math for CS problems 2" - coming soon (probably a video).
 +
* 2022-10-11 - note that there will not be class on Thursday, Oct 13.
 +
* 2022-10-10 - due date on induction Oct 17.
 +
* 2022-10-10 - reading assignment - Big-O chapter in Building Blocks, section 14.7 in MCS (and/or google search for little o, little omega, etc. and pick something that you can follow along).
 +
* 2022-10-10 - truth table assignments 2 initial grading done.  See the assignment for general grading notes.  You received an email with comments on yours.  If you didn't get 2/2 then you need to fix it, as indicated in the email you received.  Note about the NOR gate problem in the grading notes - put a comment for your submission in Canvas for what you used (whether it be a solution for NOR or NAND); '''if you used something and do not add a comment, that is plagiarism'''.
 +
* 2022-10-05 - reading assignment - up through chapter on Trees in Building Blocks (for now, skipping the part in Trees on context free grammars and parse trees).
 +
* 2022-10-05 - more on recursion, finish from last time, also trees.
 +
* 2022-10-03 - no lecture today, I will be zoom just to answer any questions (not required to attend).
 +
* ''' 2022-09-29 - advice - you demo the proof to yourself on the board or on paper.'''
 +
* 2022-09-28 - pair and meet - let me know if you want me to pair you up with someone.
 +
* 2022-09-27 - new assignment "pair and meet", see above.
 +
* 2022-09-27 - reading assignment - up through chapter on Induction in Building Blocks.
 +
* 2022-09-22 - interim grades - I have updated the grading part of the syllabus (below) for how I am scoring for the interim grades. I added grade items for all of this so you can see how I calculated it, and watch today's lecture to see how to check.  Note that these are rough approximations, since we don't have many grades and you will have more chances to get pass ratings on old topics.  We'll come back and look at these again in a few more weeks (after the mid-term).
 +
* 2022-09-21 - interim grades will be based on how many "pass" ratings, I'll do something with that before Tuesday.
 +
* 2022-09-21 - new assignments posted in canvas, cleaned up above.  Due Sept 28. Start now.
 +
* 2022-09-20 - no lecture this day, work on the new assignment.
 +
* 2022-09-19 - new assignment listed above, due date TBD.
 +
* 2022-09-15 - coming up - Building Blocks graphs, some new assignments, some new challenge problems. Today we took an aside to go over Big-O a bit, since that is being looked at in CS 202 right now.
 +
* 2022-09-14 - puzzle challenge problems 1.  Aside - [https://en.wikipedia.org/wiki/RSA_(cryptosystem) RSA cryptosystem] - examples now, proofs some time later, read the wikipedia page.  Go to the job/career fair.
 +
* 2022-09-13 - puzzle challenge problems 1.  You will present solutions to: 2=1 (Lexy), irrational powers (JF), log7(n) (). The other one is still a bit up in the air.  How will they count?  About 1/3 of the class got one correct.
 +
* 2022-09-13 - letter grades - will be based on getting pass rating on things, will be revisiting before interim grades.
 +
* 2022-09-13 - notes on grading for truth table proofs, proofs of irrationality, and running the Euclidean algorithm...
 +
** Scoring on each problem: 2 is pass, 1.5 is pass-. A pass should be required, right? One option is to revisit items that haven't been passed yet at the midterm (which will include an interview component).
 +
** I was hoping people would resubmit and fix problems.  Some did, some didn't. 
 +
** When I assign different numbers to different people, part of the reason is to ensure everyone is doing their own work. If you submit a solution for a problem that was not yours, that is suspicious (and extra work for me to have to decide on).
 +
** When it is required to visit the lab to demo your solution, then you need to do it.
 +
** Don't say things that are not true - check your proofs carefully.
 +
** A few people gave a proof of irrationality for a number that was not assigned to them, and looked like it was based off of an online resource. If you use something and don't cite it, that is plagiarism - you get a 0 on the assignment for the first offence, then F for the course on the second.  And you created extra work for me. ;(
 +
* 2022-09-12 - no class/lecture today
 +
* 2022-09-08 - will continue to keep moving through Building Blocks, and also doing problems from MCS (in class, and probably also assignments).  Will make up your next assignment after the current ones are graded (likely Monday).
 +
* 2022-09-07 - "challenge" problems from the end of today's lecture - our start is in the OneNote notebook under Proofs and then Problems.
 +
* 2022-09-07 - aside - examples/problems from MCS (Mathematics for Computer Science, link above in General Info).
 +
* 2022-09-07 - reading assignment Building Blocks chapters 6 (relations), 7 and 8 (functions).
 +
* 2022-09-06 - for the proofs assignments, please resubmit by 9/7 midnight.
 +
* 2022-09-06 - grading for the two proofs.  Most people need to do edits to fix the truth table proof and irrationality proof.  Check the rules of writing good proofs - [[Proofs]].  For the proof of irrationality, note that things are a tiny bit different for doing a proof with a composite number (check the wiki assignment link again for an example).  For the gcd question, same thing - say what you are solving, and indicate what the answer is when you get to it.  Also, you need to visit the help lab to have them sign off that you can explain/demonstrate your solutions.  Also, remember that I am grading mostly "pass/fail", so you should revise and resubmit (partial credit won't be good enough for these).
 +
* 2022-08-29 - try finishing the last proof we were in the middle of.
 +
* 2022-08-29 - '''reminder to take quizzes today'''.  '''new assignments due Friday''', which include a check-in with the help lab - if you use the weekend to work on this class, that's okay too.
 +
* 2022-08-29 - reading assignment - Building Blocks chapter 5 (sets)
 +
* 2022-08-29 - FYI in terms of when I tend to reply to messages - starting some time around 7am depending on the day, up until about 4pm (with gaps for classes, meetings, etc.), then again roughly 8-10pm. Weekends I will often have longer periods of not checking messages but try to at least a few times per day.
 +
* 2022-08-24 - reading assignment - Building Blocks chapter 4 (number theory - integers)
 +
* 2022-08-22 - fyi, will use OneNote in the browser from now on (spacing wasn't looking right going back and forth between application and browser)
 +
* 2022-08-22 - reminder of the Hello Unix Lab assignment
 +
* 2022-08-18 - ungraded self-check - think about what the first DeMorgan's law should be, and verify or disprove with truth tables.  Another question: is not (p and q) equivalent to p->q ?
 +
* 2022-08-18 - reading assignment - Building Blocks chapter 3 (proofs)
 +
* 2022-08-18 - reading assignment - Building Blocks chapter 2 (logic)
 +
* 2022-08-17 - reading assignment - [https://mfleck.cs.illinois.edu/building-blocks/index-sp2020.html Building Blocks] chapter 1 (math review)
 +
* 2022-08-10 - to start off we will be following along from the beginning of ''Building Blocks for Theoretical Computer Science'', so if you want to do some reading you can start taking a look at that.
 
* 2022-08-09 - creation of this site, including the preliminary list of topics, outcomes, achievements, etc.
 
* 2022-08-09 - creation of this site, including the preliminary list of topics, outcomes, achievements, etc.
  
Line 42: Line 134:
 
'''Course Description'''  
 
'''Course Description'''  
  
−
The catalog description for this course is: "Review of undergraduate topics in Computer Science including Data Structures, Computer Architecture, and Computer Organization. Review of a computer programming language that students can expect to use in advanced courses." The two main goals are that you leave the course as proficient C programmers and proficient at using and analyzing the most important data structures and algorithms.
+
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'''
 
'''Course Outline'''
−
* Getting started - system setup, git, linux, bash, make, apache, math background, development on your personal computer.
+
* We will start the course by following along in the order of ''Building Blocks for Theoretical Computer Science'', see link above.
−
* C programming basics - operators, reserved words, data types, base systems, overflow.
 
−
* C programming strings - manipulation of C strings.
 
−
* C programming memory management - different types of memory in C, how to use them, pros and cons.
 
−
* C programming style - good programming style for reliability, readability, extensibility, security.
 
−
* Data structures - understanding/use of most important data structures - arrays, linked lists, skip list, binary search trees, red black trees, hash tables, heaps, B tree.  Implementation of some of these in C.
 
−
* Algorithms - understanding/use of basic algorithms - sorting (various), binary/linear search (and uses), graph algorithms (basic properties, BFS, DFS, MST, shortest path), strings (edit distance) - including some algorithms that are each of - greedy, dynamic programming, heuristic, randomized, brute force / backtracking.
 
−
* Vocab - additional terms, algorithms, concepts at a shallow level.
 
  
 
'''Learning Outcomes'''
 
'''Learning Outcomes'''
−
* System setup - personal computer setup for both remote (connecting to CS server with terminal, sftp, X windows) and local development (editor, compiler).
+
* Basic math - ability to use basic algebra, properties of numbers, rules of exponents and logarithms
−
* Git - basic use of git for source code management.
+
* 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
−
* Linux - proficient using the Linux terminal for development.
+
* Logic - ability to use the rules of logic (truth tables, DeMorgan's laws, etc.) in arguments
−
* Bash - basic use of bash scripts for testing code.
+
* Integers - can use the properties of the integers to write algorithms and reason about their correctness
−
* Make - basic use of GNU make for compiling code.
+
* Sets, relations, functions - can apply the definitions of these concepts in proofs
−
* Apache - able to post content to your CS accounts to be viewable over the web.
+
* Graphs, trees - understanding of standard definitions related to graphs and trees, able to argue basic properties
−
* Math background - proficient in math background needed for data structures and algorithms.
+
* 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
−
* Personal computer - is setup for development so you can do coursework from your home computer as well.
+
* 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
−
* C programming - understanding of all language features, proficient in writing code using the most common, write code using good programming style.
+
* Notions of infinity - understanding of difference between countably and uncountably infinite, can use these in proofs
−
* Data structures - understanding of operations, efficiency, use cases, can write code in C for data structure operations.
+
* Probability - knowledge of basic definitions and properties of discrete probability, can apply to the analysis of randomized algorithms and processes
−
* Algorithms - understanding of basic algorithms, arguments for correctness and efficiency, can use the write algorithms to solve problems efficiently.
+
* 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.)
  
 
=Grading and Assignments=
 
=Grading and Assignments=
Line 71: Line 159:
 
We will be trying out what I am calling "achievements-based" grading. There are a series of skills, knowledge, and experiences that I want you to achieve.  Your final letter grades will be based strictly on which of these you have completed.  For each achievement, you can achieve the rating of incomplete, pass-, pass, pass+.  The following will be our starting point for how letter grades will be assigned. I will reevaluate this throughout the term to make sure we are on track. I will also be setting the standards for pass-, pass, and pass+ for each of the achievements as we get to them in the course.
 
We will be trying out what I am calling "achievements-based" grading. There are a series of skills, knowledge, and experiences that I want you to achieve.  Your final letter grades will be based strictly on which of these you have completed.  For each achievement, you can achieve the rating of incomplete, pass-, pass, pass+.  The following will be our starting point for how letter grades will be assigned. I will reevaluate this throughout the term to make sure we are on track. I will also be setting the standards for pass-, pass, and pass+ for each of the achievements as we get to them in the course.
  
−
'''C - lowest passing grade in a grad course'''  
+
'''Interim grades''' - I will look at the bullet points below which have already been evaluated. Grades will be assigned as follows:
−
* Pass or higher achievement for ''all'' of the following
+
* A - pass rating on everything so far, at least one challenge/puzzle problem completed.
−
* System setup, git, linux, bash, make, apache, math background, personal computer
+
* A- - pass rating on everything so far
−
* C programming basics
+
* B - at least 2/3 pass rating
−
* Data structures basic understanding - arrays (stack and queue), linked lists (stack and queue), binary search trees, hash tables
+
* C - at least 1/2 pass rating, at least 2/3 pass- or higher
−
* Data structures programming - can write the code for methods for ''some'' of the above
+
* D - at least 1/2 pass rating
−
* Data structures programming - can use ''some'' of the above data structures to solve problems
+
 
−
* Sorting algorithms - basic understanding of at least one slow and at least one efficient sorting algorithm
+
'''D'''
−
* Sorting algorithms - can write the code for at least one sorting algorithm
+
* Pass- or higher achievement for ''all'' of the following
−
* Algorithm techniques - basic understanding of ''at least one'' greedy, divide and conquer, brute force, and dynamic programming algorithm.
+
* Hello unix lab (at least 2/2)
−
* Asymptotic resource usage - basic understanding, can use Jeff's rules of thumb in simplifying expressions
+
* Math notation (at least 80%)
 +
* Math bases (at least 80%)
 +
* Truth table proof (at least 1.5/2)
 +
* Proof that a number is irrational (at least 1.5/2)
 +
* Euclidean algorithm - demo of running the algorithm (at least 1.5/2)
 +
* ''We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.''
 +
 
 +
'''C'''  
 +
* Pass or higher achievement for ''all'' of the above (at least 90% on quizzes, at least 2/2 on assignment problems)
 +
*  
 +
* ''We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.''
  
−
'''B - satisfactory'''
+
'''B'''
−
* In addition to the above...
+
*  
−
* Data structures programming - can write the code for methods for ''most'' of the "C grade" basic data structures
+
* ''We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.''
−
* Data structures programming - can use ''most'' of the "C grade" basic data structures to solve problems
 
−
* Data structures basic understanding - skip list, red black trees, heap, B tree
 
−
* Sorting algorithms - can write the code for at least one slow and at least one efficient sorting algorithm
 
−
* Sorting algorithms - basic understanding of multiple slow and multiple efficient sorting algorithms
 
−
* Graph algorithms - basic understanding of the adjacency lists, adjacency matrices, graph algorithms DFS and BFS
 
−
* Asymptotic resource usage - can apply the precise definitions of big-O, little-o, big-Omega, little-omega, big-Theta to simplify and compare expressions; can apply the master theorem ''or'' recursion tree methods to recursive resource formulae
 
  
−
'''A - good/excellent'''
+
'''A'''
 
* In addition to the above...
 
* In addition to the above...
 +
* At least 1 puzzle/challenge problem solved correctly (pass rating)
 
* Pass+ rating on most of the above
 
* Pass+ rating on most of the above
 
* Pass or higher achievement for ''all'' of the following
 
* Pass or higher achievement for ''all'' of the following
−
* Graph algorithms - can write the code for some of the "B level" graph algorithms
+
* ''We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.''
−
* Graph algorithms - basic understanding of an MST algorithm and shortest path algorithm
 
−
* Asymptotic resource usage - can apply the master theorem ''and'' recursion tree methods to recursive resource formulae
 
−
* Integer algorithms - basic understanding of faster-than-obvious multiplication and exponentiation algorithms
 
−
* Algorithm techniques - can write code for at least one algorithm for each of the "C level" algorithm techniques
 
−
* Algorithm techniques - basic understanding of ''multiple'' algorithms for each of the "C level" algorithm techniques
 
−
* Complexity theory - basic understanding of the definitions of L, P, NP, PSPACE, EXP and a few canonical problems in each
 
  
 
Achievements can be earned based on quizzes, assignments, in-class work, and exams. Rather than having numerical scores for these, I will use them to mark off your achievements. Note that achievements can be "lost" if you demonstrate a skill early in the term and then demonstrate a lack of the skill later in the term. I expect this will not normally be the case, but I will continue to evaluate you based on all of the skills throughout the term.
 
Achievements can be earned based on quizzes, assignments, in-class work, and exams. Rather than having numerical scores for these, I will use them to mark off your achievements. Note that achievements can be "lost" if you demonstrate a skill early in the term and then demonstrate a lack of the skill later in the term. I expect this will not normally be the case, but I will continue to evaluate you based on all of the skills throughout the term.
Line 125: Line 212:
 
* B+/A-: You understand nearly everything, and should be all set to use this knowledge in other courses or in a job.
 
* 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).
 
* 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. '''Note that the lowest grade for grad courses is a C, so if you fall in the range below C then your letter grade will be an F.'''
+
* 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.
 
* F: Normally, students that get an F simply stopped doing the required work at some point.
  
Line 169: Line 256:
  
 
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.
 
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==
 
==Participating online==
Line 181: Line 270:
 
Information specific to CS courses - [[Start of Term Announcements]]
 
Information specific to CS courses - [[Start of Term Announcements]]
  
−
''Note - this section needs to be updated still for fall 2022, what is below is from last year.''
+
''Standard ISU language required in all syllabi (read this all once, then skim for your other courses)...''
  
−
''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. Students must complete the Sycamore Symptom Assessment by email before arriving on campus each day unless they have documented their COVID immunization and have been exempted from the program. 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. Students who have been notified by contact tracers of a close contact who has tested positive for COVID must abide by their instructions, which will include a mandatory period of quarantine, especially if the student is unvaccinated, and/or mandatory testing. 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: ourshot.in.gov. The ISU Health Center also administers COVID-19 vaccines by appointment.
+
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.
 
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. Please follow this link for updated information on ISU’s Fall 2021 requirements.
+
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.
−
 
 
−
Masks on campus: All faculty, staff, and students are required to wear face coverings anytime they are in public spaces. In classrooms they are required of faculty, staff, and students. Failure to comply with this policy will be treated, by policy, as would any student disruption of class. (A refusal or failure to properly wear an appropriate mask will result in the faculty member asking the student to do so. A refusal of that request may result in the student being asked to leave the class for that period. A refusal of that request may result in the faculty member cancelling class and referring the matter to the Office of Student Conduct and Integrity.) A failure of a faculty member to wear an appropriate mask/shield should be reported to the Chairperson of the faculty member.
 
−
 
 
−
Face coverings will be worn by all students and faculty in classrooms as well as in buildings (unless you are alone in an office). What is said/printed on a mask will be held to the same Student Code of Conduct standard as if it were printed on a shirt or hat. As a result, a political statement such as MAGA, BIDEN2020, or BLM is not grounds for demanding that it be removed/replaced. In judging what constitutes an offensive statement on a mask, the determination will be made by Student Affairs using the Student Code of Conduct. If there is a question about a mask, the faculty member will refer the matter to Student Affairs and only insist upon its immediate removal if there is no doubt that it violates the Code. Medical waivers will be made through Student Affairs and students with such a waiver are expected to carry the documentation with them and present it when asked.
 
  
 
==Special Needs / Disability Services==
 
==Special Needs / Disability Services==

Latest revision as of 20:00, 6 January 2023

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

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

General Information

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

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, MTWRF 2-3pm

Lecture, Exam

Lecture: MW 1-1:50 and TR 12:30-1:20 in Root Hall A-019, over Zoom (link in Canvas, see below), and recorded
Mid-term exam: TBA
Final exam: Wednesday, Dec 7, 1-2:50am and/or Tuesday, Dec 6 1-2:50pm
Asynchronous students: For students who will be mostly participating asynchronously even though the course is being offered synchronously, you should pick a regular time each week to check in with the instructor. Make an appointment with the instructor during the first 2 weeks at this time to make sure you are on track. Each week at this time, write an email or Teams message to the instructor to let them know how things are going and if you have any questios.

Prerequisites - C or higher in CS 151.

CRN numbers - 53200 for the 001 face to face section, 52021 for the 301 online section

Required text

Class notes - Notes during class will mostly be kept in the CS 303 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.

Microsoft Teams - There is Team for our course. If you post questions there, these can be answered by anyone in the class, and everyone can see the Q&A that are coming up. You should see a CS 303 team in your teams list, or the direct link is CS 303 MS teams direct link

Announcements/Assignments/Quizzes

This section will be kept up to date with announcements of assigned reading, assignments, quizzes, etc. This will be kept as a "stack" with the most recent at the top of the list.

Assignments

Announcements

  • 2022-12-07 - Final exam quizzes. To get to the quizzes, go to canvas, then Quizzes, then look for the quizzes that are labeled as "final exam" quizzes. These will become available to take at 1pm, and they must be submitted by 3pm. Reminder that you should start with any previous ones you did not have an 80% on yet (according to the letter grade email), and then take the new ones, and then take any old ones you did not have a 90% on yet. Good luck!
  • 2022-12-06 - last 3 assignments due (last chance) Dec 8.
  • 2022-12-05 - CS 303 final updated to have links to practice quizzes to the new quizzes (graphs, big O asymptotics, complexity classes / running times, regular languages / expressions). Note that probability will not be on the final (no quiz for this).
  • 2022-12-07 - 1-3pm, canvas quizzes exam. Check canvas/zoom for the zoom link.
  • 2022-12-06 - 1-3pm, review session, and honors conversion project presentation on Mersenne primes and perfect #s. Check canvas/zoom for the zoom link.
  • 2022-12-01 - when are the last HW's "drop dead" due? If nobody needs my answers early next week, then it could Dec 7 or 8. After the first round of grading, if you have an opinion let me know. Default to be due Dec 7 or 8, pending what you think after the first round of feedback.
  • 2022-11-27 - discrete probability - we have to do at least some of this, so will start that today or tomorrow. See the OneNote notebook for notes and suggested reading.
  • 2022-11-27 - CS 303 final - a bit updated with how the final letter grade will be determined.
  • 2022-11-27 - Induction assignment - grading notes were emailed to everyone. You can submit again in Canvas up through Dec 4, and then I can do a video going over correct solutions. Of course, you can ask questions in lecture or by email/Teams as well. On the first time through, the highest was getting 5/10 correct.
  • 2022-11-22 - new assignments (see above) that are due Dec 4, start working on them soon. Also, have filled in an outline for the CS 303 final. I will get caught up on grading and then fill in the details for the final. The canvas part will be Wed Dec 7 from 1-3pm (and required to be face to face if you are in the face to face section, unless you get approval from me), and everyone will take the canvas part at the same time (unless you get approval from me). The interview portion will be available early next week up through Dec 9 at noon; those in the face to face section need to do it in person (unless you get approval from me).
  • 2022-11-16 - some assignments or quizzes or something. Working version of that - CS 303 final.
  • 2022-11-15 - reading - chapter 2 (regular languages) in Theory of Computation
  • 2022-11-14 - reading - halting problem in Theory of Computation, pg 163
  • 2022-11-10 - binomial theorem, ch 20. Next time - finish up uncountability, applications to programming. Next time - on to regular languages.
  • 2022-11-09 - no lecture today
  • 2022-11-08 - fun, which is bigger - 3^(1000!) or (3^1000)!
  • 2022-11-07 - no lecture tomorrow in this class, since it's election day.
  • 2022-11-07 - read up through ch. 18 in BB.
  • 2022-11-07 - note that for the final exam, the "interview" part - for those registered face to face, the interview will need to be in person. Just a head's up, and that will likely be for any time during exam week.
  • 2022-11-03 - NP-completeness reduction for Clique from SAT
  • 2022-11-01 - chapters on NP and contradiction in BB. Questions on scheduling classes?
  • 2022-10-27 - no class, take the exam today/tomorrow.
  • 2022-10-26 - MCS2 #7 - how to finish it, what was wrong yesterday (nothing, just didn't put it all together).
  • 2022-10-24 - Truth table proofs assignment 2 and Math for CS Review other assignments - submissions up through tomorrow 12:30pm, we can go over my solutions tomorrow.
  • 2022-10-24 - midterm exam - see CS 303 midterm for practice quizzes and more details. Try out the practice quizzes and if you don't understand how to do any of them, ask in class (or send questions by email/teams). If you think there are any mistakes let me know. Reminder - sign up for slot for midterm part 2 - https://cs.indstate.edu/scheduler
  • 2022-10-20 - no lecture today, I will be available for questions.
  • 2022-10-19 - update on midterm timing - canvas part will be open Oct 27-28, sign up for interview slot for after you will have taken the canvas part. Last 2 HW assignments (TT and MCS2) last chance due on Sunday (Oct 23), and then I'll give my solutions soon after.
  • 2022-10-18 - midterm outline - CS 303 midterm. That will be updated with more information (practice quizzes, sample questions) as it becomes available.
  • 2022-10-17 - midterm - timed on canvas part will be available Oct 27-28, you will have an interview portion with me as well. For the interview, sign up for a slot off of https://cs.indstate.edu/scheduler for some time after you plan to do the canvas part of the exam.
  • 2022-10-17 - a bit more in big O, start the Algorithms chapter in Building Blocks. Assignment for Induction is in Canvas now, so you can submit your work. I'll probably be looking at them on Wednesday.
  • 2022-10-13 - no lecture today.
  • 2022-10-12 - discuss problems 6 and 7 on the Induction assignment. Updates on grading "math for CS problems 2" - coming soon (probably a video).
  • 2022-10-11 - note that there will not be class on Thursday, Oct 13.
  • 2022-10-10 - due date on induction Oct 17.
  • 2022-10-10 - reading assignment - Big-O chapter in Building Blocks, section 14.7 in MCS (and/or google search for little o, little omega, etc. and pick something that you can follow along).
  • 2022-10-10 - truth table assignments 2 initial grading done. See the assignment for general grading notes. You received an email with comments on yours. If you didn't get 2/2 then you need to fix it, as indicated in the email you received. Note about the NOR gate problem in the grading notes - put a comment for your submission in Canvas for what you used (whether it be a solution for NOR or NAND); if you used something and do not add a comment, that is plagiarism.
  • 2022-10-05 - reading assignment - up through chapter on Trees in Building Blocks (for now, skipping the part in Trees on context free grammars and parse trees).
  • 2022-10-05 - more on recursion, finish from last time, also trees.
  • 2022-10-03 - no lecture today, I will be zoom just to answer any questions (not required to attend).
  • 2022-09-29 - advice - you demo the proof to yourself on the board or on paper.
  • 2022-09-28 - pair and meet - let me know if you want me to pair you up with someone.
  • 2022-09-27 - new assignment "pair and meet", see above.
  • 2022-09-27 - reading assignment - up through chapter on Induction in Building Blocks.
  • 2022-09-22 - interim grades - I have updated the grading part of the syllabus (below) for how I am scoring for the interim grades. I added grade items for all of this so you can see how I calculated it, and watch today's lecture to see how to check. Note that these are rough approximations, since we don't have many grades and you will have more chances to get pass ratings on old topics. We'll come back and look at these again in a few more weeks (after the mid-term).
  • 2022-09-21 - interim grades will be based on how many "pass" ratings, I'll do something with that before Tuesday.
  • 2022-09-21 - new assignments posted in canvas, cleaned up above. Due Sept 28. Start now.
  • 2022-09-20 - no lecture this day, work on the new assignment.
  • 2022-09-19 - new assignment listed above, due date TBD.
  • 2022-09-15 - coming up - Building Blocks graphs, some new assignments, some new challenge problems. Today we took an aside to go over Big-O a bit, since that is being looked at in CS 202 right now.
  • 2022-09-14 - puzzle challenge problems 1. Aside - RSA cryptosystem - examples now, proofs some time later, read the wikipedia page. Go to the job/career fair.
  • 2022-09-13 - puzzle challenge problems 1. You will present solutions to: 2=1 (Lexy), irrational powers (JF), log7(n) (). The other one is still a bit up in the air. How will they count? About 1/3 of the class got one correct.
  • 2022-09-13 - letter grades - will be based on getting pass rating on things, will be revisiting before interim grades.
  • 2022-09-13 - notes on grading for truth table proofs, proofs of irrationality, and running the Euclidean algorithm...
    • Scoring on each problem: 2 is pass, 1.5 is pass-. A pass should be required, right? One option is to revisit items that haven't been passed yet at the midterm (which will include an interview component).
    • I was hoping people would resubmit and fix problems. Some did, some didn't.
    • When I assign different numbers to different people, part of the reason is to ensure everyone is doing their own work. If you submit a solution for a problem that was not yours, that is suspicious (and extra work for me to have to decide on).
    • When it is required to visit the lab to demo your solution, then you need to do it.
    • Don't say things that are not true - check your proofs carefully.
    • A few people gave a proof of irrationality for a number that was not assigned to them, and looked like it was based off of an online resource. If you use something and don't cite it, that is plagiarism - you get a 0 on the assignment for the first offence, then F for the course on the second. And you created extra work for me. ;(
  • 2022-09-12 - no class/lecture today
  • 2022-09-08 - will continue to keep moving through Building Blocks, and also doing problems from MCS (in class, and probably also assignments). Will make up your next assignment after the current ones are graded (likely Monday).
  • 2022-09-07 - "challenge" problems from the end of today's lecture - our start is in the OneNote notebook under Proofs and then Problems.
  • 2022-09-07 - aside - examples/problems from MCS (Mathematics for Computer Science, link above in General Info).
  • 2022-09-07 - reading assignment Building Blocks chapters 6 (relations), 7 and 8 (functions).
  • 2022-09-06 - for the proofs assignments, please resubmit by 9/7 midnight.
  • 2022-09-06 - grading for the two proofs. Most people need to do edits to fix the truth table proof and irrationality proof. Check the rules of writing good proofs - Proofs. For the proof of irrationality, note that things are a tiny bit different for doing a proof with a composite number (check the wiki assignment link again for an example). For the gcd question, same thing - say what you are solving, and indicate what the answer is when you get to it. Also, you need to visit the help lab to have them sign off that you can explain/demonstrate your solutions. Also, remember that I am grading mostly "pass/fail", so you should revise and resubmit (partial credit won't be good enough for these).
  • 2022-08-29 - try finishing the last proof we were in the middle of.
  • 2022-08-29 - reminder to take quizzes today. new assignments due Friday, which include a check-in with the help lab - if you use the weekend to work on this class, that's okay too.
  • 2022-08-29 - reading assignment - Building Blocks chapter 5 (sets)
  • 2022-08-29 - FYI in terms of when I tend to reply to messages - starting some time around 7am depending on the day, up until about 4pm (with gaps for classes, meetings, etc.), then again roughly 8-10pm. Weekends I will often have longer periods of not checking messages but try to at least a few times per day.
  • 2022-08-24 - reading assignment - Building Blocks chapter 4 (number theory - integers)
  • 2022-08-22 - fyi, will use OneNote in the browser from now on (spacing wasn't looking right going back and forth between application and browser)
  • 2022-08-22 - reminder of the Hello Unix Lab assignment
  • 2022-08-18 - ungraded self-check - think about what the first DeMorgan's law should be, and verify or disprove with truth tables. Another question: is not (p and q) equivalent to p->q ?
  • 2022-08-18 - reading assignment - Building Blocks chapter 3 (proofs)
  • 2022-08-18 - reading assignment - Building Blocks chapter 2 (logic)
  • 2022-08-17 - reading assignment - Building Blocks chapter 1 (math review)
  • 2022-08-10 - to start off we will be following along from the beginning of Building Blocks for Theoretical Computer Science, so if you want to do some reading you can start taking a look at that.
  • 2022-08-09 - creation of this site, including the preliminary list of topics, outcomes, achievements, etc.

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

Grading and Assignments

We will be trying out what I am calling "achievements-based" grading. There are a series of skills, knowledge, and experiences that I want you to achieve. Your final letter grades will be based strictly on which of these you have completed. For each achievement, you can achieve the rating of incomplete, pass-, pass, pass+. The following will be our starting point for how letter grades will be assigned. I will reevaluate this throughout the term to make sure we are on track. I will also be setting the standards for pass-, pass, and pass+ for each of the achievements as we get to them in the course.

Interim grades - I will look at the bullet points below which have already been evaluated. Grades will be assigned as follows:

  • A - pass rating on everything so far, at least one challenge/puzzle problem completed.
  • A- - pass rating on everything so far
  • B - at least 2/3 pass rating
  • C - at least 1/2 pass rating, at least 2/3 pass- or higher
  • D - at least 1/2 pass rating

D

  • Pass- or higher achievement for all of the following
  • Hello unix lab (at least 2/2)
  • Math notation (at least 80%)
  • Math bases (at least 80%)
  • Truth table proof (at least 1.5/2)
  • Proof that a number is irrational (at least 1.5/2)
  • Euclidean algorithm - demo of running the algorithm (at least 1.5/2)
  • We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.

C

  • Pass or higher achievement for all of the above (at least 90% on quizzes, at least 2/2 on assignment problems)
  • We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.

B

  • We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.

A

  • In addition to the above...
  • At least 1 puzzle/challenge problem solved correctly (pass rating)
  • Pass+ rating on most of the above
  • Pass or higher achievement for all of the following
  • We will be filling in the minimum standards here as we begin the course and start having assignments and quizzes.

Achievements can be earned based on quizzes, assignments, in-class work, and exams. Rather than having numerical scores for these, I will use them to mark off your achievements. Note that achievements can be "lost" if you demonstrate a skill early in the term and then demonstrate a lack of the skill later in the term. I expect this will not normally be the case, but I will continue to evaluate you based on all of the skills throughout the term.

Late Work - Assignments will generally be available to still handin for around a week after their due date. Once the solutions are posted and discussed, late submissions will no longer be graded. Quizzes will normally need to be taken on the day they are due, or perhaps within a few days of when they are due. Solutions will normally be discussed or posted within a week of their due date. Not accepting late work that is more than about a week old is in part because it takes much longer to grade quizzes/assignments that are no longer super fresh in the instructor's head, and in part to try to keep everyone in the class working on the same material.

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

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/scheduler 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 and exams you will normally have a 24 hour period during which to take the quiz/exam (note that different students will have slightly different questions and any communication between students about quiz/exam content is academic misconduct).

So also the General Information section at the top of this page for setting up a normal check-in time with the instructor.

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

Retrieved from "https://cs.indstate.edu/wiki/index.php?title=CS_303_Fall_2022&oldid=3597"