Navigating Line Segments If you’re given a problem to find out whether two line-segments intersect, there is an easy approach to this. It involves finding the orientation of the line segments. If they’re different, they intersect. Each line segment has a start-point and an end-point. Our first line will be represented by (a1,b1) and our second line will be represented by (a2,b2). To test if they intersect, we need to verify the following condition: What does this mean exactly? Let’s jump into an example and find out. It’s clear to us that the two line-segments intersect, but it’s not clear
Author: Dino Cajic
A Visual Guide to Graham’s Scan Graham’s scan is a method for finding the convex hull that encompasses all points on the plane. Below you’ll see an example of a convex hull. Graham’s scan starts by finding the point with the lowest y coordinate. If there are multiple points on the y-coordinate, the point with the smallest x-value is chosen. The points are sorted by polar angles in counterclockwise rotation. Graham’s scan utilizes the stack. Points are pushed onto the stack. If the point is not part of the convex hull, the point is popped from the stack. Let’s look
Finding the Closest Pair of Points on a Plane If we’re given a set of points that lie on a plane, how can we figure out which pairs are the closest pair of points on the plane? The points are frequently stored in an array. One approach is to take the divide and conquer method. How? By following the steps below: Count the number of points on the plane. Divide the points into two equal groups and draw a line through the middle. If there are an odd number of points, a line will go through at least one of the
A Visual Guide to Voronoi Graph & Delaunay Triangulation Voronoi diagrams help us find the closest points from an arbitrary point. Let’s start by displaying a set of points on a plane. The Voronoi diagram draws boundaries between each of those points. Around each point, regions will develop called the Voronoi regions. Let’s see how we would draw those boundaries. Each boundary should be in the middle of two points. Let’s begin by drawing a boundary between point 1 and point 2. The boundary should be directly in the middle separating the two points. Let’s move to creating a boundary
Understanding Maximum Independent Set Visually Given a graph, a subset of the vertices is an independent set if there are no edges between the vertices in the subset. Let’s take a look at a quick example to see what this means. We can see that there is an edge between the following points: Points 1 and 2 Points 1 and 3 Points 1 and 4 Points 2 and 3 Points 2 and 5 Points 3 and 5 Points 4 and 5 Points 4 and 6 Points 5 and 6 When trying to find the maximum independent set, we’ll try to
Understanding Minimum Vertex Cover Visually When trying to find the minimum vertex cover, you’re going to be trying to find the minimum number of vertices that will include all the edges. We can start with the densest vertex on the graph and hope that we get lucky. We can choose vertex 3 next. Through some trial and error, you’ll see that you will have to choose 2 points from points 1, 2, and 3 regardless of which point you choose next. Finally, we must choose either vertex 4 or vertex 6. We’ll choose vertex 4. Since all the edges are
Visual Explanation of Maximum Clique Maximum clique is a technique used to find the largest vertex cluster where each vertex is connected to each other. Let’s look at an example. We’ll examine each vertex and see what the greatest cluster of the following graph will be. Let’s look at the first vertex. Vertex 1 is connected to vertices 2, 4, and 6. We need to make sure that each of those vertices has a connection to one another as well. Is vertex 2 connected to vertex 4? Yes Is vertex 2 connected to vertex 6? Yes Is vertex 4 connected to
Programming Language Concepts Let’s finish this series off right: with another 141 questions. I think 781 questions are a good starting point in your Computer Science exploration. Check out the links at the bottom of the page for the previous 640 questions. 641. True or False? Pointers in C can point to any variable. – True 642. How do you get the address of a variable in C? – with the ampersand symbol (&) 643. If the pointer is pointing to an array, what are the 3 forms of pointer arithmetic supported in C and C++? – Adding an integer
Programming Language Concepts I think it’s time to start moving into some relatively modern questions. 547. What is an associative array? – An unordered collection of data elements that are indexed by keys. 548. Each element of an associative array is a pair consisting of a _______ and a _______. – key and a value 549. True or False? Java supports associative arrays? – True. As a matter of fact, Perl, Python, Ruby, C++, C# and F# do too. 550. What are associative arrays called in Perl? – hashes 551. Why are associative arrays in Perl called hashes? – Because
Programming Language Concepts Back at it again. This time we’ll cover some common questions/answers you may encounter when asked about: Names, Bindings and Scopes Data Types 401. Names are also called _______. – Identifiers 402. Why are names also called identifiers? – Because they are used to identify a variable, a function, class or other program constructs. 403. Fortran I names had a maximum name length of _____. – Six 404. COBOL names had a maximum length of ______. – 30 405. Name two languages that don’t have a name length limit. – Java and C# 406. How are scalar,