Are you over 18 and want to see adult content?
More Annotations
![A complete backup of salvadoracomic.com](https://www.archivebay.com/archive2/78702367-ad6a-4cbb-ace2-745a1d8fadc7.png)
A complete backup of salvadoracomic.com
Are you over 18 and want to see adult content?
![A complete backup of deutschlandfunk.de](https://www.archivebay.com/archive2/3528d099-56ad-4fdf-904a-eb0988c58cb6.png)
A complete backup of deutschlandfunk.de
Are you over 18 and want to see adult content?
![A complete backup of pocketgpsworld.com](https://www.archivebay.com/archive2/b03f1cab-4e48-4650-8aba-19afb444e6bb.png)
A complete backup of pocketgpsworld.com
Are you over 18 and want to see adult content?
![A complete backup of samuraitactical.com](https://www.archivebay.com/archive2/7b96ecb1-dde0-48e8-8230-77baa83aa98c.png)
A complete backup of samuraitactical.com
Are you over 18 and want to see adult content?
![A complete backup of ricardogarciamz.com](https://www.archivebay.com/archive2/9ab7a401-ab95-4257-8678-86960a337f83.png)
A complete backup of ricardogarciamz.com
Are you over 18 and want to see adult content?
![A complete backup of thegardenvadavada.com](https://www.archivebay.com/archive2/cda43edc-0af5-4e6d-8cf8-27418a4a7031.png)
A complete backup of thegardenvadavada.com
Are you over 18 and want to see adult content?
![A complete backup of fernandacaroline.com](https://www.archivebay.com/archive2/fd8888c5-62a9-4d7c-8b0a-067a501e69e3.png)
A complete backup of fernandacaroline.com
Are you over 18 and want to see adult content?
Favourite Annotations
![A complete backup of www.kaufmich.com](https://www.archivebay.com/archive5/images/613963e4-92b4-4a47-8df2-1e68a18c3394.png)
A complete backup of www.kaufmich.com
Are you over 18 and want to see adult content?
![A complete backup of www.lushstories.com](https://www.archivebay.com/archive5/images/46349d88-412d-4ce1-a2c9-0e69e76b3133.png)
A complete backup of www.lushstories.com
Are you over 18 and want to see adult content?
![A complete backup of www.model-kartei.de](https://www.archivebay.com/archive5/images/a20fcd60-52ba-41dc-b342-71b94e9f6363.png)
A complete backup of www.model-kartei.de
Are you over 18 and want to see adult content?
![A complete backup of dirtyhomeclips.com](https://www.archivebay.com/archive5/images/5204b634-cc9d-4e2c-aed7-a4dc81877b67.png)
A complete backup of dirtyhomeclips.com
Are you over 18 and want to see adult content?
Text
RSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upMEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:FAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.DP PART II | CS6505
PDF of Eric’s handwritten notes are here. More Dynamic Programming. Knapsack. Input: objects with integer weights and integer values , and a total capacity . Output: The set of objects where that maximizes . Version 1: can only include an item at most once. LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
LP STRONG DUALITY
Theorem (strong LP duality). Let (P) be an LP and (D) be its dual. Suppose that both systems are feasible. Then their optimal values are equal. Proof: We will focus on the standard form where (P) is specified as max s.t. and and its dual (D) is s.t. . Let be the optimal value of the dual. AUGUST | 2015 | CS6505 1 post published by svempala during August 2015. Spring 2016. MWF 9-10: Klaus 1456 . Instructors: Eric Vigoda and Santosh Vempala (email: vigoda,vempala gatech.edu)RSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upMEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:FAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.DP PART II | CS6505
PDF of Eric’s handwritten notes are here. More Dynamic Programming. Knapsack. Input: objects with integer weights and integer values , and a total capacity . Output: The set of objects where that maximizes . Version 1: can only include an item at most once. LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
LP STRONG DUALITY
Theorem (strong LP duality). Let (P) be an LP and (D) be its dual. Suppose that both systems are feasible. Then their optimal values are equal. Proof: We will focus on the standard form where (P) is specified as max s.t. and and its dual (D) is s.t. . Let be the optimal value of the dual. AUGUST | 2015 | CS6505 1 post published by svempala during August 2015. Spring 2016. MWF 9-10: Klaus 1456 . Instructors: Eric Vigoda and Santosh Vempala (email: vigoda,vempala gatech.edu)MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.CONNECTIVITY
PDF of Eric’s handwritten notes are here. DFS on Directed Graphs and Strongly Connected Components In this lecture we'll review the classic DFS (depth first search) algorithm, look at its application to directed graphs and then use it find strongly connected components of a general, directed graph. We begin by reviewing the basic DFSalgorithm
SCHEDULE: FALL 2018
Sept 19. Exam 1. Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft) Oct 1, 3 Linear equations Notes1 Notes 2 ( draft) Oct 10, 15 Maxflow and Mincut Notes. OctNP: GRAPH PROBLEMS
PDF of Eric’s handwritten notes are here. In this last lecture we took for granted that SAT is NP-Complete, and then we used this fact to show that 3-SAT is NP-Complete. Now we'll build on that to prove that a few graph problems, namely, Independent Set, Clique, and Vertex Cover, are NP-Complete. The first problemDP PART II | CS6505
PDF of Eric’s handwritten notes are here. More Dynamic Programming. Knapsack. Input: objects with integer weights and integer values , and a total capacity . Output: The set of objects where that maximizes . Version 1: can only include an item at most once. LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.RSA: PART II
RSA: Part II. PDF of Eric’s handwritten notes is here. RSA Protocol. We will look at the setting where Alice has some message that she wants to send to Bob. She encodes this message using the public key that Bob publishes, which will be a pair of numbers . Bob uses aBLOOM FILTERS
PDF of Eric’s handwritten notes are here. Today we’ll discuss hashing and see a widely-used scheme known as a Bloom filter. Before diving into hashing let’s look at a NOVEMBER | 2018 | CS6505 The Ellipsoid Algorithm is a first known to be polynomial time algorithm for linear programming, find. subject to. i.e., find a feasible solution, or in other words, given a convex set , written as , find a point in . We start with a big enough ball, which is guaranteed to contain . The sphere is defined , where is sufficientlylarge.
LP STRONG DUALITY
Theorem (strong LP duality). Let (P) be an LP and (D) be its dual. Suppose that both systems are feasible. Then their optimal values are equal. Proof: We will focus on the standard form where (P) is specified as max s.t. and and its dual (D) is s.t. . Let be the optimal value of the dual.HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:FAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses. LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.SCHEDULE: FALL 2018
Sept 19. Exam 1. Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft) Oct 1, 3 Linear equations Notes1 Notes 2 ( draft) Oct 10, 15 Maxflow and Mincut Notes. OctDP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
NOVEMBER | 2018 | CS6505 The Ellipsoid Algorithm is a first known to be polynomial time algorithm for linear programming, find. subject to. i.e., find a feasible solution, or in other words, given a convex set , written as , find a point in . We start with a big enough ball, which is guaranteed to contain . The sphere is defined , where is sufficientlylarge.
HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:FAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses. LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.SCHEDULE: FALL 2018
Sept 19. Exam 1. Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft) Oct 1, 3 Linear equations Notes1 Notes 2 ( draft) Oct 10, 15 Maxflow and Mincut Notes. OctDP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
NOVEMBER | 2018 | CS6505 The Ellipsoid Algorithm is a first known to be polynomial time algorithm for linear programming, find. subject to. i.e., find a feasible solution, or in other words, given a convex set , written as , find a point in . We start with a big enough ball, which is guaranteed to contain . The sphere is defined , where is sufficientlylarge.
CONNECTIVITY
PDF of Eric’s handwritten notes are here. DFS on Directed Graphs and Strongly Connected Components In this lecture we'll review the classic DFS (depth first search) algorithm, look at its application to directed graphs and then use it find strongly connected components of a general, directed graph. We begin by reviewing the basic DFSalgorithm
FAST MULTIPLICATION
PDF of Eric’s handwritten notes are here. Multiplication: Given 2 -bit numbers and (where is large). Compute .. Naive Algorithm: A naive algorithm for multiplying two numbers and creates an array of intermediate sums, each representing the product of by a single digit of .This algorithm takes time.. An Idea of Gauss: Suppose we want to multiply two complex numbers and .2-SAT | CS6505
Input: given formula in CNF with variables and clauses. Output: assignment satisfying if one exists, and NO if no satisfying assignment exists. k-SAT: same as SAT but the input has clauses with literals in each. We’ll see that SAT is NP-complete and k-SAT is NP-complete for each . Claim: 2-SAT NP-COMPLETENESS: INTRO Now we can use reductions to show the second part of the proof of NP-completeness for SAT. That is, for any problem A in NP, we need to find a reduction from A to SAT. Suppose we know SAT is NP-Complete somehow, which gives us for every problem A in NP, we have A SAT. And now we want to show Colorings is NP-Complete.DP PART II | CS6505
PDF of Eric’s handwritten notes are here. More Dynamic Programming. Knapsack. Input: objects with integer weights and integer values , and a total capacity . Output: The set of objects where that maximizes . Version 1: can only include an item at most once.LP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objective LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
CS 6505 – SPRING ’17 SCHEDULE For the Fall 2017 CS 8803 GA schedule go here. Below is the Spring 2017 CS 6505 schedule. Dynamic Programming (see Chapter 6): 1/10 and 1/12 LIS, LCS - notes Knapsack, Chain Multiply - notes Shortest paths (Floyd-Warshall all-pairs) - notes RSA Cryptosystem (see Chapter 1): 1/17 and 1/19 Number theory, RSA protocol - notes Primality testing - notes Divide & Conquer (see [DPVRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upFAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem: LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
SCHEDULE: FALL 2018
Sept 19. Exam 1. Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft) Oct 1, 3 Linear equations Notes1 Notes 2 ( draft) Oct 10, 15 Maxflow and Mincut Notes. OctLP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objectiveRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upFAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem: LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
SCHEDULE: FALL 2018
Sept 19. Exam 1. Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft) Oct 1, 3 Linear equations Notes1 Notes 2 ( draft) Oct 10, 15 Maxflow and Mincut Notes. OctLP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objectiveCONNECTIVITY
PDF of Eric’s handwritten notes are here. DFS on Directed Graphs and Strongly Connected Components In this lecture we'll review the classic DFS (depth first search) algorithm, look at its application to directed graphs and then use it find strongly connected components of a general, directed graph. We begin by reviewing the basic DFSalgorithm
FAST MULTIPLICATION
PDF of Eric’s handwritten notes are here. Multiplication: Given 2 -bit numbers and (where is large). Compute .. Naive Algorithm: A naive algorithm for multiplying two numbers and creates an array of intermediate sums, each representing the product of by a single digit of .This algorithm takes time.. An Idea of Gauss: Suppose we want to multiply two complex numbers and . LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.LP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objective NP-COMPLETENESS: INTRO Now we can use reductions to show the second part of the proof of NP-completeness for SAT. That is, for any problem A in NP, we need to find a reduction from A to SAT. Suppose we know SAT is NP-Complete somehow, which gives us for every problem A in NP, we have A SAT. And now we want to show Colorings is NP-Complete. A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
2-SAT | CS6505
Input: given formula in CNF with variables and clauses. Output: assignment satisfying if one exists, and NO if no satisfying assignment exists. k-SAT: same as SAT but the input has clauses with literals in each. We’ll see that SAT is NP-complete and k-SAT is NP-complete for each . Claim: 2-SATHW1: COMPUTABILITY
HW1: Computability. A NARCISSIST is a Turing Machine (TM) that on any input writes “IT IS ABOUT ME” at the beginning of the tape. Show that there is not Turing Machine that can decide if a given Turing Machine is a NARCISSIST, i.e., the language of TMs that are NARCISSISTS is undecidable.BLOOM FILTERS
PDF of Eric’s handwritten notes are here. Today we’ll discuss hashing and see a widely-used scheme known as a Bloom filter. Before diving into hashing let’s look at a CS 6505 – SPRING ’17 SCHEDULE For the Fall 2017 CS 8803 GA schedule go here. Below is the Spring 2017 CS 6505 schedule. Dynamic Programming (see Chapter 6): 1/10 and 1/12 LIS, LCS - notes Knapsack, Chain Multiply - notes Shortest paths (Floyd-Warshall all-pairs) - notes RSA Cryptosystem (see Chapter 1): 1/17 and 1/19 Number theory, RSA protocol - notes Primality testing - notes Divide & Conquer (see [DPVRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upFAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem: LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
SCHEDULE: FALL 2018
Sept 19. Exam 1. Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft) Oct 1, 3 Linear equations Notes1 Notes 2 ( draft) Oct 10, 15 Maxflow and Mincut Notes. OctLP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objectiveRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upFAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.DIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem: LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
SCHEDULE: FALL 2018
Sept 19. Exam 1. Sept 24, 26. Dynamic Programming Notes1 Notes2 (draft) Oct 1, 3 Linear equations Notes1 Notes 2 ( draft) Oct 10, 15 Maxflow and Mincut Notes. OctLP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objectiveCONNECTIVITY
PDF of Eric’s handwritten notes are here. DFS on Directed Graphs and Strongly Connected Components In this lecture we'll review the classic DFS (depth first search) algorithm, look at its application to directed graphs and then use it find strongly connected components of a general, directed graph. We begin by reviewing the basic DFSalgorithm
FAST MULTIPLICATION
PDF of Eric’s handwritten notes are here. Multiplication: Given 2 -bit numbers and (where is large). Compute .. Naive Algorithm: A naive algorithm for multiplying two numbers and creates an array of intermediate sums, each representing the product of by a single digit of .This algorithm takes time.. An Idea of Gauss: Suppose we want to multiply two complex numbers and . LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.LP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objective NP-COMPLETENESS: INTRO Now we can use reductions to show the second part of the proof of NP-completeness for SAT. That is, for any problem A in NP, we need to find a reduction from A to SAT. Suppose we know SAT is NP-Complete somehow, which gives us for every problem A in NP, we have A SAT. And now we want to show Colorings is NP-Complete. A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
2-SAT | CS6505
Input: given formula in CNF with variables and clauses. Output: assignment satisfying if one exists, and NO if no satisfying assignment exists. k-SAT: same as SAT but the input has clauses with literals in each. We’ll see that SAT is NP-complete and k-SAT is NP-complete for each . Claim: 2-SATHW1: COMPUTABILITY
HW1: Computability. A NARCISSIST is a Turing Machine (TM) that on any input writes “IT IS ABOUT ME” at the beginning of the tape. Show that there is not Turing Machine that can decide if a given Turing Machine is a NARCISSIST, i.e., the language of TMs that are NARCISSISTS is undecidable.BLOOM FILTERS
PDF of Eric’s handwritten notes are here. Today we’ll discuss hashing and see a widely-used scheme known as a Bloom filter. Before diving into hashing let’s look at a CS 6505 – SPRING ’17 SCHEDULE For the Fall 2017 CS 8803 GA schedule go here. Below is the Spring 2017 CS 6505 schedule. Dynamic Programming (see Chapter 6): 1/10 and 1/12 LIS, LCS - notes Knapsack, Chain Multiply - notes Shortest paths (Floyd-Warshall all-pairs) - notes RSA Cryptosystem (see Chapter 1): 1/17 and 1/19 Number theory, RSA protocol - notes Primality testing - notes Divide & Conquer (see [DPVRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upDIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet. A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
HW11: NP-COMPLETENESS I P1. Consider the clique problem restricted to graphs in which every vertex has degree at most 3. Call this problem CLIQUE-3. (a) Prove that CLIQUE-3 is in NP. (b) What is wrong with the following proof of NP-completeness for CLIQUE-3? We know that the clique problem in general graphs is NP-complete, so it is enough to present LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
RSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upDIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet. A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
HW11: NP-COMPLETENESS I P1. Consider the clique problem restricted to graphs in which every vertex has degree at most 3. Call this problem CLIQUE-3. (a) Prove that CLIQUE-3 is in NP. (b) What is wrong with the following proof of NP-completeness for CLIQUE-3? We know that the clique problem in general graphs is NP-complete, so it is enough to present LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
FAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
LP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objectiveNP: GRAPH PROBLEMS
PDF of Eric’s handwritten notes are here. In this last lecture we took for granted that SAT is NP-Complete, and then we used this fact to show that 3-SAT is NP-Complete. Now we'll build on that to prove that a few graph problems, namely, Independent Set, Clique, and Vertex Cover, are NP-Complete. The first problemDP PART 1 | CS6505
DP Part 1. PDF of Eric’s handwritten notes are here. Dynamic Programming. Here we study dynamic programming. We’ll discuss a few examples so you see the methodology for designing a dynamic programming algorithm. Problem 1: Longest Increasing Subsequence (LIS) Input: numbers . Output: The length of the LIS. Example: If the inputis , then
2-SAT | CS6505
PDF of Eric’s handwritten notes are here. Boolean formula. Variables: taking values True or False Literals: . Operators: OR, AND. Clause is an OR of several literals. Example: . Boolean formula is in conjunctive normal form (CNF) means that it is the AND of suchclauses. Example: .
A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.HW1: COMPUTABILITY
HW1: Computability. A NARCISSIST is a Turing Machine (TM) that on any input writes “IT IS ABOUT ME” at the beginning of the tape. Show that there is not Turing Machine that can decide if a given Turing Machine is a NARCISSIST, i.e., the language of TMs that are NARCISSISTS is undecidable. LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
BLOOM FILTERS
PDF of Eric’s handwritten notes are here. Today we’ll discuss hashing and see a widely-used scheme known as a Bloom filter. Before diving into hashing let’s look at aRSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upDIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet. A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
HW11: NP-COMPLETENESS I P1. Consider the clique problem restricted to graphs in which every vertex has degree at most 3. Call this problem CLIQUE-3. (a) Prove that CLIQUE-3 is in NP. (b) What is wrong with the following proof of NP-completeness for CLIQUE-3? We know that the clique problem in general graphs is NP-complete, so it is enough to present LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
RSA: PART I
RSA: Part I. PDF of Eric’s handwritten notes are here. Modular Arithmetic. Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example: For , mod 2 = least significant bit of =. 1 if is odd. 0 if is even. The general definition is the following:HOMEWORK | CS6505
Homework policy: You may work with other people on the homework, but you must each write up your solutions separately (without any notes from your group discussion). If you work with other people, indicate clearly who you worked with on your solution. Avoid looking up solutions online or in references. Each solution must take upDIVIDE AND CONQUER
Recall that in a divide and conquer algorithm, the strategy is. Breaking the problem into smaller subproblems of the same type, Solving these subproblems recursively, Combining these solutions. Here, we break each input number into 2 halves. Let and be the first digits and last digits of respectively.MAX-SAT APPROX ALG.
First we give a very simple algorithm for Max-SAT. The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. I then outputs the resulting assignment. Since this is a randomized algorithm we look at its “expected”. Let be the number of satisfied clauses.MEDIAN | CS6505
PDF of Eric’s handwritten notes are here. Median. Given an unsorted list of size , find the median of .For concreteness we’ll define the median as the smallest element of the list.. k-Selection. Just as in inductive proofs where one often needs to strengthen the inductive hypothesis and thus prove a stronger statement, here we will give an algorithm for a more general problem:DP PART III
DP Part III. PDF of Eric’s handwritten notes are here. Shortest path algorithms using DP. Input: Directed with edge weights . Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive. What if negativeweight edges?
LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet. A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
HW11: NP-COMPLETENESS I P1. Consider the clique problem restricted to graphs in which every vertex has degree at most 3. Call this problem CLIQUE-3. (a) Prove that CLIQUE-3 is in NP. (b) What is wrong with the following proof of NP-completeness for CLIQUE-3? We know that the clique problem in general graphs is NP-complete, so it is enough to present LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
FAST MULTIPLICATION
Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence. which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one. Fast Multiplication: This is where Gauss’s idea comesinto the picture.
LP DUALITY | CS6505
Weak Duality: Our construction of the dual LP was designed so that it gave an upper bound on the value of the primal LP’s objective function. More precisely, any feasible point for the dual LP gives an upper bound on the value of the primal LP’s objective function. Thus, for any feasible point for the primal LP its value of the objective function is at most that of the dual’s objectiveNP: GRAPH PROBLEMS
PDF of Eric’s handwritten notes are here. In this last lecture we took for granted that SAT is NP-Complete, and then we used this fact to show that 3-SAT is NP-Complete. Now we'll build on that to prove that a few graph problems, namely, Independent Set, Clique, and Vertex Cover, are NP-Complete. The first problemDP PART 1 | CS6505
DP Part 1. PDF of Eric’s handwritten notes are here. Dynamic Programming. Here we study dynamic programming. We’ll discuss a few examples so you see the methodology for designing a dynamic programming algorithm. Problem 1: Longest Increasing Subsequence (LIS) Input: numbers . Output: The length of the LIS. Example: If the inputis , then
2-SAT | CS6505
PDF of Eric’s handwritten notes are here. Boolean formula. Variables: taking values True or False Literals: . Operators: OR, AND. Clause is an OR of several literals. Example: . Boolean formula is in conjunctive normal form (CNF) means that it is the AND of suchclauses. Example: .
A FEW MORE REDUCTIONS A few more reductions. Theorem: SAT is polytime reducible to 3SAT. Proof (idea). Using the following idea clauses of length can be broken into smaller ones: After making all clauses of length at most we can easily increase smaller clauses lengths to make all equal to : Definition: k-popsicle is a graph including a clique of size k whereone of
LECTURE 1: COMPUTABILITY Lecture 1: Computability. What is computation? Computation is a “well-defined” sequence of state changes. Computation is the evaluation of functions. For example, the function. is computable but the function. is not computable. Language. Let be an alphabet.HW1: COMPUTABILITY
HW1: Computability. A NARCISSIST is a Turing Machine (TM) that on any input writes “IT IS ABOUT ME” at the beginning of the tape. Show that there is not Turing Machine that can decide if a given Turing Machine is a NARCISSIST, i.e., the language of TMs that are NARCISSISTS is undecidable. LECTURE 2: INCOMPLETENESS Lecture 2: Incompleteness. Review of Last Class. Recall that “computable” means computable by a Turing machine (TM). We saw that the set of strings for a given alphabet is countable, while the set of languages is uncountable. Note that as a consequence of the set of languages being uncountable, not all languages can be decidable,since
BLOOM FILTERS
PDF of Eric’s handwritten notes are here. Today we’ll discuss hashing and see a widely-used scheme known as a Bloom filter. Before diving into hashing let’s look at aSkip to content
* __View menu
* ____View sidebar
CS6505
* Home
* Schedule & Notes
* Homework
Search for:
ARCHIVES
* November 2018
* October 2018
* September 2018
* August 2015
META
* Register
* Log in
CS 6505: FALL 2018
LECTURES: MW 3-4:15 in Howey-L3. INSTRUCTOR: Santosh Vempala , Klaus2222
OFFICE HOURS: Wed 2-3pm, Fri 2-3pm TA OFFICE HOURS (held in open area in front of Klaus 2138) * Samira Samadi: Tue-Wed, 4:30-6:30pm * Kyle Zimmerman: Tue: 1-4pm, Fri: 1-2pm * Majid Farhadi: Wed: 8am-12pm * Ricky Pudota: Tue, Fri: 10am-12pm * James Choi: Mon 12-2pm, Thu 12:15-1:15, 3-4pm.GRADING:
* HW: 25% (we will drop the two lowest HW scores).* Exams: 75%
Books:
* _Algorithms _by S. Dasgupta, C. Papadimitriou, and U. Vazirani * _Introduction to the Theory of Computation_, M. Sipser (3rdEdition)
* _Foundations of Data Science_, A. Blum, J. Hopcroft and R. Kannan Blog at WordPress.com. Do Not Sell My Personal Information Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: CookiePolicy
* Follow
*
* cs6505
* Customize
* Follow
* Sign up
* Log in
* Copy shortlink
* Report this content * Manage subscriptions* Collapse this bar
Details
Copyright © 2024 ArchiveBay.com. All rights reserved. Terms of Use | Privacy Policy | DMCA | 2021 | Feedback | Advertising | RSS 2.0