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

2.3

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

Review: Gale-Shapley Stable matching algorithm has at most n^2 iterations --> worst-case runtime = O(n^2)

2.4

Anonymous (anonymous@undisclosed.example.com) — 2018-01-30T03:51:15+00:00

2.4: Runtimes This Chapter went into further detail about some common running times, including: Linear time O(n) This running time is at most a constant factor times the size of the input. Common problems that have this running time include computing the maximum and merging two sorted lists.

3.2.6

Anonymous (anonymous@undisclosed.example.com) — 2018-02-07T04:55:59+00:00

3.2-3.6: Brief summary 3.2 covered graph connectivity and graph traversal, including breadth-first and depth-first searches, which determine s-t connectivity, or whether or not there is a path between s and t in a given graph. 3.3 covered implementing graph traversals using queues and stacks, but also covered the different ways to represent graphs themselves. 3.4 covered an application of BFS that tested bipartness, and 3.5 covered connectivity in directed graphs. Overall, this section wasn't …

4.1.4

Anonymous (anonymous@undisclosed.example.com) — 2018-02-27T04:39:01+00:00

Chapter four largely focused on greedy algorithms. Parts one and two helped me understand how to prove if/when a greedy algorithm is, in fact, the optimal solution to a problem. * Part one had its own method to help me do so called the greedy algorithm stays ahead. It focuses on measuring the progress of the greedy algorithm each step of the solution and comparing it to any other algorithm. The logic behind this is that, if we can prove that the greedy algorithm is more efficient than alterna…

4.5.7

Anonymous (anonymous@undisclosed.example.com) — 2018-03-06T03:15:58+00:00

Section 4.5 discusses the minimum spanning tree problem, which is focused on finding the cheapest possible connected graph (such that every pair of nodes is connected). It presented 3 primary algorithms for this problem, each of which is guaranteed to produce an optimal solution:

4.85.3

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

This was a lot of reading! We started with Huffman codes, which I felt like I understood more from my class with Levy than I did from the textbook. 5.1 covered divide and conquer, 5.2 covered more recurrence relations, and 5.3 covered counting inversions. I have more hand-written notes to add because I'm an idiot

6.0.3

Anonymous (anonymous@undisclosed.example.com) — 2018-04-03T02:56:12+00:00

6.0-6.3

7.1.1

Anonymous (anonymous@undisclosed.example.com) — 2018-04-03T02:56:26+00:00

7.1-7.2, 7.5, 7.7

chapter2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-21T16:14:54+00:00

Chapter 2 2.1-2.2 Discrete: involving an implicit search over a large set of combinatorial possibilities How do we measure runtime?: using the worst case runtime * Why not avg runtime? --> what is average? * When looking at polynomial runtimes, we only really need to pay attention to the highest-order term

chapters1_2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-19T22:42:54+00:00

1.1 Why is stable matching important?: so we don’t have a situation that could spiral out of control, with one person/object/etc. throwing off another object which throws off another object, etc. How should you initially approach complex problems, especially matching ones?

home

Anonymous (anonymous@undisclosed.example.com) — 2018-04-03T02:55:46+00:00

Janie's Wiki 1.1, 2.1, 2.2: Stable Matching and Asymptotes -- separated Chapter 1 from Chapter 2, so this is just Chapter 1. Chapter2 (2.3: Using Lists and Arrays for Stable Matching - folded into Chapter 2 page.) 2.4,2.5,3.1 3.2-3.6 4.1-4.1, 4.4 4.5-4.7 4.8,5.1-5.3 6-6.3 7.1-7.2, 7.5, 7.7

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2018-01-21T17:34:02+00:00

Janie's Wiki * Chapter 1 * Chapter 2 ---------- <- Janie's Wiki <- CSCI 211: Algorithm Design and Analysis