GUIDESacademicssucceed in course xsucceed in 441

How to Succeed in CS0441, Discrete Structures for Computer Science

Dylan Feehan

Preface: If you want to do well in any course, the bare minimum is attending all lectures and doing all homework assignments.

What is Discrete Structures for Computer Science?

CS 0441 Discrete Structures for Computer Science is a mathematics course which focuses on the study of mathematical structures that are discrete rather than continuous. This means that the objects within the mathematical structures that you'll learn about are distinctly separated values. This course will focus heavily on the integers (which are discrete by nature), whereas a continuous field like calculus focuses more on real numbers. Lets start with a birds-eye view of the main topics covered in 441:

  • Logic and Proofs

    • This is the theoretical foundation of the course which teaches you how to derive additional information from some given information. Thoroughly understanding the proofing techniques is incredibly important because you will be using these techniques throughout the rest of the course.

  • Sets

    • Sets are unordered collections of distinct objects, which have their own unique properties and laws. An example of a set is Z, the set of all integers. Another example is the set V of all vowels, V = {a, e, i, o, u}. You will learn about set operations, functions which map from sets to sets, and you will use sets when doing proofs.

  • Functions

    • Functions are mappings from inputs to outputs, from set A to set B. Functions also have their own properties and sub-topics, such as correspondences and composition. For example, think about the function f(x) = x^2 + 1 which maps from Z->Z+, from the set of all integers to the set of all positive integers.

  • Sequences and Summations

    • In contrast to the unordered sets, sequences are ordered structures. Take for example the sequence 0, 1, 1, 2, 3, 5, 8, ... , the well known Fibonacci sequence, where each number is the sum of the two preceding numbers (given first is 0 and second is 1). Summations are the addition of terms over a sequence, and these have handy applications to algorithm analysis.

  • Recursion

    • A more theoretical, mathematical, and proof-focused version of the recursion you've seen in a programming class. Also, you'll be able to do much more with recursion in 441. You can use recursion to define sequences like the Fibonacci sequence, you can define sets and functions recursively.

  • Counting

    • Combinatorics, pronounced (com-bin-a-tor-icks), is the study of arranging objects. You'll learn about how many ways you can arrange a number of objects in ordered or unordered arrangements of objects. For example, how many bit strings can be made from a sequence of 8 bits?

  • Probability

    • Probability centers around the likelihood of a certain event happening given a set of conditions. You'll learn about finite probability, probabilities of compliments and unions of events, conditional probabilities, dependent vs. independent events, and much more.

  • You may cover either / both of these topics:

    • Induction: a powerful proofing technique. You'll learn about mathematical induction, strong induction, and structural induction.
    • Relations: the study of relationships between elements of sets.

Why do we study discrete mathematics in computer science?

The applications of discrete math shine well in math-y CS subjects. Consider algorithm analysis, databases, machine learning/AI, networking, compression, computability theory, cryptography, writing proofs about algorithms, etc. Although it helps with the theoretical side of CS, discrete math is also about connecting theory to practice. If we understand the math which underlies our code and algorithms, we can make simpler and more efficient software.

How to succeed in 441:

Remember, the goal of higher education is education, not getting good grades. The primary goal should be learning and understanding the concepts. Luckily, deep conceptual understanding of course material usually yields a good grade :)

You don't have to follow all of these guidelines to pass the course, but these are my recommendations if you want to walk away with as much knowledge as possible.

High level ideas

  • Have a problem solving mindset

    • Get curious about the topics and problems
    • Approach challenges with an open mind
    • Appreciate and understand clever solutions, whether or not you came up with them
    • Don't just headbut the problem, try to view it and solve it from all angles
  • Go to office hours

  • Engage with the course material before, during, and after each lecture

    • Before lecture: read the chapter and try some exercises
    • During lecture: focus, and think conceptually about what the professor is saying
    • After lecture: do the assignments, do more practice problems, write and solve your own problems, etc
  • Practice proofs frequently

  • You WILL get stuck on many problems. It's natural and it happens to everybody. Spend time with the problem, get familiar and comfortable with it, and the answer will come to you eventually. If you want to do math right, enjoy being stuck

  • Even if you're really stuck, DO NOT look up the answer on the internet. Especially on a homework, that's cheating. Cheating = F in the course, and you rob yourself of the opportunity to build your problem-solving muscles. Often times it is helpful to step away from a problem or even sleep on it (one of many reasons to start assignments early)

