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
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
Time Complexity and Correctness of recursive algorithms: Exponentiation, Merging sorted arrays, Divide-And-Conquer: Mergesort, Multiplication of large integers (Karatsuba’s algorithm)
3 Counting
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
Probability, Probability and counting, Conditional probabilities, Bayes' Theorem, Expected value and linearity of expectation, Birthday Paradox, Randomized algorithms and Hashing
5 Graphs and 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), Travelling-Salesperson-Problem (Minimum Spanning Tree Algorithm and Christrofides' Algorithm)
Lectures: We will upload the lecture slides on Canvas.
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. Students who are still not sure about the solutions after discussions are more than welcome to join our office hours.
We will upload the lecture slides, solutions to the homework questions, 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.
To make the course less stressful and an excellent experience for all students,
we offer several bonus points opportunities:
1. You can get bonus points for an active participation during the lectures.
2. You can get bonus points for an active participation during the homework discussions.
3. You can get bonus points for an active participation on Piazza (especially for responses to
questions from other students).
We will have two exams. Both will be in person (and not online). After your weighted average (Midterm, Final, Bonus points) 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 |
The only allowed appliance to bring to the exams is a pen. You may not use calculators but can bring one page with hand-written notes. Please be sure to write your name on the back page. The notes must be submitted together with the exams. 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.
The following will all considered to be breaches of academic integrity:
1. Collaboration or copying on exams of any kind.
2. Use of aids on exams outside of explicitly allowed materials (this may vary by exam).
The textbook for this course is Dasgupta, Papadimitriou, Vazirani: Algorithms, McGraw Hill
You may also wish to look at the following literature as a supplementary resource:
- Algorithm Design (Kleinberg, Tardos), Addison Wesley
- Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein), MIT Press
The IDEA Engineering Student Center, located just off the lobby of Jacobs Hall, is a hub for student engagement, academic enrichment, personal/professional development, leadership, community involvement, and a respectful learning environment for all. The Center offers a variety of programs, listed in the IDEA Center Facebook page at http://www.facebook.com/ucsdidea/ and the Center web site at http://idea.ucsd.edu/. The IDEA Center programs support both undergraduate students and graduate students.
We are committed to fostering a learning environment for this course that supports a diversity of thoughts, perspectives and experiences, and respects your identities (including race, ethnicity, heritage, gender, sex, class, sexuality, religion, ability, age, educational background, etc.). Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive. Our instructional staff will make a concerted effort to be welcoming and inclusive to the wide diversity of students in this course. If there is a way we can make you feel more included please let one of the course staff know, either in person, via email/discussion board, or even in a note under the door. Our learning about diverse perspectives and identities is an ongoing process, and we welcome your perspectives and input. We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community https://ucsd.edu/about/principles.html. Please understand that others’ backgrounds, perspectives and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable. If you experience any sort of harassment or discrimination, please contact the instructor as soon as possible. If you prefer to speak with someone outside of the course, please contact the Office of Prevention of Harassment and Discrimination: https://ophd.ucsd.edu/.
We aim to create an environment in which all students can succeed in this course. If you have a disability, please contact the Office for Students with Disability (OSD), which is located in University Center 202 behind Center Hall, to discuss appropriate accommodations right away. We will work to provide you with the accommodations you need, but you must first provide a current Authorization for Accommodation (AFA) letter issued by the OSD. You are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance so that accommodations may be arranged.
If you are experiencing any basic needs insecurities (food, housing, financial resources), there are resources available on campus to help, including The Hub and the Triton Food Pantry. Please visit http://thehub.ucsd.edu for more information.
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