Algorithm算法代写代考

Linear Programming Solving LP 2021-03-10 CSC373 Winter 2021 – Sam Toueg 1 Recall: Farmer Example • Canplanttwokindsofcorncrop:!!(forhumanconsumption)and!”(foranimalfeed) Planting Requirements per hectare Available Resources Profit per hectare !! 3$ !# 2$ Labour (hours) ≤ 40 Seed (kg) ≤ 100 Pesticide (bags) ≤ 10 !! !” Labour (hours) Pesticide (bags) 2 1 1 1 Seed (kg) 3 […]

UNIVERSITY OF TORONTO Faculty of Arts and Science AUGUST 2018 EXAMINA TIONS CSC373H1Y Instructor(s): Koushik Pal Duration – 3 hours Examination Aids: One 8.5″ x 11″ sheet of paper, handwritten on both sides. Student Number: Last (Family) Name(s): First (Given) Name(s): Do not turn this page until you have received the signal to start. (In

Approximation Algorithms 2021-04-05 CSC373 Winter 2021 – Sam Toueg 1 We saw approximation algorithms for: • Δ-TSP [using MST] • Minimum Vertex cover [greedy algorithm] • Minimum Weighted Vertex Cover [ILP rounding] • Makespan (on-line and off-line) [greedy algorithm] Approximation algorithms based on Local Search • Max-Cut • Exact Max-“-SAT (today) 2021-04-05 CSC373 Winter 2021

Local Search Paradigm 2021-03-31 CSC373 Winter 2021 – Sam Toueg 1 Local Search • A heuristic paradigm for solving complex problems • Idea: Ø Start with some solution 𝑆 Ø While there is a better solution 𝑆′ in the local neighborhood of 𝑆 switch to 𝑆′ • Need to define: Ø what is “better”, and

Dynamic Programming Chain Matrix Multiplication 2021-02-03 CSC373 Winter 2021 – Sam Toueg 1 Multiplication of 2 matrices • Multiplying a !×# matrix $ by a #×% matrix & yields a !×% matrix ‘ & “## !% × =% #$% (!” = * +!# , -#” #%!#%# ⋯ #%$ & %%” ( ) !!” !#” ⋮

Approximation Algorithms 2021-03-29 CSC373 Winter 2021 – Sam Toueg 1 Min Vertex Cover and Max Matching 2021-03-29 CSC373 Winter 2021 – Sam Toueg 2 Vertex Cover • 𝐺 = (𝑉, 𝐸): undirected graph • vertex cover (VC): a subset 𝑉′ of the nodes of 𝐺 that “touches’’ every edge of 𝐺, i.e., every edge has

Approximation Algorithms 2021-03-31 CSC373 Winter 2021 – Sam Toueg 1 So far, we have seen approximation algorithms for: • Δ-TSP (Euclidian Traveling Salesman Problem) ØUsing MST • Minimum Vertex cover ØUsing Greedy algorithm and Matching • Minimum Weighted Vertex Cover ØUsing ILP: Relaxation and Rounding 2021-03-31 CSC373 Winter 2021 – Sam Toueg 2 Makespan Minimization

Last week recap • Dynamic Programming: Ø Edit Distance Ø Chain Matrix Multiplication Ø 0-1 Knapsack Problem 2021-02-08 CSC373 Winter 2021 – Sam Toueg 1 Dynamic Programing Bellman-Ford’s Single-Source Shortest Paths Algorithm 2021-02-08 CSC373 Winter 2021 – Sam Toueg 2 Single-Source Shortest Path • Problem ØInput: • Each edge 𝑢, 𝑣 has a weight (“length’’)

Approximation Algorithms 2021-03-24 CSC373 Winter 2021 – Sam Toueg 1 NP-Completeness • We saw that many problems are NP-complete Ø Unlikely to have polynomial time algorithms to solve them Ø What can we do? • One idea: Ø Instead of solving them exactly, solve them approximately 2021-03-24 CSC373 Winter 2021 – Sam Toueg 2 Approximation

Complexity NP-Complete Problems 2021-03-24 CSC373 Winter 2021 – Sam Toueg 79 Some NP-Complete Problems and Reduction Techniques 2021-03-24 CSC373 Winter 2021 – Sam Toueg 80 NP-Complete problems and Reductions so far… Ø SAT Ø Clique Ø Independent Set Ø Vertex Cover Ø Set Cover Ø IP Feasibility Ø Coloring Ø Exact Set Cover [Cook-Levin Theorem]