CSE101

Design and Analysis of Algorithms
(SS1 2021)


Welcome Message


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


Structure of CSE 101


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


Class Meeting


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.


Canvas and Piazza


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.


Grading


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.


Academic Integrity


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.


Accommodations


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.


Textbook


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

Top