Small collection of animations of algorithms and data structures Computer Science |
- Small collection of animations of algorithms and data structures
- Is Radix sort always linear for 32 bit integers?
- Share: a solution for both multiple object tracking (MOT) and speed estimation
- Creating a gRPC service in Asp.Net Core
- What are the different computer science textbooks across uni's.. I know Ivy League schools use different ones..
- New DeepMind Unsupervised Image Model Challenges AlexNet
- FooBar
- Incorrect Big O from this O'Reilly book?
- New Facebook PyTorch Hub Facilitates Reproducibility Testing
- Mentoring in programming languages
- Is it actually possible to go from a non CS undergrad background to Graduate school for CS?
- How do you realistically simulate water/waves?
- The Best Machine Learning Course to Learn 2019
- Detailed proof of P = NP
| Small collection of animations of algorithms and data structures Posted: 11 Jun 2019 04:51 AM PDT |
| Is Radix sort always linear for 32 bit integers? Posted: 11 Jun 2019 06:08 PM PDT I came across this Leetcode solution: https://leetcode.com/problems/maximum-gap/solution/. It explains that it can be solved in linear time by using Radix sort instead of Quicksort for example. It offers the following explanation:
Since the maximum digits is <= 10 for a 32 bit integer, and the base is always 10, doesn't this mean that we can always sort an array of integers in linear time using Radix sort? If this is true, it seems like I should always pick Radix sort over something like quicksort for integer arrays. Am I missing something? [link] [comments]  |
| Share: a solution for both multiple object tracking (MOT) and speed estimation Posted: 11 Jun 2019 07:21 PM PDT Hi all, I am just an amateur but I want to share a solution that achieves both multiple object tracking (MOT) and speed estimation at the same time at real-time speed. Here is the demo:  The basic idea is from this article: POI: Multiple Object Tracking with High Performance Detection and Appearance Feature. The process is: Detection (faster R-CNN) + Appearance Feature (GoogLeNet) + Online Tracker (Kalman Filter + Kuhn-Munkres algorithm) It shows state-of-the-art performance in most quotas other than the frame rate (<0.5Hz). To increase the frame rate as well as achieving speed estimation, I made below modifications:
And the improvements include:
A few conclusions:
Please correct me if I am mistaken, thanks for watching. [link] [comments]  |
| Creating a gRPC service in Asp.Net Core Posted: 11 Jun 2019 06:58 PM PDT |
| Posted: 11 Jun 2019 08:23 PM PDT Wandering if anyone knows what computer science textbooks ivy league students get ( undergrad ). I know the Ivy League has different curriculum than 95% of colleges. I was wanting to get an ivy league "approved" CS textbook, to see if its better than the one my uni offered. [link] [comments]  |
| New DeepMind Unsupervised Image Model Challenges AlexNet Posted: 11 Jun 2019 02:27 PM PDT |
| Posted: 11 Jun 2019 07:41 PM PDT I just got an email saying that a new foobar challenge came out on June 6th, anyone gotten it yet [link] [comments]  |
| Incorrect Big O from this O'Reilly book? Posted: 11 Jun 2019 01:41 PM PDT This is literally the second paragraph that I read from "High Performance Python" by Ian and Ozsvald, Micha Gorelick (https://www.oreilly.com/library/view/high-performance-python/9781449361747/ch04.html) "While we saw in the previous chapter that we are restricted to, at best, O(log n) lookup time on lists/tuples with no intrinsic order (through a search operation), dictionaries and sets give us O(n) lookups based on the arbitrary index. In addition, like lists/tuples, dictionaries and sets have O(1) insertion time. [4]" And then the footnote: "[4] As we will discuss in Hash Functions and Entropy, dictionaries and sets are very dependent on their hash functions. If the hash function for a particular datatype is not O(1), any dictionary or set containing that type will no longer have its O(1) guarantee." Maybe I'm missing something, but I see three things wrong here: (1) You can't get O(log n) lookup from an unordered list. (2) Dictionaries/sets are implemented as hashtables which give O(1) lookup. (3) The footnote makes no sense. For a hash function to be worse than O(1), that would imply that it looks at more than one key. Because the N here is the number of items in the hashtable, not the length of a single item. Am I missing something? [link] [comments]  |
| New Facebook PyTorch Hub Facilitates Reproducibility Testing Posted: 11 Jun 2019 09:09 AM PDT |
| Mentoring in programming languages Posted: 11 Jun 2019 12:55 PM PDT Hey, if you're interested in Javascript, C#, Java, Python, C++/C, android/web/ios programming, and would like to have a mentor, follow streams and be able to interact with the streamers, you can join our new community. It currently has ~1350 members and are growing quite fast! I hope to be able to contribute as much as possible to this community :) Hope to see u there! [link] [comments]  |
| Is it actually possible to go from a non CS undergrad background to Graduate school for CS? Posted: 11 Jun 2019 12:16 PM PDT Yes, I technically know it's possible, but what is it like for those who have done it? I want to hear your stories. I finished my bachelors in CS, yet I still feel like I'm at a disadvantage. I want to know what efforts you and others put it to achieve what you needed. What was the hardest part? What was the easiest part? [link] [comments]  |
| How do you realistically simulate water/waves? Posted: 11 Jun 2019 07:53 AM PDT I'm trying to simulate water/waves movement in a 3D engine. Conceptually, I have a 2D matrix where the value in each cell is that pixel's height. I have tried modifying the height by sampling from a sinusoidal distribution (using the timestamp of a given frame) s.t. the animation is continuous. The downside of this is that the entire thing looks really bland and has no randomness. To fix this, I initially sampled perlin noise to initialize the matrix values and then added the sampled sinusoidal values on top. This is much better and resembles water, but if you look at it long enough you can see that it's just a terrain map that goes up and down periodically. What am I missing? How is this traditionally done? Any method I'm coming up with now seems to be overlycomplicated and excessive. [link] [comments]  |
| The Best Machine Learning Course to Learn 2019 Posted: 11 Jun 2019 09:30 AM PDT |
| Posted: 11 Jun 2019 09:00 AM PDT I have a new proof with an algorithm for the known NP-complete problem MONOTONE-1-IN-3-3SAT that no one has found before, The trick is that I noticed this can be reduced to the input for a nondeterministic logarithmic space Turing machine M such that M accepts the input if and only if the instance is an element of MONOTONE-1-IN-3-3SAT. Since the complexity class NL is contained in P, then this language MONOTONE-1-IN-3-3SAT can be solved in polynomial time. Given a monotone formula F, we construct another Boolean formula G which is an instance of XOR-SAT such that -- if F has a truth assignment such that each clause has exactly one true literal if and only if G complies with the same property. -- G contains clauses of two and three literals. The amount of clauses of three literals is equal to F, but the number of clauses of two literals is at most six times per each clause in F. Therefore, there are a polynomially amount of clauses in G in relation to F. -- The Boolean formula G has always three new variables for each clause of three literals and every variable appears once as a positive literal and once as a negated literal in the clause of two literals. We enumerate the variables in G for 1 to 3m (where m is the amount of clauses of F). We do this from the clauses of three literals and later we replace the old variables that are still in the clauses of two literals. For example (+ denote the EXCLUSIVE OR): (x1 + y1 + z1) ^ (x2 + g1 + w1) ^ ... ^(not x1 + x2) ^ (not x2 + x1)^.... is transformed with the new enumeration as (x1 + y2 + z3) ^ (x4 + g5 + w6) ^ ... ^(not x1 + x4) ^ (not x4 + x1)^... (notice that we also replace the new enumeration in the variables of two clauses). Then we construct another Boolean formula H that is in 2CNF where every clause has no positive literals. In this way, we create H for the clauses in ascending enumeration as follows: For the first clause (x1 + y2 + z3) we create (not x1 v not y2) ^ (not x1 v not z3) ^ (not y2 v not z3) for the second we do the same until the last one clause of three literals in G. Finally, we join all these formula from left to right in H. Notice the original clause (x v y v z) has exactly one true literal if and only if (x1 + y2 + z3) and (not x1 v not y2) ^ (not x1 v not z3) ^ (not y2 v not z3) have the same satisfying truth assignment. Certainly, (x1 + y2 + z3) is true if 1 or 3 variables of the set {x1, y2, z3} are true and (not x1 v not y2) ^ (not x1 v not z3) ^ (not y2 v not z3) is true if 1 or 0 variables of the set {x1, y2, z3} are true. Now, we create a logspace verifier M such that on H as input and a truth assignment as a certificate which has the first variable in the enumeration as the first one from left to right, the second variable in the enumeration as the second one and so forth... Since for a truth assignment with the enumerated order, the first three variables are only in the first three clauses in H from left to right, and the next three variables are in the next contiguous three clauses and so on, then we can analyze each time three variables which represent a logarithmic space in the work tapes in M and we do not have to look backward in the special read-once polynomial tape. We prove that L = +L, therefore XOR-SAT is in NL. We obtain a nondeterministic logarithmic Turing machine N which outputs every possible satisfying assignment of an instance of XOR-SAT in logarithmic space when XOR-SAT is in NL. In addition, we assume N outputs in the truth assignment with the enumerated order of the variables that we mentioned before. Therefore, if M(H, N(G)) = "yes" then H and G have the same satisfying truth assignment which also means F is in indeed in MONOTONE-1-IN-3-3SAT. M is converted into not deterministic from now because N is nondeterministic. In addition, the special tape will still be read at once since we process a single symbol of the output of N(G) as much as it is required to read a new symbol in the certificate. There will not be a backward move direction since the output is written from left to right. Since NL is contained in P and M now is a nondeterministic logarithmic Turing machine, then we can assume that MONOTONE-1-IN-3-3SAT can be solved in polynomial time. However, this algorithm requires that L = +L for the creation of the nondeterministic logarithmic Turing machine N in the previous reduction. I have a logarithmic space algorithm for XOR-3SAT that no one has found before, The trick is that I noticed this can be reduced to the language MONOTONE XOR-4SAT and thus, this problem is hard for parity-L. Besides, I noticed that an instance of MONOTONE XOR-4SAT is equivalent to an instance of XOR-2SAT which is in SL. Certainly, a clause of MONOTONE XOR-4SAT when (a + b + c + d) is satisfiable under some truth assignment if and only if a + b and c + d have different assignments for the same truth assignment, that is if x = a + b and y = c + d and thus (x + y) is satisfiable where + is XOR operation. However, we do not use XOR-2SAT for the logarithmic space reduction. Indeed, we use the another SL problem that is HITTING--SET--2 which is whether a subset from a "universe" set U can intersect exactly one element with every set S_i that is within a list of sets of elements from the same "universe" set U such that the cardinality of each set S_i is at most 2. This guarantee in a reduction for each clause (a + b + c + d) that a+b and c+d should exist in the same set S_j and thus, they should be intersected exactly one of them by a subset of U, so one of the formulas a+b and c+d could be true and the other false according to this intersection. In this way, we guarantee if we cannot separate the elements of the set S_j that we obtain in the reduction by a subset from the universe U, then the formula is unsatisfiable for MONOTONE XOR-4SAT since we cannot evaluate a+b and c+d as opposite truth assignments. Since SL = L, then the proof is completed. This is all for now. Any comment, critic, advice or improvement are always welcome. The paper is in https://www.academia.edu/39517235/A_Solution_of_the_P_versus_NP_Problem and you can download it in https://zenodo.org/record/3243510 Thanks in advance!!! [link] [comments]  |
| You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
| Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States | |
No comments:
Post a Comment