Preparation

This section will be about the preparation you can do before the semester. Walking into the first day of lecture with a solid understanding of the course material is a fantastic learning advantage and confidence booster. Before the semester starts, we recommend learning a little bit about discrete math on your own. Regarding depth at which you should read / learn, we recommend going an inch deep and a mile wide. Instead of learning only the first course topic in its entirety, learn a little bit about all of the topics.

Learning everything about logic and proofs before the semester will just make the first month of class boring, and the learning benefits will be over as soon as the next topic beings (which means your workload will increase quite a bit). If you learn a little bit about every topic, you'll have the learning advantage throughout the entire semester, and your workload will stay more consistent. That being said, if you find yourself excited about a particular topic and you wish to read deeper, do it!!!!

Readings

We recommend readings the assigned textbook chapter class. Coming to class with a sound understanding of what will be taught in lecture is profoundly helpful. It's helpful to hear certain topics explained from a different perspective. Your professor might not explain a concept in a way that suits you, so it's nice to have the textbook explanation (don't forget, a textbook is really a professor. Dr. Rosen in this case). I've always found it beneficial to read ahead before class, then use the lecture as more of a review / study session, that way I never feel like I'm actually studying. It works well to read with medium depth, try to understand the core concepts of the reading. If you can't wrap your head around a difficult idea, wait until lecture to address it.

If you didn't have the time or energy to do any reading, that's okay. Quickly look through the lecture slides before class to get a glance at the topics and concepts to be covered. You don't want any surprises during lecture!

The textbook

Discrete Mathematics and its Applications by Kenneth Rosen is a fantastic textbook. The concepts are explained well and there are in-text exercises to get you ready for the end-of-chapter problems. These in-text exercises are notated by EXAMPLE X in the left margin, and they consist of a small problem followed by a solution. Try solving the exercises by hand before looking at the solution. This is a fantastic way to engage with the material before class, even if you only do a few problems. At the end of each chapter is around 50 practice problems, and the solutions to the odd-numbered problems can be found at the end of the book.

Homeworks

Start the homeworks as early as possible. You don't want to be stuck having to write 5+ proofs with 3 hours until the submission deadline. If you get stuck on a problem, move on and finish as many as you can. Then, go to office hours and address the problems that you are stuck on. Also, do the starred problems in the textbook (they may be bonus questions). While you may get stuck on the regular problems, you will get stuck on the starred ones. These provide fantastic opportunities to get stuck when attempting questions that require a bit more creativity.

When the homework is graded and you see which problems you got wrong, figure out why. This will fill in important gaps in knowledge that will be important for exams. Try odd problems (which have answers) that are similar to those you got wrong. Try solving the problem again from scratch, or try solving a simpler version of the same problem to see where your weaknesses lie. Refer back to the text or lecture recording and re-learn a topic if you're struggling with it. If you still cannot to solve the problem, see the next bullet.

Go to office hours (UTA or prof) and ask why you got the problems wrong that you did. If you go soon after the assignment is graded rather than right before an exam, it prevents crowding during the UTA's office hours. Crowding is stressful for the UTAs and it prevents some students from getting their needs addressed.

The homeworks will start out relatively easy, but they will ramp up in difficulty very quickly. Once proofs are introduced, homeworks will probably take about twice the amount of that they did before.

Studying for exams

As with most CS courses, avoid rote memorization. Computer science is very a conceptual field and memorization plays a minuscule role. What's important is understanding the systems / patterns, conceptualization, and problem solving, all of which are skills that can be strengthened with practice. The odd-numbered practice problems at the end of every chapter are very helpful and their answers can be found at the end of the book.

Conclusion:

You can learn a massive amount of information from this course. You will have better problem solving skills, you'll be better prepared to understand theoretical topics in CS, and your logical thinking will be much more sound. This is a challenging course, but if you spend enough time engaging with the material you will succeed! Remember, if a course isn't challenging, it's probably not increasing the value of your education.

Last updated: Jul 28th 2023