Course Details

  • Course Number: 01:198:206
  • Course type: Undergraduate
  • Semester 1: Fall
  • Semester 2: Spring
  • Credits: 4
  • Description:

    Provides the background in combinatorics and probability theory required in design and analysis of algorithms, in system analysis, and in other areas of computer science.

  • Prerequisite information:

    01:198:205 or 14:332:20201:640:152. Credit not given for this course and 01:640:477 or 14:332:226.

    - A grade below a "C" in a prerequisite course will not satisfy that prerequisite requirement.

  • Course links: 01:198:205 - Introduction to Discrete Structures I
  • This course is a Pre-requisite for the Following Courses: 01:198:334 - Introduction to Imaging and Multimedia, 01:198:344 - Design and Analysis of Computer Algorithms, 01:198:352 - Internet Technology, 01:198:425 - Brain-Inspired Computing, 01:198:460 - Introduction to Computational Robotics, 16:198:522 - Network and Combinatorial Optimization Algorithms
  • Topics:

    Counting: Binomial Coefficients, Permutations, Combinations, Partitions.
    Recurrence Relations and Generating Functions.
    Discrete Probability:
    Events and Random Variables;
    Conditional Probability, Independence;
    Expectation, Variance, Standard Deviation;
    Binomial, Poisson and Geometric Distributions; law of large numbers.
    Some Topics from Graph Theory: Paths, Components, Connectivity, Euler Paths, Hamiltonian Paths, Planar Graphs, Trees.

  • Expected Work: Weekly assignments
  • Exams: 1 or 2 tests, Final Exam
  • Learning Goals:

    Computer Science majors ...

    • will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).
    • will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.
    • will be prepared for the next step in their careers, for example, by having done a research project (for those headed to graduate school), a programming project (for those going into the software industry), or some sort of business plan (for those going into startups).