Welcome to CSE101. Algorithmic problems arise in every area of the real world and computer science. You will learn useful methods and concepts for designing algorithms, and know how to apply them to new problems. You will become familiar with a lot of interesting algorithms for many classical and also new problems. You will learn techniques to analyze algorithms for correctness, time complexity, optimality and worst‐case behavior. You will be well prepared for starting a career as a researcher and for job interviews at tech companies after this class.
- Complete Enumeration
- Greedy-Algorithms
- Branch-And-Bound
- Dynamic Programming
- Divide-And-Conquer
- Approximation Algorithms
- Heuristics
- NP-Completeness
- Linear Programming
- Graph algorithms
- Proving the correctness of greedy algorithms
- Performing a time analysis for algorithms
- Analyzing the worst-case behavior of approximation algorithms
1 Algorithms and Optimization Problems. Time analysis and Correctness proofs of algorithms are important, because you want to see how fast your algorithm is and you want to make meaningful comments on your code so that you and other people can understand what is going on there. You will see how to attack and solve two optimization problems (a minimization and a maximization problem) in a systematic way. How can you do better than performing a brute-force "Complete Enumeration" of all possible solutions? You can be clever and use "Branch-And- Bound" to limit the number of possible solutions that you have to explore. Or you can use “Dynamic Programming” to get almost polynomial time algorithms (pseudo-polynomial), even for NP-hard problems.
Content:
Algorithmic problems, Continuous vs. discrete optimization, Assignment (min) and Knapsack
(max) Prolems: Greedy Heuristics, Complete Enumeration, Dynamic Programming, Branch-And-Bound.
2 Bin Packing and Scheduling. Packing problems and scheduling problems (production planning) occur on the operational level in everyday applications in the industry. You will see how to prove the optimality of Greedy algorithms and how to perform a worst-case analysis of approximation algorithms.
Content:
Bin Packing:
Complete Enumeration, Approximation algorithms, Worst-case analysis:
First Fit, First Fit Decreasing, Next Fit,
Scheduling:
Basics, Parallel processor scheduling: McNaughton,
Approximation algorithms, Worst-case analysis: Ron Graham's results (List Scheduling and LPT),
Single-processor scheduling: maximum lateness (Earliest-Due-Date), number of delayed jobs
(Moore), sum of delays (Complete Enumeration and Branch-and-Bound), Dynamic Programming,
Proving the Optimality of Greedy algorithms
3 Divide-and-Conquer. A very common algorithm design technique that gives often drastic improvements in terms of the running time. One example is Mergesort, another one is Karatsuba's algorithm for large integer multiplication and newer algorithms that are based on his idea. For many years we had for both cases O(n^2) runtime, now it is almost linear O(n log n).
Content:
Mergesort: Correctness and Time analysis, Multiplication of large integers (Karatsuba’s
algorithm), Medians, Counting inversions, Counting occurences, Largest subrange, Closest pair
of points
4 Graph Algorithms. Just think about Single-Source shortest paths or Minimum Spanning Trees, there are so many real-world applications where you need these algorithms to solve these problems. You will see how additional information about the structure of a graph greatly influences the running time of the algorithms. You will see an algorithm to solve the All-Pairs shortest paths problem based on Dynamic Programming and you will see the Savings heuristic for the Capacitated Vehicle Routing Planning that plays an important role in operational tour planning every day.
Content:
Euler and Hamilton, BFS, DFS, Minimum Spanning Trees (Prim#s algorithm), Topological Sort,
Single-source Shortest Paths: Bellman/Ford, Dijkstra (non-negative networks, PQ: Array, Binary Heap),
Bellman (acyclic networks), All-pairs Shortest Paths (Floyd/Warshall),
Travelling Salesperson Problem (Minimum-Spanning-Tree algorithm, Christofides' algorithm),
Capacitated Vehicle Routing Planning (Savings Heuristic)
5 Linear Programming. Arguably that mathematical tool with the widest spread and applications in industry. So many optimization problems are modeled and solved with linear programs. You get to know the Simplex algorithm to solve this problem and you learn about shadow prices and how to interpret the final Simplex tableau in extending the constraints, maximum gain in profit and Outsourcing.
Content: Linear Programs, Graphical Solution, Simplex algorithm, Shadow prices, Case Study: Interpretation of final Simplex tableaus: Extension of constraints, Lower and upper bounds, Maximum gain in profit, Outsourcing
6 Algorithmic complexity and NP-hard problems. Why are some problems inherently hard to solve? How is it possible to prove that a problem belongs to this class? You will see some concrete reductions from one NP-complete problem to another one.
Content:
Optimization vs. Decision problems, NP-hard problems, NP-complete in the ordinary and in the
strong sense, P, NP and reducibility, Subset Sum, Zero Subset Sum, Partition, 3-Partition,
Sequencing within intervals, Minimum tardiness sequencing, Parallel processor scheduling,Flow-
Shop Scheduling, Bin Packing, Knapsack, Zero-One Equations, 3-Dimensional Mathching, Vertex
Cover, Clique
Class Meeting
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. 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 their 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 thoughtful answers to
questions from other students).
We will have two exams (both will be in person and not online) and five programming assignments. After your weighted average (Midterm, Final, Programming Assignments, 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.
Homework: Students are encouraged to collaborate on homework assignments. You should feel free to discuss the problems and talk about how to come up with solutions with each other.
Programming Assignments (PA): You are expected to write up your solution and code independently of any collaborators, and you should not share your solutions to the programming assignments with other students before the deadline. If you do collaborate with other students on the assigments, you should make sure to list any collaborators that you had on any given problem. You should not attempt to search for PA solutions online or in sources outside of the course text. You may use such sources as a study guide, but if you accidentally stumble upon a PA solution in such an outside source you should cite it in your PA solution. If your solution proves to be too similar to the cited one, you may lose credit on the problem, however failure to cite the other solution will be treated as academic dishonesty.
The following will all considered to be breaches of academic integrity:
1. Collaboration on PA's beyond the scope outlined in the section above (including
sharing of PA solutions with other students before the PA deadline).
2. Failure to cite collaborators on PA's or outside sources used to findi PA
solutions.
3. Collaboration or copying on exams of any kind.
4. 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.