Welcome to CSE21. This course is intended to introduce you to the broad field of algorithms and give you the mathematical tools needed to study algorithms and their efficiency. You will learn about sorting and searching, asymptotics, recursion, graphs, enumeration, and discrete probability. Understanding these topics and being able to work out related problems will be essential to your work as a computer scientist.
Analyzing Algorithms
1 Analyzing iterative algorithms
(Minsort, Bubblesort, Insertionsort, Linear Search, Binary Search):
Correctness and Time Analysis
2 Analyzing recursive algorithms
(Edges in an undirected graph, Exponentiation, Towers of Hanoi, Merging sorted arrays,
Binary strings, Ternary strings): Recurrences, Correctness and Time Analysis
3 Divide-and-Conquer (Mergesort, Multiplication of two n-digit numbers), Master Theorem
4 Worst-case analysis of algorithms: Ron Graham‘s results
Counting
1 Product and Sum rule
2 Permutations, Combinations
3 Counting Binary Strings, 4-digit-PINs, 4-letter-strings
4 Counting Binomial coefficients and identities, Counting Paths
5 Counting using Inclusion and Exclusion
6 Counting using the Complement
Probability
1 Basic definitions, uniform and binomial distribution, Hypothesis testing
2 Probability and Counting
3 Conditional Probabilities and Bayes' Theorem
4 Expected values and linearity of expectations
5 Birthday Paradox, Randomized algorithms and Hashing
Graphs and graph algorithms
1 Basic definitions, Max. number of edges, Representing graphs
2 Euler and Hamilton
3 Breadth-First-Search and Depth-First-Search
4 Minimum Spanning Trees (Prim's algorithm)
5 Topolgical Sorting (Kahn's algorithm)
6 Single-source Shortest Paths (Bellman/Ford, Dijkstra, Bellman)
Lectures: We will upload the lecture slides on Canvas and provide videos where the content of the slides is explained. Most of the videos are about 10-15 minutes long. We will meet online on Zoom during the regular lecture hours.
Discussions: Homework questions will be similar to the exam questions. The homework will not be graded, however, we highly recommend you to practice using these questions for an optimal preparations of the exams. Discussions will be online on Zoom every Thursday from 2:00 pm - 3:50 pm. Students who are still not sure about the solutions after discussions are more than welcome to join our TAs and/or Tutors at weekly Zoom office hours.
We will upload the lecture slides, videos, homework discussions and additional material on CANVAS.
We will be communicating with you and making announcements through the online question and answer platform PIAZZA. We ask that when you have a question about the class that might be relevant to other students, you post your question on PIAZZA instead of emailing us. That way, everyone can benefit from the response. Students who are especially active on Piazza and help other students to understand the material will earn some extra credit.
| Name | Role | |
| Oliver Braun | Instructor | olbraun (at) cs.ucsd.edu |
| Dheeraj Mekala | Teaching Assistant | dmekala (at) eng.ucsd.edu |
| Yihe Tang | Tutor | yitang (at) ucsd.edu |
We will have two exams. After your weighted average (Midterm, Final) is calculated, letter grades will be assigned based on the following curved grading scale:
| A+ | A | A- | B+ | B | B- | C+ | C | C- |
| 97 | 93 | 89 | 85 | 81 | 77 | 73 | 69 | 65 |
Requests for regrades should be made immediately by returning your exam on the day you get it back.
The Jacobs School of Engineering code of Academic Integrity is here. You should make yourself aware of what is and is not acceptable by reading this document. Academic integrity violations will be taken seriously and reported immediately. Ignorance of the rules will not excuse you from any violations.
Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD). If you have an AFA letter, please schedule an appointment with your instructor within the first three days of class to ensure that reasonable accommodations can be arranged. For more information, see here.
The textbook for this course is Rosen, Kenneth: Discrete Mathematics and its Applications, McGraw Hill. The texbook's companion website has extra practice problems and resources. Access the companion website here.
You may also wish to look at the following textbook as a supplementary resource: Jenkyns, Tom and Stephenson, Ben: Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, Springer. The full pdf of this book is available for free download from a UCSD internet connection at: http://link.springer.com/book/10.1007%2F978-1-4471-4069-6