Protected: CMSC 660 Scientific Computing I Homework
There is no excerpt because this is a protected post.
CS110 C++ Programming
|
1 |
#pragma warning(disable:4996) |
Clean code deveopment: http://lumiera.org/project/background/CleanCodeDevelopment.html * [http://www.cplusplus.com/doc/tutorial Here] is a great C/C++ tutorial. * [http://www.thegeekstuff.com/2012/08/gprof-tutorial/ GPROF Tutorial – How to use Linux GNU GCC Profiling Tool] ==Style== *Clean code deveopment: http://lumiera.org/project/background/CleanCodeDevelopment.html ==Warning== #pragma warning(disable:4996) ==PCH== # Right-click on your project … Continued
CS475 Algorithm Analysis and Design
== Treap ==
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <iostream> using namespace std; const int INF = 200000000; class treap{ public: class node{ public: int x,y,c; node *l,*r; node(int data=0):x(data),c(0),l(0),r(0){y=((rand()<<15)+rand())%INF;} }; node *root, *null; public: treap(){null=new node(); null->l=null->r=null; null->y=INF; root=null; } void update(node*&p){ if(p!=null){p->c=p->l->c+p->r->c+1; }} void lr(node *&p){ node *q=p->l; p->l=q->r; q->r=p; update(p); update(q); p=q; } void rr(node *&p){ node *q=p->r; p->r=q->l; q->l=p; update(p); update(q); p=q; } void ins(node *&p, int x){ if (p==null){ p=new node(x); p->l=p->r=null; p->c=1; } else if (x<p->x) { ins(p->l,x); if(p->l->y<p->y) lr(p); } else { ins(p->r,x); if(p->r->y<p->y) rr(p); } update(p); } void del(node *&p, int x){ if (p==null) return; if (p->x==x) del(p); else if (x<p->x) del(p->l,x); else del(p->r,x); if (p!=null) update(p); } void del(node *&p){ if (p->l==null&&p->r==null) {delete p; p=null; return; } if (p->l->y<p->r->y) {lr(p); del(p->r); } else {rr(p); del(p->l); } update(p); } bool find(node *&p, int x){ if(p==null) return false; if (x==p->x) return true; if (x<p->x) return find(p->l,x); else return find(p->r,x); } int rfs(node *&p, int k){ if (k<=p->l->c) return rfs(p->l,k); else if (k==p->l->c+1) return p->x; else return rfs(p->r,k-p->l->c-1); } void ins(int x){ ins(root,x); } void del(int x){ del(root,x); } bool find(int x){ return find(root,x); } int rfs(int k){if (k>=1&&k<=root->c) return rfs(root,k); else return -1; } }; treap t; int n,m,x; char s[2]; int main(){ srand(time(0)^141592653); freopen("BST.in","r",stdin); freopen("BST.out","w",stdout); scanf("%d%d",&m,&n); for (int i = 0; i < n; ++i ){ scanf("%s%d",&s,&x); switch (s[0]) { case 'I': t.ins(x); break; case 'D': t.del(x); break; case 'F': printf("%d\n",t.rfs(x)); break; case 'B': printf("%d\n",t.find(x)); break; } } return 0; } |
== Quicksort ==
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void qs(int l, int r){ int p, mid, i, j; i = l; j = r; mid = avg[(l + r) >> 1]; do { while (avg[i] < mid) ++i; while (avg[j] > mid) --j; if (i <= j){ swap(avg[i], avg[j]); swap(order[i], order[j]); ++i; --j; } } while (i < j); if (l < j) qs(l, j); if (i < r) qs(i, r); } |
=== K-th element ===
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void Kth(int l,int r,int k) { int i = l,j = r,mid= a [(i + j) >> 1]; while (i <= j) { while (a[i] < mid) ++i; while (a[j] > mid) --j; if (i<=j) { int t = a[i]; a[i] = a[j]; a[j] = t; ++i;--j; } } if (k >= i && k<= r) Kth(i, r, k); if (k >= l && k<= j) Kth(l, j, k); } |
== Merge Sort ==
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
void Solutions::merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; while (i >= 0 && j >= 0) { nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--]; } while (j >= 0) { nums1[k--] = nums2[j--]; } } ListNode* Solutions::mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == nullptr) return l2; if (l2 == nullptr) return l1; ListNode* h = new ListNode(0); ListNode* ans = h; while (l1 != nullptr || l2 != nullptr) { if (l1 == nullptr) { h->next = l2; break; } if (l2 == nullptr) { h->next = l1; break; } if (l1->val < l2->val) { h->next = l1; h = h->next; l1 = l1->next; } else { h->next = l2; h = h->next; l2 = l2->next; } } return ans->next; } |
== Fast SQRT ==
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 15 times faster than the classical float sqrt. // Reasonably accurate up to root(32500) // Source: http://supp.iar.com/FilesPublic/SUPPORT/000419/AN-G-002.pdf unsigned int root(unsigned int x){ unsigned int a,b; b = x; a = x = 0x3f; x = b/x; a = x = (x+a)>>1; x = b/x; a = x = (x+a)>>1; x = b/x; x = (x+a)>>1; return(x); } |
Reference: http://blog.ruofeidu.com/treap-in-45-lines-of-c/ http://blog.ruofeidu.com/quicksort-in-c/
MA066 Advanced Algebra I
Algebra defines, roughly, relationships. See: http://blog.ruofeidu.com/gradient-circulation-laplacian-divergence-jacobian-hessian-trace/ Matrix Form for Linear Regression For the regression model $$Y = AX + B$$, the coefficients of the least squares regression line are given by the matrix equation $$A = (X^T X)^{-1} X^T Y$$ and … Continued