Advanced Data Structures

Algorithms in Computational Biology

Applied Genomic Technologies

Basic Data Struc and Object-Oriented Des

Biological Databases

Design and Analysis of Algorithms

Discrete Mathematics

Fluency in Information Technology

Genomics Proteomics and Network Bio

Intro to Comp Sci and Object-Oriented Prog

Introduction to Bioinformatics Algo

Introduction to Computer Science JAVA

Molecular Sequence Analysis

Testing Exceptions What we want to test: If a method specification says it may throw an exception, make sure it does so for that input. Ex: add(int index, E element) should throw an IndexOutOfBoundsException if the index < 0 Testing Exceptions try { // make a call that causes the exception. myList.add(- 1, “CSE12”); } catch (IndexOutOfBoundsException e) { } Testing Exceptions try { // make a call that causes the exception. myList.add(- 1, “CSE12”); } catch (IndexOutOfBoundsException e) { } If this line does NOT throw exception, should the test pass or fail? Testing Exceptions try { // make a call that causes the exception. myList.add(- 1, “CSE12”); fail(“Should have thrown IOBException ”); } catch (IndexOutOfBoundsException e) { } Makes the test fail Testing Exceptions try { // make a call that causes the exception. myList.add(- 1, “CSE12”); } catch (IndexOutOfBoundsException e) { } If this line throws an exception, where does the control go? Testing Exceptions try { // make a call that causes the exception. myList.add(- 1, “CSE12”); } catch (IndexOutOfBoundsException e) { // IF control reaches here, we want the test to pass. // The test passes if we do nothing  } Number of tests • How many tests do I write? o Really depends on how you write tests. For some 10 might be enough, others 20.. o Make them as modular as possible. So that each test tests specific things for each method. o For example:  testAddGet – add elements and use get() to check whether they were added in the right index.  testAddException – pass invalid index and see if IndexOutOfBoundsException is thrown. 1 Have a great weekend! Acknowledgments Prof.Kube and Prof.Cynthia Lee

CSE | 12 | Basic Data Struc and Object-Oriented Des | lecture notes | Testing Exceptions What we wan

Know Thy Complexities! www.bigocheatsheet.com Big-O Complexity Chart Horrible Bad Fair Good Excellent O(log n), O(1) O(n) O(n log n) O(n^2) O(2^n) O(n!) Operations Elements Common Data Structure Operations Data Structure Time Complexity Space Complexity Average Worst Worst Access Search Insertion Deletion Access Search Insertion Deletion Array Θ(1) Θ(n) Θ(n) Θ(n) O(1) O(n) O(n) O(n) O(n) Stack Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Queue Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Singly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Doubly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) Skip List Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n log(n)) Hash Table N/A Θ(1) Θ(1) Θ(1) N/A O(n) O(n) O(n) O(n) Binary Search Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n) Cartesian Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n) O(n) O(n) O(n) B-Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) Red-Black Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) Splay Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n) AVL Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) KD Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n) Array Sorting Algorithms Algorithm Time Complexity Space Complexity Best Average Worst Worst Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n)) Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n) Timsort Ω(n) Θ(n log(n)) O(n log(n)) O(n) Heapsort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1) Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1) Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1) Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1) Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n) Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(1) Bucket Sort Ω(n+k) Θ(n+k) O(n^2) O(n) Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k) Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k) Cubesort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

CSE | 282 | Introduction to Bioinformatics Algo | lecture notes | Know Thy Complexities! www.big

Lecture 06  More Clustering o Say we finished our clustering algorithm, but we can still end up with different clusters o We want “tight” clusters: we want all of the nodes of the same cluster to be close together o We want “separated” clusters: we want the different clusters to be far apart from one another  Computing the Optimal Clustering o Say we have Data Z = { z 1 ,z 2 ,…,z n } (where each element can be multidimensional) o Say we have Inference ∆ = { ∆ 1 ,∆ 2 ,…,∆ n }  ∆ i = { 1,2 ,…,K } o Say we have a Distance Function d ( z i ,X k ) o We can thus construct a Target Function:  min K,∆ f ( Z,∆,K )  f ( Z,∆,K ) = ∑ k = 1 K ∑ ∆ i = k d ( z i ,X k ) o However, this fails when k = n (since minimal sum of distances would be if we had each node in its own cluster, because each distance would be 0, so sum of distances is 0)  Thus, we probably want a penalty for how many clusters k we make  ChIP-Seq Technology o Chromatin Immunoprecipitation (ChIP) followed by sequencing o Transcription factor binds to DNA, and while it’s bound, somehow “fix” it to the DNA o Shear the DNA, and the parts bound by TF will be preserved o Extract the TFs using antibodies o Purify DNA and sequence, and you’ll see what parts were bound by the TFs  ChIP-Seq Data o Unlike TF ChIP-Seq results, which tend to be pretty targeted, Histone ChIP-Seq results typically span a wide range of the genome  Where do TFs Bind in the Genome? o Most TFs bind around the proximal promoter o Some, however, bind all over the place!  How is Specificity of TF Binding Achieved? o Consensus motif  Commonly found sequence  Shows which nucleotide is most abundant at each position  Example: YYANWYY o Used to computationally identify potential binding sites o Does not guarantee specificity o ChIP-Seq suggests some TFs don’t require a specific motif (E2F)

CSE | 183 | Applied Genomic Technologies | lecture notes | Lecture 06  More Clustering o

Lecture 13 - Red-Black Tree Insertions and Review  Red-Black Tree Insertion: Black Sibling o Case 0 : Parent of node being inserted is black (just insert, no worries) o Case 1 : P is left child of G , X is left child of P (single rotate right then recolor) o Case 2 : P is left child of G , X is right child of P (single rotate X and P left, then do Case 1) o Case 3 : P is right child of G , X is right child of P (single rotate left then recolor) o Case 4 : P is right child of G , X is left child of P (single rotate X and P right, then do Case 3) o For all of these cases, we assumed that the inserted node's sibling is black  What about if inserted node's sibling is red?  Red-Black Tree Insertion: Red Sibling o AVL Rotation algorithm we used for Black Sibling insert fails, because we still end up with parent and node being red o Instead, we start at root, and as we go down, if we find any cases where there's a black node with 2 red children, we make its 2 children black and make it red o Now what? This could result in a problem if this node has a red parent!  However, now we have a structure that we've seen before! Ignoring the 2 newly black children, we now have the 2-red-in-a-row structure!  AVL Rotate just like before! o Now continue down from where you were before the AVL rotate stuff, and insert the new node just like normal  Can any node have 2 red children? o Yes! That's perfectly fine! The only problem with 2 red children is if we're inserting through those children, which THEN we would have to change this property!  Midterm Review o Go over the clicker questions o It will have multiple choice, short answer, and a bit of coding (C++) o Have to memorize the properties of the major data structures we've talked about!!! o A Treap is a structure that has both BST and Heap properties  “Key” is in terms of the BST properties  “Priority” is in terms of the Heap properties  Both sets of properties must be maintained  An RST is just a Treap that has randomized priorities assigned to it o A Skip List of level n has forward pointers 0 to n -1  So a Skip List of level 2 has forward pointers 0 and 1 (2 total)

CSE | 100 | Advanced Data Structures | lecture notes | Lecture 13 - Red-Black Tree In

Lecture_05.docx-Lecture 05  Midterm Topics o

All courses in CSE

Popular Documents