CS173
CS173 (Discrete Structures) is a 3-credit hour course that is specifically required for CS majors and CEs and qualifies as a technical elective for EEs. It is offered in both the fall and spring. MATH213 may substitute this course for ECE majors, and cannot for CS majors.
Content Covered
The topics covered in CS 173 will introduce number theory concepts, mathematical proofs, especially inductive proofs, set theory, graph theory, recursive relations, trees, counting, common algorithms, and big O analysis.
Topics
- Math Concepts and Basic Boolean Logic
- Proofs and Number Theory
- Modular Arithmatic and Sets
- Relations
- Functions
- Graphs and 2-way Bounding
- Induction
- Recursive Definition
- Trees and Grammars
- Big-O and Algorithms
- NP Time
- Collections of Sets
- Contradiction State Diagrams
- State Diagrams Countability
Prerequisites
CS 173's few prerequisites are of limited importance to being able to succeed in the course. Coding experience is mainly helpful for analyzing Big-O for several algorithms but also helps in the specific mindset it promotes. Having the prerequisites done is still recommended, especially since the requirement for ECE students to take ECE 220 before this course has been enforced recently.
When to Take it
Due to this class being a hard prerequisite for CS 225, we now recommend taking MATH213 instead of CS173 concurrently with ECE 220 instead.
Discrete Structures officially a prerequisite for CS 225, which is the gateway to most, if not all CS courses. As such, take Discrete Structures as early as possible, especially for Computer Engineering majors. Most higher-level CS courses will definitely cover discrete math concepts so the topics introduced in CS 173 will be reviewed again and again. Furthermore, a lot of the computer engineering concepts are also introduced in this class and so it will complement a lot of early computer engineering classes, like ECE 120 and ECE 220. Though it is possible to do well even when taking discrete structures concurrently with a coding class, like ECE 220 or CS 125, it is highly recommended to take the coding class before taking CS 173. Exposure to coding will greatly help the understanding of discrete math and taking them concurrently will most likely just be a bigger burden to try and grasp the concepts faster.
Course Structure
Lecture
CS173 has 2-5 asynchronous lecture videos per week which are posted on the course website. Aside from this, lecture notes and sections to read are also posted, which go over the topics covered in the videos.
Tutorial and Homework
CS173 has tutorial sections similar to discussion sections of other classes. They are held in a lecture hall and nothing is required to be turned in during class. In tutorial, you can work on extra problems with classmates, while CAs and TAs walk around to answer any questions you may have.
The pretutorial checkpoints are due the day before tutorial as an autograded PrairieLearn homework. They are simpler questions designed to make sure that you have completed the readings and watched the lecture videos online.
The homework is due 4 days after tutorial. These are also due on PrairieLearn and you can resubmit them as many times as you want.
Exams and Grading
CS173 has 6 smaller Examlets and a final, and typically does not curve exam scores. Exam scores make up roughly 90% of a student's grade and the remainder comes from pretutorial checkpoints and homework.
The lowest checkpoint grade and lowest homework grade are dropped when computing your final averages. You can submit these multiple times, so it should not be too difficult to ultimately get 100% on all of them.
At the end of the semester, you can optionally choose to retake one of the examlets. You do not have to declare in advance which you're retaking, the choices will be offered to you when you've started the retake at the CBTF. Your retake score will replace your original score on that examlet if it is better.
Instructors
Professor Margaret Fleck and Professor Benjamin Cosman usually teach CS 173; however, there may be some different professors in different semesters. The professors historically are great at carefully explaining confusing material during their office hours and to a limited degree lecture. They typically take extra care to ensure that all questions are answered and the material is learned during these office hours.
Course Tips
Discrete Structures can be a straightforward class but it is very easy to fall behind at the end of the semester. The homework can be difficult, so it is good to check answers with other students. The examlets usually consists of one large proof-like problem and other smaller problems. These often consist of similar problems shown on the older exams, so reviewing those before the examlets can be very helpful.
Life After
CS 173 is the gateway to all higher-level CS and ECE tech-electives. The content seen in CS 173 will be seen again and again for most ECE/CS tech-electives. CS 225 (Data Structures) can be taken afterward, if not taken concurrently. For students who enjoy CS theory, consider CS 374A (Introduction to Algs & Models of Computation) and CS 473 (Fundamental Algorithms), which both build on the fundamentals introduced in CS 173.
Infamous Topics
- Induction Proofs
- Big-O Analysis
- Set and Graph Theory