Course Websites

CS 173 - Discrete Structures

Last offered Spring 2022

Official Description

Discrete mathematical structures frequently encountered in the study of Computer Science. Sets, propositions, Boolean algebra, induction, recursion, relations, functions, and graphs. Course Information: Credit is not given for both CS 173 and MATH 213. Prerequisite: One of CS 124, CS 125, ECE 220; one of MATH 220, MATH 221.

Related Faculty

Subject Area

Theory / Math

Text(s)

Varies

Learning Goals

Predicate logic: determine the truth of statements, perform simple transformations (esp. negation), accurately apply formal definitions (esp. vacuous truth cases, attention to variable types and scope) (6)
Write literate proofs using straightforward application of standard outlines (direct, contrapositive, contradiction, upper/lower bounds). (3)
Write inductive proofs, including proofs on trees (3), (6)
State and apply basic definitions, facts, and notation for commonly used discrete math constructs (3)
Derive big-O running time for simple pseudocode examples, especially recursive examples. Includes finding closed-forms for recursively-defined formulas using unrolling and recursion trees (6)
Classify examples the complexity of very simple examples in terms of countable versus uncountable, polynomial versus exponential, decidable versus undecidable (6)

Topic List

logic and proofs
number theory
sets and collections of sets
relations
functions
graphs
Induction and recursive definition
trees
big-O, algorithms, NP
state diagrams
countability

Assessment and Revisions

Revisions in last 6 years Approximately when revision was done Reason for revision
New Textbook Spring 11-Spring 2013 Integrate logic and proof learning throughout term, relate math to applications, modernize
On-line activities Fall 2011-Spring 2013 (on-going) Move simple material out of lectures, aid learning with drill, help students prepare for lectures and be more engaged,
On-line homework submission with rubric grading Fall 2012-Spring 2013 Simplify submission process, encourage quality writing product, enable research into automated feedback

Required, Elective, or Selected Elective

Required

TitleSectionCRNTypeHoursTimesDaysLocationInstructor
Discrete StructuresADA31187DIS00900 - 0950 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADB48263DIS01000 - 1050 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADC48264DIS01100 - 1150 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADD57329DIS01200 - 1250 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADE57330DIS01300 - 1350 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADF57446DIS01400 - 1450 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADG48265DIS01500 - 1550 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADH61915DIS01600 - 1650 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresADI61916DIS01700 - 1750 W  1304 Siebel Center for Comp Sci Benjamin Cosman
Discrete StructuresAL139311LEC30930 - 1045 T R  1002 Electrical & Computer Eng Bldg Benjamin Cosman
Discrete StructuresALP61102LEC30930 - 1045 T R  1002 Electrical & Computer Eng Bldg Benjamin Cosman
Discrete StructuresBDA48266DIS00900 - 0950 F  1111 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresBDB48267DIS01000 - 1050 F  1111 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresBDC50441DIS01100 - 1150 F  1111 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresBDD50442DIS01200 - 1250 F  1111 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresBDE51087DIS01300 - 1350 F  1111 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresBDF51089DIS01400 - 1450 F  1111 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresBL250094LEC31230 - 1345 T R  1404 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresBLR50093LEC31230 - 1345 T R  1404 Siebel Center for Comp Sci Payam Delgosha
Discrete StructuresCDA71613DIS01200 - 1250 R  1111 Siebel Center for Comp Sci Madhusudan Parthasarathy
Discrete StructuresCDB71614DIS01300 - 1350 R  1111 Siebel Center for Comp Sci Madhusudan Parthasarathy
Discrete StructuresCDC71615DIS01400 - 1450 R  1111 Siebel Center for Comp Sci Madhusudan Parthasarathy
Discrete Structures- HonorsCL171611LEC30930 - 1045 T R  0216 Siebel Center for Comp Sci Madhusudan Parthasarathy
Discrete Structures-HonorsCLQ71612LEC30930 - 1045 T R  0216 Siebel Center for Comp Sci Madhusudan Parthasarathy