Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:dikm:home [2018/01/17 04:55] – dikm
+++ courses:cs211:winter2018:journals:dikm:home [2018/01/30 04:59] (current) – [Chapter 2.4 - Survey of Common Running Times] dikm
@@ Line 1: / Line 1: @@
-====== Chapter 1.1 Summary:
+====== Michael's Wiki ======
- ======
+===== Chapter 1.1 Summary:  =====
 Stable matching problem
@@ Line 10: / Line 11: @@
 A prefers her current situation over working for employer E.
+===== Chapter 2 =====
-====== Chapter 2.1 Computational Tractability:  ======
+==== Chapter 2.1 Computational Tractability:  ====
@@ Line 35: / Line 37: @@
 Helps to see that there might not be an efficient algorithm for a particular problem
-====== Chapter 2.2 Asymptotic Order of Growth:  ======
+==== Chapter 2.2 Asymptotic Order of Growth:  ====
@@ Line 50: / Line 52: @@
 Exponentials- fast growing
-Every exponential grows faster than every polynomial  ====== Michael's Wiki ======
+Every exponential grows faster than every polynomial
+==== Chapter 2.4 - Survey of Common Running Times  ====
+**Summary: Goes over various common running times and common problems associated with those running times.
+Search space : The set of all possible solutions the search for algorithms' whose performance is more efficient than a brute-force enumeration of this search space.
+One of the goals of the book is to improve on brute-force algorithms **
+//Linear Time//
+-At most a constant factor time the size of the input
+Ex.
+Computing the Maximum
+Merging Two Sorted Lists
+**//O(n logn) Time: //**
+Running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear times
+Ex.
+Sorting Algorithms like Mergesort
+Algorithms whose most expensive step is to sort the input
+**//Quadratic Time://**
+Performing a search over all pairs of inputs and spending constant time per pair
+Also arises naturally from nested loops.
+**//Cubic Time:  //**
+More elaborate sets of nested loops.
+Ex.
+Finding sets which are disjoint
+**//O(n^k) Time// **
+Arises for any constant k when we search over all subsets of size k
+Ex.
+Finding independent sets in a graph
+==== Chapter 2.5 - More Complex Data Structure: Priority Queue  ====
+**Summary: Priority Queue can be implemented well using a Heap data structure which is like a balanced binary tree. The Heap data structure with Heapify-down and Heapify-up operations can efficiently implement a priority queue that is constrained to hold at most N elements at any point in time**
+We seek algorithms that improve qualitatively on brute-force search and in general we use polynomial-time solvability as the concrete formulation of this.
+Priority Queue – designed for applications in which elements have a priority value or key and each time we need to select an element form S, we want to take the one with the highest priority
+-Smaller keys represent higher priorities
+-Supports addition and deletion of elements from the set and also the selection of the element with smallest key
+Heap data structure- Useful data structure for implementing a priority queue
+Combines the benefits of a sorted array and list
+Useful to think of as a balanced binary tree
+Tree will have a root, and each node can have up to two children, a left and a right child
+Heap Order: for every element v, at a node I, the element w at I's parent satisfies key(w) <= key(v)
+Common Operations:
+Accessing Min- O(1) time because it will be the root
+Heapify-Up – Used to 'fix' the heap after an element is added or deleted and an element is in a spot it is 'too big' for
+Heapify-Down – Inverse of Heapify-up : is used to 'fix' the heap when an element is deleted or added and an element is 'too small' for its current spot.
+====  Chapter 3.1 Graphs- Basic Definitions and Applications:  ====
+**Summary: Goes over some basic graph types and some uses for a graph**
+Graph – collection of things and join some of them by edged
+Examples/Uses:
+   *  Transportation Networks
+  *   Communication Networks
+  *   Information Networks
+  *   Social Networks
+Simple Path- all vertices are distinct from one another
+Cycle – a path v1,v2,...vk-1,vk in which k >2, the first k-1 nodes are all distinct, and v1=vk. In other words, the sequence of nodes "cycles back: to where it began.
+Tree – an undirected graph, is connected and does not contain a cycle, the simplest kind of connected graph.
+-Rooted trees help to explain the concept of hierarchy in computer science.
+//Theorem 3.2:
+Let G be an undirected graph on n nodes. Any two of the following statements implies the third.
+- G is connected
+- G does not contain a cycle
+- G has n-1 edges.
+//