Welcome to CSE101. Algorithmic problems arise in every area of the real world and computer science. This course exposes you to a variety of algorithms for problems from various domains. You will learn how the speed of algorithms greatly impact their utility. You will learn elementary mathematical techniques to analyze algorithms for correctness and time complexity. You will learn how to prove the optimality of algorithms and to analyze the worst-case behavior of approximation algorithms, i.e. to provide guarantees on the distance of the returned solution to the optimal one. You will become familiar with a lot of interesting algorithms for many classical and also new problems. You will learn the most useful methods and concepts for designing algorithms, and know how to apply them to new problems:
- 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 algorithms
- Performing a time analysis for algorithms
- Analyzing the worst-case behavior of approximation algorithms
1. Algorithms: Algorithmic problems, Continuous vs. discrete optimization, Requirements analysis, Problem solving,
Analyzing iterative algorithms: Correctness and Time analysis
2. Divide-And-Conquer: Recurrences, Analyzing recursive and D&C-algorithms: Correctness and Time analysis
3. Graph Algorithms I: Basics, Maximum number of edges, Representing graphs, Euler and Hamilton, BFS, DFS,
Minimum Spanning Trees, Topological Sorting, Single-source Shortest Paths: Bellman/Ford,
Dijkstra (non-negative networks, PQ: Array, Binary Heap), Bellman (acyclic networks)
4. Linear Programming: Introduction, 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
5. Assignment Problem and Knapsack Problem: Greedy Heuristics, Complete Enumeration, Branch-And-Bound, Dynamic Programming
6. Algorithmic complexity and NP-hard problems: Combinatorial explosion, NP-hard problems, NP-Completeness,
Optimization vs. Decision problems, P, NP and reducibility, Approximation algorithms, Heuristics, Some Reductions:
Subset Sum, Partition, 3-Partition, (Numerical)3-Dimensional Matching, Sequencing within intervals,
Parallel processor scheduling (with m or m=2 processors), Flow-Shop scheduling (with m=3 processors),
Knapsack, Bin Packing, Zero-One Equations (ZOE)
7. Bin Packing and Scheduling:
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), Scheduling with time restrictions
9. Graph Algorithms II: All-pairs Shortest Paths (Floyd/Warshall),
Travelling Salesperson Problem (MST Heuristic),
Capacitated Vehicle Routing Planning (Savings Heuristic)
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 5:00 pm - 6: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 |
| Jay Bonthius | Teaching Assistant | jbonthiu (at) ucsd.edu |
| Nicholas Chung | Tutor | nkchung (at) ucsd.edu |
We will have two exams. After your weighted average (Midterm, Final, Programming Assignments) 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 Dasgupta, Papadimitriou, Vazirani: Algorithms, McGraw Hill
You may also wish to look at the following literature as a supplementary resource:
- Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein), MIT Press
- Algorithm Design (Kleinberg, Tardos), Addison Wesley