W&L Computer Science Wiki - courses:cs211:winter2014:journals:emily

entryeight

Anonymous (anonymous@undisclosed.example.com) — 2014-03-26T03:04:55+00:00

This chapter introduces a new design technique. Instead of using greedy algorithms or divide and conquer, we use dynamic programming. It comes from the divide and conquer method but is the opposite of greedy solutions. This techniques divides a problem into subproblems then builds up solutions to those subproblems until it reaches the full problem. It is close to brute-force.

entryfive

Anonymous (anonymous@undisclosed.example.com) — 2014-02-26T04:51:41+00:00

Entry Five Chapter 4.2 Scheduling to Minimize Lateness: An Exchange Argument In this section we look at solving another scheduling problem where there is one resource and a set of requests to use that resource for a certain amount of time. Each request has a deadline and a time interval length and can be scheduled any time before the deadline. Different requests cannot overlap. An example of this problem is scheduling jobs to minimize lateness. The algorithm must determine a start and a finis…

entryfour

Anonymous (anonymous@undisclosed.example.com) — 2014-02-11T03:24:08+00:00

Entry Four Chapter 3.4 Testing Bipartiteness: An Application of Breadth-First Search A bipartite graph is a graph where one node V can be partitioned into sets X and Y where X are red and Y are blue. In a bipartite graph it is possible to color all the nodes blue and red so every edge has one red end and one blue end.

entrynine

Anonymous (anonymous@undisclosed.example.com) — 2014-04-02T06:22:37+00:00

Entry Nine Chapter 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm In this chapter we are working on modeling transportation networks through graphs. These network models require capacities, source, and sink nodes. Capacities represent how much the edges can carry. Source nodes generate traffic and sink nodes absorb traffic (destination nodes). We also have to represent that traffic that is transmitted across edges.

entryone

Anonymous (anonymous@undisclosed.example.com) — 2014-02-24T20:10:14+00:00

Entry One Chapter 1.1 The Stable Matching Problem - Gale and Shapely * design an admissions/recruiting process that was self-enforcing * based on matching preference lists * if the process is based on self interests, then there will be situations where people will commit and possibly go back on their commitments if a better offer comes along (retract and redirect)

entryseven

Anonymous (anonymous@undisclosed.example.com) — 2014-03-25T19:10:31+00:00

Entry Seven Chapter 5.2 Further Recurrence Relations This section focuses on solving recurrence relations more generally. We look at divide and conquer algorithms that have q recursive calls on subproblems of size n/2. This recurrence relation is represented as T(n) =< qT(n/2) + cn.

entrysix

Anonymous (anonymous@undisclosed.example.com) — 2014-03-05T02:49:40+00:00

Entry Six Chapter 4.7 Clustering How do minimum spanning trees play a role in clustering??? Clustering is when you organize a collection of objects into coherent groups. How might we organize these groups? By how similar they are. We use a distance function on the objects with the assumption that those closer together are more similar to each other.

entrythree

Anonymous (anonymous@undisclosed.example.com) — 2014-02-10T18:42:29+00:00

Entry Three Chapter 3.1 Basic Definitions and Applications In this section, we learn about the basic elements and characteristics of graphs. A graph consists of V (nodes or vertex) and E (edges) which are represented as a two-eement subset of V: e={u,v}. A directed graph is a specific type of graph that has directed edges and ordered pairs of nodes to represent asymmetric relationships. We use the words tail and head to describe the nodes and to show that they are not interchangeable. We as…

entrytwo

Anonymous (anonymous@undisclosed.example.com) — 2014-02-24T20:09:01+00:00

Entry Two Chapter 2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays In this section of chapter two, we explore the tradeoffs between lists arrays and lists to determine which data is appropriate for the algorithm. Some of the tradeoffs we read about are finding an element in the array or list with given index i, seeing if a given element is an array or list and if the array is sorted or not. An important concept to take away from this section is that preprocessing allows u…

home

Anonymous (anonymous@undisclosed.example.com) — 2014-04-01T23:04:32+00:00

Emily's Journal Journal Entries Listed In Order: Preface, 1.1, 2.1, 2,2 First Entry 2.3, 2.4, 2.5 Second Entry 3.1, 3.2., 3.3 Third Entry 3.4, 3.5, 3.6, 4.1 Fourth Entry 4.2, 4.4, 4.5, 4.6 Fifth Entry 4.7, 4.8, 5.1 Sixth Entry 5.2, 5.3, 5.4 Seventh Entry 6.1, 6.2, 6.3, 6.4 Eighth Entry 7.1, 7.2, 7.5, 7.7 Ninth Entry

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2014-04-01T23:03:47+00:00

Home First Entry Second Entry Third Entry Fourth Entry Fifth Entry Sixth Entry Seventh Entry Eighth Entry Ninth Entry CS211-W14 Wiki Home Course Website