(SS1 2021)

Welcome to CSE101. Algorithmic problems arise in every area of the real world and computer science. You will learn very 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 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 Program, 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:
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, many years we had for both cases
O(n2) runtime, now it is almost linear O(n log n).

Content:
Mergesort: Correctness and Time analysis, Multiplication of large integers (Karatsuba’s
algorithm)

**4 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:
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)

**5 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, 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 (Complete
Enumeration and MST Heuristic), Capacitated Vehicle Routing Planning (Savings Heuristic)

**6 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: 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

**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 their 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 and programmign assignments. 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:

*- Algorithm Design* (Kleinberg, Tardos), Addison Wesley

*- Introduction to Algorithms* (Cormen, Leiserson, Rivest, Stein), MIT Press