skip to main content

CS 173 - Discrete Structures

Fall 2020

Discrete StructuresCS173ADA51495OD01300 - 1350 R    
Discrete StructuresCS173ADB51497OD01400 - 1450 R    
Discrete StructuresCS173ADC51499OD01500 - 1550 R    
Discrete StructuresCS173ADD60279OD01600 - 1650 R    
Discrete StructuresCS173ADE63143OD01100 - 1150 R    
Discrete StructuresCS173ADF71539OD01200 - 1250 R    
Discrete StructuresCS173ADG63145OD01300 - 1350 R    
Discrete StructuresCS173ADH63146OD01400 - 1450 R    
Discrete StructuresCS173ADI71542OD01500 - 1550 R    
Discrete StructuresCS173ADJ59603OD01600 - 1650 R    
Discrete StructuresCS173ADK63147OD01700 - 1750 R    
Discrete StructuresCS173ADL71541OD01700 - 1750 W    
Discrete StructuresCS173ADM59602OD01200 - 1250 R    
Discrete StructuresCS173AL130102OLC30930 - 1045 T R    Benjamin Cosman
Discrete StructuresCS173ALP72280OLC30930 - 1045 T R    Benjamin Cosman
Discrete StructuresCS173BDA51500OD01000 - 1050 R    
Discrete StructuresCS173BDB63144OD00900 - 0950 R    
Discrete StructuresCS173BDD51496OD01700 - 1750 R    
Discrete StructuresCS173BL240083OLC31100 - 1215 T R    Patrick Lin
Discrete StructuresCS173BLR72281OLC31100 - 1215 T R    Patrick Lin
Discrete StructuresCS173CDA60278OD01500 - 1550 W    
Discrete StructuresCS173CDB51498OD01600 - 1650 W    
Discrete StructuresCS173CDC51469OD01100 - 1150 R    
Discrete StructuresCS173CL371734OLC31230 - 1345 T R    Mahesh Viswanathan
Discrete StructuresCS173CLR58923OLC31230 - 1345 T R    Mahesh Viswanathan

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 125, ECE 220; one of MATH 220, MATH 221. Class Schedule Information: Students must register for a lecture and discussion section.

Subject Area

Theory / Math



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
Induction and recursive definition
big-O, algorithms, NP
state diagrams

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


Last updated

2/3/2019by Margaret M. Fleck