CS 173 is a computer science course at the Computer Science department of the Grainger College of Engineering at the University of Illinois Urbana-Champaign.
This course is an introduction to the theoretical side of computer science. It teaches you how to construct proofs, as well as read and write literate formal mathematics.
It also does a tour of standard concepts used in theoretical computer science, such as modular arithmetic, sets and functions, relations, trees and graphs, counting and countability, and asymptotic analysis of algorithms.
This course is typically offered in fall, spring, and sometimes summer terms. Remember, credit is not given for both CS 173 and MATH 213.
Check out: UIUC academic calendar, important dates and deadlines.
Table of Contents
CS 173 prerequisites
The course involves discrete mathematical structures frequently encountered in the study of Computer Science. Sets, propositions, Boolean algebra, induction, recursion, relations, functions, and graphs.
You’ll need one of CS 124, CS 125, ECE 220; one of MATH 220, MATH 221.
This course assumes that you have significant practice with recursion, have worked with basic data structures (e.g. linked lists, trees, or graphs), and have seen simple examples of big-O algorithm analysis.
Students without this background sometimes think they are ok towards the start of the term, but get into trouble midway through the course.
To take this course, you must have completed Calculus I (Math 220 or 221) and CS 125 or ECE 220. UIUC Banner is now enforcing these prerequisites automatically, so you will not be able to add CS 173 if you don’t have them.
If you have credit for a prerequisite course but it is not visible on your transcript, you must speak to the CS academic office for an override.
This would include students with incoming transfer credit, exchange students, and students who pass the CS 125 proficiency exam at the start of the term.
Be aware that the academic office is swamped during registration and also at the start of the term, so be patient especially if you are a non-major.
What can be used to satisfy cs 173 prerequisites?
- Since registration happens in the middle of the previous term, you’ll be allowed to register for CS 173 based on the fact that you’re currently taking the prerequisite course(s). If you fail a prerequisite class, you’ll have to drop CS 173.
- You can take CS 173 if you have credit for Calculus II or III, but mysteriously no credit for Calculus I. However, you should see your advisor to sort out your situation if your major (e.g. CS) explicitly requires Calculus I for graduation.
- You cannot satisfy the programming requirement using AP CS, CS 101/105, and/or ECE 120. These courses do not cover some of the critical background material.
- You may not take a prerequisite course (e.g. CS 125 or ECE 220) concurrently with CS 173. CS 173 uses certain critical material before these courses cover it.
- Having taken much of a prerequisite course (e.g. Calc I) in high school does not change this rule. If you cannot place out of the course at U. Illinois, that means you don’t have the background to take CS 173.
- You may satisfy the intro programming requirement by passing the CS 125 proficiency exam (in C++ or Java), at the start of term. Have a backup plan in case you don’t pass it.
- It is also sufficient if you pass the ECE 220 proficiency exam at the start of term. (The ECE department gives this only by special arrangement, primarily to transfer students).
CS 173 topic list
Below are the topics you’ll study on CS173: Discrete Structures at UIUC.
- 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
Discrete structures course 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).
- Write literate proofs using straightforward application of standard outlines (direct, contrapositive, contradiction, upper/lower bounds).
- Write inductive proofs, including proofs on trees.
- State and apply basic definitions, facts, and notation for commonly used discrete math constructs.
- 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.
- Classify examples the complexity of very simple examples in terms of countable versus uncountable, polynomial versus exponential, decidable versus undecidable.
CS 173 proficiency
If you have already mastered the material covered in certain Illinois Computer Science courses, you may receive credit and satisfy prerequisites by taking a proficiency exam.
Here you will find details about how to prepare and sign up for Illinois CS proficiency exams.
Proficiency exams are similar in coverage and scope to a comprehensive final exam. They are intended to ensure that you are well-prepared for later courses in the same subject area.
To get proficiency credit, you must score at least a B- on the proficiency exam. If you don’t pass the exam, nothing appears on your record. You may either take the course (recommended) or re-take the proficiency exam. Specific passing criteria are at the discretion of each course instructor.
For the core programming sequence (CS 124, CS 128, CS 225) you must attempt the proficiency exams in order. Results are available immediately for the CS 124 and CS 128 exams, so you’ll know whether you can continue with the sequence.
Proficiency exams are offered at the beginning of each semester, and at other times at the discretion of the computer science department.
How to sign up for CS 173 proficiency exam
Note that the student code does not allow you to take the CS 173 Proficiency Exam after taking either CS 225 or CS 374.
- Sign up by navigating to the proficiency moodle “course”.
- UIUC Moodle will ask you to log in with your netID.
- Next, enroll in a course named “CS 173 proficiency exams (academic year 2021-22)”. Enroll yourself.
- You will return to this course when it’s time to take the proficiency exam.
- The moodle site now has a brief activity that will allow you to practice typing equations and diagrams into the online interface.
- You will not be able to upload handwritten work for the exam.