(SS1 2021)

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. Understanding these topics and being able to work out related problems will be essential to your work as a computer scientist. You will learn tools to formulate and solve problems, and develop and analyze algorithms. You will learn how to justify (prove) your conclusions, so that others can follow your reasoning and be convinced of your results. In addition, you will learn examples for problem‐solving techniques that can be used in a much broader context.

1 Iterative Algorithms (Week 1)

Big O and its relatives, Time Complexity and Correctness of iterative algorithms: Minsort, Bubblesort, Insertionsort, Linear Search, Binary Search, Summing Triple, Intersection

2 Recursive Algorithms (Week 2)

Time Complexity and Correctness of recursive algorithms: Exponentiation, Merging sorted arrays, Divide-And-Conquer: Mergesort, Multiplication of large integers (Karatsuba’s algorithm)

3 Counting (Week 3)

Product rule and Sum rule, Permutations and Combinations, Counting Binary Strings, 4-digit- PINs, 4-letter-strings, Counting Binomial coefficients and Identities, Counting Paths, Techniques: Counting using Inclusion and Exclusion, Counting using the Complement

4 Probability (Week 4)

Probability, Probability and counting, Conditional probabilities, Expected value and linearity of expectation, Birthday Paradox, Randomized algorithms and Hashing

5 Graph Algorithms

Basic defintions and properties of graphs, Euler and Hamilton, BFS, DFS, Minimum Spanning Trees (Prim's algorithm), Topolgical Sorting (Kahn's algorithm), 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.
We will meet online on Zoom during the regular lecture hours.

**Discussions:**
The homework will not be graded, however, we highly recommend
you to practice using these questions
for an optimal preparations of the exams.
Homework questions will be similar to the exam questions.
Discussions will be online on Zoom.
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.

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