W&L Computer Science Wiki - courses:cs211:winter2018:journals:nasona

chapter1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-16T00:06:08+00:00

Chapter 1 1.1: Stable Matching Summary of the Section * We start off with the question of “is there a way to make have a college admission process or a job application process self-enforcing?” The goal was to assign every applicant A to every employer E such that E prefers every accepted applicant to A or A prefers her current employment situation over working for E. From there, we learn how to turn that very broad issue into a clearer problem. We changed from a problem in which there was a…

chapter2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-29T16:20:19+00:00

Chapter 2 2.1: Computational Tractability Summary of the Section * The two main components of computational efficiency are efficiency in running time and the amount of space (memory) used by an algorithm. A good way to gauge the efficiency of an algorithm is to analyze its worst case runtime. Additionally, in comparison to a brute search algorithm, an algorithm should be more efficient and have more of an intellectual weight or flavor to the structure of the algorithm. The text then settles…

chapter3

Anonymous (anonymous@undisclosed.example.com) — 2018-02-06T15:19:34+00:00

3.1 Basic Definitions and Applications Summary Undirected graphs indicate symmetric relationships while directed graphs depict asymmetric relationships. An undirected graph is connected if, if for every pair of node u and v, there is a path from u to v. Graphs can be used to depict a number of things such as transportation networks, connection networks, dependency networks, information networks, and social networks. A directed graph is strongly connected if, for every two nodes u and v, there …

chapter4

Anonymous (anonymous@undisclosed.example.com) — 2018-03-11T22:01:31+00:00

The Front Matter Summary This section is an introduction to Greedy Algorithms. Greedy algorithms build a solution by making step-by-step, local decisions to optimize underlying criterion. There are two types of proofs: Greedy Stays Ahead and Exchange Argument. Greedy Stays Ahead measures the progress of the algorithm and proves that it does better than or equal to any other algorithm, especially a simple brute search. The exchange argument is when you consider an optimal solution and gradually…

chapter5

Anonymous (anonymous@undisclosed.example.com) — 2018-03-11T22:21:15+00:00

5.1 The Mergesort Algorithm Summary Mergesort sorts a list by dividing it into two equal parts, sorting each half by recursion, then combining resulting sorted components. The recurrence relation for mergesort is T(n) <= 2T(n/2) + cn when n>2 and T(2)

chapter6

Anonymous (anonymous@undisclosed.example.com) — 2018-03-25T12:15:02+00:00

6.1 Weighted Interval Scheduling Summary There is no known greedy solution for this problem. Using a straightforward algorithm, we would get an exponential algorithm. To decrease the runtime and redundancy of the computations, we can use memoization. Memoization is the technique of saving values that have already been computed. The runtime of M-Compute-Opt(n), the version of the algorithm that uses memoization, is O(n). However, we are not done. We need to also retroactively compute the compon…

chapter7

Anonymous (anonymous@undisclosed.example.com) — 2018-04-01T16:57:35+00:00

7.1 Max Flows and Ford-Fulkerson Summary A flow network is a directed graph G=(V, E) that has a capacity associated with each edge, a single source node, and a single sink node. Our goal is to create an algorithm that computes the maximum flow of the flow network while also satisfying capacity and conservation conditions. Our algorithm will push flow forward on edges with leftover capacity and push flow backward on edges that are already carrying flow, to divert it in a different direction. We…

home

Anonymous (anonymous@undisclosed.example.com) — 2018-03-31T03:47:54+00:00

Abby's Wiki-Style Journals * Preface * Chapter 1: Introduction * Chapter 2: Algorithm Analysis * Chapter 3: Graphs * Chapter 4: Greedy Algorithms * Chapter 5: Divide and Conquer * Chapter 6: Dynamic Programming * Chapter 7: Network Flows

preface

Anonymous (anonymous@undisclosed.example.com) — 2018-01-16T00:04:38+00:00

Preface The First Two Pages Summary of the Section * Algorithms are everywhere and have many applications within computer science and beyond. We must look through at computer science through the lens that algorithms provide us, as algorithms are central to computer science as a whole. Because problems that can be solved by algorithms are rarely clear and cleanly packaged, the “algorithmic enterprise” has two major tasks: getting to the mathematical core of the problem and identifying the ap…

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2018-04-19T20:45:18+00:00

Abby's Wiki * Preface * Chapter 1 * Chapter 2 * Chapter 3 * Chapter 4 * Chapter 5 * Chapter 6 * Chapter 7 ---------- <- Abby's Wiki-Style Journals <- CSCI 211: Algorithm Design and Analysis