Algorithmic Analysis

Abstract Data Type (ADT)

Stack (abstract data type)

Queue (abstract data type)

Map (higher-order function)

Case Analysis

Algorithm Analysis

Asymptotic Analysis

Recursive Algorithm Analysis

Binary Search Tree (BST)

Hashing

AVL Trees

Tree (data structure)

Graphs

Breadth-first search (BFS)

Depth-first search (DFS)

Topological sorting

Graph traversal

Minimum Spanning Tree (MST)

Disjoint Sets

Dynamic programming

Graph Modelling

Sorting algorithm

P/NP

Computer memory

Shortest paths

Heap (data structure)

CSE 373 Data Structures and Algorithms University of Washington Summer 2022 This course focuses on common data structures and algorithms. It integrates theoretical understanding with practical exercises, preparing students for software-related roles and industry technical interviews. Programming projects, unit testing, and source control techniques are emphasized.  In this course, you will gain a strong theoretical and conceptual understanding of common data structures and algorithms, as well as how to apply them within larger programming projects.

Specific topics we will cover include:

- **Data structures and ADTs**: lists, stacks, queues, sets, dictionaries, linked lists, arrays, trees, balanced trees, AVL trees, hash tables, priority queues, binary heaps, and disjoint sets.
- **Graphs and graph algorithms**: graph search, shortest path, and minimum spanning trees.
- **Algorithm analysis**: asymptotic analysis, and P and NP complexity classes.
- **Sorting** and divide-and-conquer.

This course is designed to have a practical component to help you gain basic familiarity with techniques used within industry. In particular, you’ll be asked to:

- Work on **programming projects** and integrate your work in an existing codebase.
- Learn how to use an **industrial-strength IDE**.
- Learn techniques for **checking correctness**: writing unit tests with JUnit, designing and checking invariants, etc.
- Learn how to collaborate on a single code base using **source control** repositories.

Finally, this course emphasizes the importance of making and justifying design decisions. Taken together, all of the above skills are chosen to set you up for success in a software-related role. In fact, this course is typically regarded as useful preparation for industry and technical interviews. [CSE 143](https://courses.cs.washington.edu/courses/cse143/), or similar Java programming experience. 

CSE 373 Data Structures and Algorithms

Data Structures and Algorithms

Counting

Combinatorics

Conditional probability

Bayes' theorem

Independence (probability theory)

Random variable

Expectation

Variance

Bernoulli distribution

Binomial distribution

Poisson distribution

Continuous Random Variables

Normal distribution

Joint probability distribution

Statistical inference

Beta distribution

Central Limit Theorem

P-Value

Maximum Likelihood Estimation (MLE)

Maximum A Posteriori (MAP)

Naive Bayes

Logistic Regression

Bootstrapping

CS 109 Probability for Computer Scientists Stanford University Spring 2023 This course offers a thorough understanding of probability theory and its applications in data analysis and machine learning. Prerequisites include CS103, CS106B, and Math 51 or equivalent courses. CS109: Probability for Computer Scientists starts by providing a fundamental grounding in combinatorics, and then quickly moves into the basics of probability theory. We will then cover many essential concepts in probability theory, including common probability distributions, properties of probabilities, and mathematical tools for analyzing probabilities. The last third of the class will focus on data analysis and machine learning as direct applications of probability we've learned in the weeks prior. Read more here to learn what CS109 is all about. This is going to be a great quarter and we are looking forward to the chance to teach you!! After you're finished with CS109, we hope you'll have achieved the following learning goals:

- Reason about situations using probabilities, expectation, and variance.
- Feel comfortable learning about new probability concepts beyond the scope of this class (e.g., through one's own research, studies, or interests).
- Write programs to simulate random experiments and to test experiment hypotheses.
- Understand and implement simple machine learning algorithms like Naive Bayes and Logistic Regression.

## Course Topics

Here are the broad strokes of the course (in approximate order). More information is available on our Schedule page. We cover a very broad set of topics so that you are equipped with the probability and statistics you will see in your future CS studies!

- Counting and probability fundamentals
- Single-dimensional random variables
- Probabilistic models
- Uncertainty theory
- Parameter estimation
- Introduction to machine learning The prerequisites for this course are CS103, CS106B, and Math 51 (or equivalent courses). Probability involves a fair bit of mathematics (set theory, calculus, and familiarity with linear algebra), and we'll be considering several applications of probability in CS that require familiarity with algorithms and data structures covered in CS106B. Here is a quick rundown of some of the mathematical tools from CS103 and Math 51 that we'll be using in this class: multivariate calculus (integration and differentiation), linear algebra (basic operations on vectors and matrices), an understanding of the basics of set theory (subsets, complements, unions, intersections, cardinality, etc.), and familiarity with basic proof techniques. We'll also do combinatorics in the class, but we'll be covering a fair bit of that material ourselves in the first week. Past students have managed to take CS106B concurrently with CS109 and have done just fine. CS103 is the pre-requisite that we rely on the least. See our FAQ for more information. ## Optional Textbook

Sheldon Ross, *A First Course in Probability* (10th Ed.), Pearson Prentice Hall, 2018.

This is an optional textbook, meaning that the text is not required material, but students may find Ross offers a different and useful perspective on the important concepts of the class. Suggested, optional reading assignments from the textbook (10th Ed.) are in the schedule on the course website. The 8th, 9th, and 10th editions of the textbook are all fine for this class.

*Borrowing the textbook online*: HathiTrust, a library archive of which Stanford is a member, has granted the university online access to the 8th edition (2010) for the duration of the Fall quarter. The "check out" system works similarly to print reserves: A user can check out the book an hour at a time as long as they are actively using it. Access guidelines are on the [HathiTrust How To Use It webpage](https://www.hathitrust.org/ETAS-How-To). Once you're logged in, the book is at [this link](https://catalog.hathitrust.org/Record/006904347).

All students should retain receipts for books and other course-related expenses, as these may be qualified educational expenses for tax purposes. If you are an undergraduate receiving financial aid, you may be eligible for additional financial aid for required books and course materials if these expenses exceed the aid amount in your award letter. For more information, review your award letter or visit the [Student Budget website](https://financialaid.stanford.edu/undergrad/budget/index.html).

CS 109 Probability for Computer Scientists

Mathematical Foundations

Analysis of algorithms

Algorithmic Analysis

2 courses cover this concept

CSE 373 Data Structures and Algorithms

CS 109 Probability for Computer Scientists